9.2.16

Bad Primes

While testing out various audacious claims I've made in the past I stumbled upon certain pairs of primes p and q such that phi(p*q)/4 is a universal exponent mod p*q.


Example 1:
For example, let p = 5, q = 13, then p*q = 65, so phi(p*q) = (p-1)(q-1) = 48 and phi(p*q)/4 = 12
2^12 = 1 mod 65
3^12 = 1 mod 65
4^12 = 1 mod 65
6^12 = 1 mod 65
.
.
.
64^12 = 1 mod 65

It can be verified that all integers a smaller than 65 that are coprime with 65 equal 1 when raised to the power of 12

Definition: A bad pair of primes is a pair of primes p and q such that phi(p*q)/4 is a universal exponent mod p*q. In other words, p and q are a bad pair of primes if for all elements a smaller than p*q that are coprime with p*q:

aphi(n)/4 = 1 mod n where n = p*q 

The first few bad pairs of primes are (5,13),(5, 17), (5, 37), (5, 41)..., (13, 17), (13, 37)....

Example 2: let p = 13, q = 17, then p*q = 221, so phi(p*q) = (p-1)(q-1) = 192 and phi(p*q)/4 = 48
2^48 = 1 mod 221
3^48 = 1 mod 221
4^48 = 1 mod 221
5^48 = 1 mod 221
.
.
.
220^48 = 1 mod 221

It can be verified that all integers a smaller than 221 that are coprime with 221 equal 1 when raised to the power of 48

Claim: All combinations of Proth primes produce bad pairs of primes.
Proof: Later


Claim: Some combination of strong primes produce bad pairs of primes.
Proof by counterexample: Assume no combinations of strong primes produce bad pairs of primes.

Let p = 17 and q = 41, then p*q = 697, so phi(p*q) = (p-1)(q-1) = 640 and phi(p*q)/4 = 160
2^160 = 1 mod 697
3^160 = 1 mod 697
4^160 = 1 mod 697
5^160 = 1 mod 697
.
.
,
696^160 = 1 mod 697

Since 17 and 41 are both strong primes then the assumption is false => some combination of strong primes produce bad pairs of primes.'.