Problems & Puzzles:
Collection 20th
Coll.20th016.
"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 r1 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^(p1) = 1 mod p^2 (Wieferich primes).
For p >= 5, since 1+r+r^2  (r+1)^pr^p1 (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.
***
