Problems & Puzzles:
JM Bergot poses the following nice puzzle:
One notices that 13^13=13mod(17) is of the
form for two consecutive primes p,q p^p=p mod(q).
Q. Find larger examples
Contributions came from Qu Shun Liang, Torbjörn Alm, Seiji Tomita,
Jan van Delden, Fred Schneider, Gurmeet Singh, Giovanni Resta,
Jean-Claude Rosa & Farideh Firoozbakht.
Qu Shun Liang wrote:
Torbjörn Alm wrote:
p= 65521 q= 65537. Both solutions have q as Fermat primes.
I searched p and q where p < 10^8.
Only one solution was found.
65521^65521 = 65521 mod 65537.
There are interesting relations between p and q where n=2 and 4.
First, q is Fermat prime number.
Next,if q=2^(2^n)+1 and p=q-2^n then p^(2^n) =1 mod q.
65521^(2^4)=1 mod 65537.
Given solution has q=F2=2^(2^2)+1=17, the next is
Using a search, described below, I also found:
Here q cannot be a Fermat number, because the difference q-p=58 is
not a divisor of q-1=2^(2^n) for any n. Smaller solutions [p,q]
might exist, but q-p>64 in that case. (See further).
Obviously the equation doesn't have solutions for p=2. For p>2 it
can be rewritten as: d^d=1 (mod q) with d=q-p, becasuse d is even.
Since (d,q)=1 we should also have d|q-1.
If we drop the requirement that q=nextprime( p), then more solutions
exist. Just a few [p,q] with increasing difference d:
untill d=20. I searched untill d=64. There are no solutions for
d=2,14,18,32,38,46,62 Constructing a table like this has the
disadvantage that a large number d^d-1 has to be factored
Only solution through 10^5: 65521^65521 = 65521 (mod 65537)
Let p and q are consecutive primes
The equation p^p=p mod(q) is equivalent to p^(p-1)=1 mod(q)
And by fermat's little theorem p^(q-1)=1 mod(q)
=> p^(p-1) * p^(q-p)=1 mod(q)
=> p^(q-p)=1 mod(q)
Now let q-p=d
=> (q-d)^d=1 mod(q)
=> (-d)^d=1 mod(q)
As d is even so,
=> d^d=1 mod(q)
=> q is a prime factor of (d^d-1)
Now d can be d=4,6.... so on any even number (for d=2 , p and q are
1 and 3 respectively from which1 is not a prime number )
=> q is a prime factor of (4^4-1)
=> q is a prime factor of 255 which are 3,5 and 17
=> for q=17 , p=q-d=13
=> as 13 and 17 are consecutive primes, so 13 and 17 follows the
given condition which was noticed by J M Bergot
After some investigation we can find out that the next such pair is
for d=6 which is 37 & 43 but unfortunately these are not consecutive
But after some help of computer I had find out a pair of consecutive
primes which follows the given condition
And the pair is 65521 and 65537 for d=16.
I had checked all possible pairs from d=4 to d=26 but
I found only one such pair other than the one which was already
given (13 & 17)
I had used c++ program of my own for solving this problem.
For puzzle 521 I searched for primes up to 4.25 x 10^12,
but I only found the couple p=65521 q=65537.
If the residues were distributed more or less uniformly, then
the probability of a hit would be about 1/q. If this is
the case, since the sum of the reciprocals of the primes diverges
one would expect an infinite number of solutions.
However, the sum 1/p diverges so slowly that a further solution, if
exists, could be unreachable by brute force.
JC Rosa wrote:
About this puzzle here is my solution:
We have p^p=p mod q.
Let q=p+k (k=even number)
The equality p^p=p mod q gives k^k-1=0 mod q
Indeed: p^p=p^(q-k) and p^p=p mod q becomes p^q=p^(k+1) mod q
fromwhere p^(q-1)=p^k mod q. But p and q are prime numbers and
from Fermat's theorem we know that p^(q-1)=1 mod q.
Thus p^k=1 mod q
(q-k)^k=1 mod q fromwhere k^k=1 mod q and k^k-1=0 mod q.
So q is a prime divisor of k^k-1
Examples: k=4 , 4^4-1=255=3.5.17.
q=17 ; p=13 ; 13^13=13 mod 17
k=6 ; 6^6-1=18.104.22.168
q=43 ; p=37 ; 37^37=37 mod 43 but unfortunately 37 and 43 are not
I obtained a solution with two consecutive prime numbers for k=16.
q=65537 ; p=65521 ; 65521^65521=65521 mod 65537
The only other prime p such that p^p = p (mod q) up to
prime(366000) = 5270521
is p = 65521, where q = next-prime(p) = 65537.
Let G(n) = F(n) - 2^n = 2^2^n + 1 - 2^n, it is interesting that the
first such pair (p, q )
is (G(2), F(2)) and the second such pair is (G(4), F(4)).
For odd numbers n we have F(n) | G(n)^2^n + 1.