15.2.16

Are All Primes Kinky?

I just thought of a new way to prove the now infamous claim about phi(pq)/2  and it involves kinky primes as defined here.

First, here's another claim on kinky primes:

Claim: All pairs of primes p and q where p and q are greater than 2 are kinky.

Proof: By definition, every integer can be represented as either 2m or 2m + 1 for some m in Z since all integers are either even or odd.

Since primes are integers, then the only prime of the form 2m is 2 because by definition of primes a prime must only divisible by itself and 1.

Therefore, every prime p > 2 can be represented as 2m + 1 for some m in Z.

Therefore, every pair of primes p, q > 2 can be represented as (2n + 1, 2m+1) for some n, m in Z

Clearly GCD(2m, 2n) > 1 and in fact it is at least 2  (or exactly 2 if n or m are also prime)

Therefore, all pairs of primes p, q where both p and q are greater than 2 are kinky.

Here's the pseudo code for an algorithm to generate all kinky primes up to a certain limit
where the functions is_prime() and get_prime_after() may use any primality test algorithm.

/* -------------------------------------------------  
 This content is released under the GNU License  
 http://www.gnu.org/copyleft/gpl.html 
 Author: Marina Ibrishimova 
 Version: 1.0
 Purpose: Generate all kinky primes up to a limit 
 ---------------------------------------------------- */ 

//returns all pairs of odd primes up to a limit
recursive_kinky_prime_gen(n, m, a, r) {
kinkypairs[];
for (i = r, i < n, i++) {
//generate b and add pair to list if b is odd prime 
  if is_prime(b = 2*i + 1)
  {
     push_to_kinkypairs(a, b);
  }
//recurse if the maximum b is reached
  else if (b >= n)
  {
   new_a = get_prime_after(a);
    new_r = 2;
    recursive_kinky_prime_gen(n, new_a, new_r);
  }
//return all pairs if max a is reached
else if (a >= m)
  {
return kinkypairs[];
  }
}
}


Example: recursive_odd_prime_gen(20, 7, 3, 2)
1.iteration
a, b = 3, 5

2.iteration
r = 3
a, b = 3, 7

3.iteration
r = 4
do nothing, loop again

4.iteration
r = 5
a, b = 3, 11

5.iteration
r = 6
a, b = 3, 13

6.iteration
r = 7
do nothing, loop again

7.iteration
r = 8
a, b = 3, 17

8.iteration
r = 9
a, b = 3, 19

9,iteration
r = 10
so b > n
therefore restart with a = 5, r = 2

10.iteration
r = 2
a, b = 5, 5

11.iteration
r = 3
a, b = 5, 7

12.iteration
r = 4
do nothing, loop again

13.iteration
r = 5
a, b = 5, 11

14.iteration
r = 6
a, b = 5, 13

15.iteration
r = 7
do nothing, loop again

16.iteration
r = 8
a, b = 5, 17

17.iteration
r = 9
a, b = 5, 19

18.iteration
return (3, 5), (3, 7), (3, 11), (3, 13),(3, 17), (3, 19) ,(5, 7), (5, 11), (5, 13), (5, 17), (5, 19)





Claim: If p and q are two distinct odd primes and a is an integer smaller than and relatively prime to p*q then:
 aphi(pq)/2 = 1 mod pq

In other words, phi(pq)/2 is a universal exponent when p and q are distinct odd primes

Proof: Follows from previous claim combined with the kinkier proof of the first claim on kinky primes