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.