Problems & Puzzles:
Collection 20th
Coll.20th-016.
"Good residues" r mod p
On May 17, 2018,
Jaroslaw Wroblewski,
wrote:
Let p be a prime number. It is a straightforward consequence of Fermat's
little theorem that for any integer r:
(r+1)^p=r^p+1 (mod p).
We will call r a "good residue" mod p if
0<=r<p and the following
stronger condition holds:(r+1)^p=r^p+1
(mod p^2).
Q. Prove that
for any prime p, the number of good residues mod p is NOT
divisible
by 3.
Yilin Zhang wrote on Oct 13, 2018:
For any prime p, we have following property:
If r is a good residue, then -r-1 and r^(-1) mod p are both good
residues.
So from r, we may get
<-> -(1+r) <-> -(1+r)^(-1) <-> -1+(1+r)^(-1)
r <->
<-> r^(-1) <-> -(1+r^(-1)) <-> -(1+r^(-1))^(-1)
But we can prove that -1+(1+r)^(-1) = -(1+r^(-1))^(-1) mod p, i.e. it is
a circle
<-> -(1+r) <-> -(1+r)^(-1) <->
r <-> <-> -1+(1+r)^(-1) or -(1+r^(-1))^(-1)
<-> r^(-1) <-> -(1+r^(-1)) <->
with length = 6. However, the circle can get smaller iff
1. r = -(1+r) -> r = -2^(-1);
2. r = r^(-1) -> r = 1, -1;
3. r = -(1+r)^(-1) -> 1+r+r^2 = 0;
4. r = -(1+r^(-1)) -> 1+r+r^2 = 0;
5. r = -1+(1+r)^(-1) -> r = 0, -2.
It is easy to find that {0, -1} is a circle and r = 0, -1 are always
good residues, while {1, -2, -2^(-1)} is a line and elements are good
residues iff 2^(p-1) = 1 mod p^2 (Wieferich primes).
For p >= 5, since 1+r+r^2 | (r+1)^p-r^p-1 (in sense of polynomial not
module, use root of unit to prove), and 1+r+r^2 = 0 mod p have two roots
r_1, r_2 iff p = 1 mod 6, in this case {r_1, r_2} is also a circle.
Thus, these circles are all disjoint and every good residue must be in
one of them.
In conclusion, let a_p be the number of good residues mod p, then
a_2 = 1, a_3 = 2,
if p is not a Wieferich prime, a_p = 4 mod 6 iff p = 1 mod 6, a_p = 2
mod 6 iff p = 5 mod 6;
if p is a Wieferich prime, a_p = 1 mod 6 iff p = 1 mod 6, a_p = 5 mod 6
iff p = 5 mod 6.
So a_p is NOT divisible by 3.
***
|