Problems & Puzzles: Puzzles

Puzzle 520. Prime divides Repunits Seiji Tomita poses the following nice puzzle: 1. Let p = 1, 13, and 19 (mod 20) be prime and q = 2p+1 is also prime. Then q divides repunit R(p) = (10^p-1)/9. 2. There doesn't exist a prime q such that q^2 divides repunit where q < 10^9. Q: Can you prove these or find a counterexample?

---

Contribution came from Farideh Firoozbakht.

***

Farideh wrote:

The first statement is true.

Proof : 10^((q-1)/2) = (10/q) (mod q) where (a/p) is the Jacobi symbol.
q = 2p + 1, so

10^p = (10/q) (mod q)
= (2/q)*(5/q) (mod q)
= (-1)^((q^2 - 1)/8)*(q/5) (mod q)

but (q^2 - 1)/8 = ((2p + 1)^2 - 1)/8 = p(p+1)/2 is even if p = 20k + 3, 20k + 11,
or 20k + 19 ( 4k' + 3) and is odd if p = 20k + 1, 20k + 9 or 20k + 13 ( 4k' + 1).

Note that since p is a prime greater than 5 and q = 2p + 1 is prime, the
cases p = 20k + 5, 20k + 7, 20k + 15 & 20k + 17 don't happen.

(5/q) = (q/5) (since 5 = 1 (mod 4), and according to the low of quadratic resiprocity for Jacobi Symbol)

p = 1 (mod 20) --> q = 3 (mod 20) --> (q/5) = (3/5) = (2^3/5) = (2/5) = (-1)^((5^2-1)/8) = -1
p = 3 (mod 20) --> q = 7 (mod 20) --> (q/5) = (2/5) = -1
p = 9 (mod 20) --> q = 19 (mod 20) --> (q/5) = (2^2/5) = 1
p = 11 (mod 20) --> q = 23 (mod 20) --> (q/5) = (3/5) = -1
p = 13 (mod 20) --> q = 27 (mod 20) --> (q/5) = (2/5) = -1
p = 19 (mod 20) --> q = 39 (mod 20) --> (q/5) = (2^2/5) = 1

By using these results we deduce that if p = 1, 13 or 19 (mod 20) then 10^p = 1 (mod q).
Namely in this case q divides 10^p - 1 and since q =2p +1 > 3 we deduce that q divides
R(p) = (10^p - 1)/9.
 

***