Binary Reformulations of Classical Primality Criteria: A Number-Theoretic and Engineering-Oriented Computational View

A binary reformulation of classical primality criteria is presented from a combinednumber-theoretic and computational viewpoint. Instead of expressing divisibility throughexplicit division or remainder by n, the proposed formulations are written using operationsnatural to binary arithmetic, including shifts, additions, masks, XOR-based equality checking,and modular inversion over powers of two. Two representative cases are studied: abinary version of the Fermat base-2 test, interpreted as a reconstruction-based acceptancefilter, and a binary version of Wilson’s criterion, yielding an exact deterministic primalitytest at substantially higher computational cost. In addition, the identityn! & (−n!) = 2 ^(n−popcount(n))is discussed as a compact bridge between factorial structure, binary representation, and 2-adic valuation. The objective is not to introduce new primality criteria, but to consolidateclassical ones under a binary computational language that preserves their number-theoreticmeaning while making them more accessible from the perspective of low-level implementation,digital arithmetic, and modular embedded design.