Jump to main content
Circulant Hadamard

Gaussian Parity

Full overview · Gaussian Parity
Show the proof map

Modulo 1+i, a Gaussian integer is determined by the parity of its real part plus its imaginary part.

Lemma (Gaussian parity). For integers , reduction modulo sends to modulo . In particular,

Parity for Gaussian integers

A Gaussian integer has the form , where . Two such numbers are congruent modulo when their difference is a Gaussian-integer multiple of .

We have

Thus divides exactly when is even: in that case and have the same parity, so both halves are integers. If the quotient is a Gaussian integer, its real part also shows that is even.

Consequently, reduction modulo sends

This identifies with the two-element field . In particular,

The factor identities behind these two congruences are

Reduce polynomial coefficients

For any positive odd , apply the same rule to each coefficient in . The target is : the cycle relation stays in place, and each Gaussian-integer coefficient is replaced by its residue or .

For example, a coefficient equal to becomes . A coefficient equal to either sign or also becomes .

Divide before reducing

Both and become zero after reduction, so they cannot be used as denominators in the quotient. In the definition of , first use the sign parity to form the exact integral quotients in characteristic zero. Only then reduce their coefficients modulo .

Output. Multiples of disappear, and both signs have residue . These are the two facts used in the all-ones congruence.

For their role in this proof, see the paper, Section 4, equations (4.5)–(4.9).

Back to Signs Become All Ones