Are all these pairs of primes twin primes?

126 Views Asked by At

For $a$ and $b$ primes, if both $(a^b \bmod b)$ and $(b^a \bmod a)$ are prime, does this imply that $(a,b)$ are twin primes?

For example, for $(a,b)=(41,43)$, $(41^{43} \bmod 43) = 41$ and $(43^{41} \bmod 41) = 2$.

Whereas for $(a,b)=(41,47)$, $(41^{47} \bmod 47) = 41$ but $(47^{41} \bmod 41) = 6$, not a prime.

2

There are 2 best solutions below

1
On BEST ANSWER

No. $3^{11} \bmod 11 = 3$, and $11^3 \bmod 3 = 2$, but $3$ and $11$ are not twin primes.

$(5,13)$ also works, and both of the other primes constructed in this case are odd.

0
On

No, the implication here is that b has a prime remainder when dividing by a, or a has a prime remainder when dividing by b. nothing more. you can see this applying Fermat's little theorem:

$a^{b-1}\equiv 1 \bmod b$ when a and b are coprime ( aka gcd(a,b)==1).

applying the more accurate version we get $a^b\equiv a \bmod b$ if a is prime we have a prime remainder, same ( but different possibly) going the other way: $b^a\equiv b \bmod a$ but one of a or b must be greater which then reduces to a prime so this happens any time either $a \bmod b$ or $b \bmod a$ depending on which is greater, are prime.