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.

***


Records   |  Conjectures  |  Problems  |  Puzzles