11.2.16

Kinky Primes

Definition: Kinky primes are pairs of primes of the form (p, q) where p = a1*r + 1 and q = a2*s + 1 such that GCD(a1, a2) > 1 and a1, a2 , r, s are in Z.

Claim: Given a pair of kinky primes (p = a1*r + 1, q = a2*s + 1) the universal exponent mod p*q is phi(p*q)/GCD(a1, a2)

Proof: A slightly kinkier version of the proof presented here

Claim: The set of all bad primes as defined here is a subset of the set of kinky primes.

Proof: Follows from the previous claim.

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.'.

8.2.16

Triumphantless

While rummaging through old graduate textbooks on Algebraic Number Theory I stumbled upon one of the claims I discovered on my own last year.

The claim that phi(n)/2 is a universal exponent when n is the product of 2 distinct odd primes has been around apparently but I first spotted it this morning on page 25 in Henri Cohen's A Course In Computational Algebraic Number Theory, as a second part to the well known Euler theorem.




When I made Conjecture #1 here I looked in many undergraduate and graduate texts but I couldn't find it anywhere so I naively thought that I was the first to come up with it. Especially since  here's what one of the professors that I sent it to had to say about it.