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

*smaller than p*q that are coprime with p*q:*

**a**

**a**^{phi(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.'.