18.2.16

Lonely Squares

Definition: Given two distinct odd primes p and q and an integer a < p*q such that GCD(a, p*q) = 1 and a2 = 1 mod p*q then a is a lonely square mod p*q.

Clearly, a = 1 is the most trivial example of a lonely square.

In Types of Exponents I showed that (p*q - 1)2 = 1 mod pq therefore a = (p*q - 1) is a lonely square mod p*q.


Claim: If 2 has order k mod p*q where p and q are distinct odd primes and k is an even integer then (2k/2) is a lonely square.

Proof:  Since k is the order of 2 then 2k= 1 mod p*q
Since k is an even integer then k/2 is also an integer and so:
(2k/2)2 mod p*q = (2(k/2)*2) mod p*q = 2mod p*q = 1 mod p*q

Example: Let p = 3, q = 7.
To find the order of 2 mod 21 using my favourite algorithm I first list all even integers < 21 followed by all odd integers < 21, (which is the second row of the multiplication table of Z21)

Then starting from index 1 I look up the value at that index, which is 2, then I look up the value at index 2, which is 4, then I look up the value at index 4, which is 8, then I look up the value at index 8, which is 16, then I look up the value at index 16, which is 11, then I look up the value at 11, which is 1, and this completes the cycle [a10,a11, a12, a13,..., a1k ], which is equivalent to [20,21, 22, 23,..., 26] or [1, 2, 4, 8, 16, 11, 1]  (which is the unique portion of the second row of the exponentiation table of Z21)

Note: I first discussed the basis for this algorithm here.

So k = 6, which is even and the value at k/2 is 8. It is clear to see that 82= 1 mod 21


Claim: If 2k/2 =  (p*q - 1) mod p*q where k is the order of 2 mod p*q and it is even and p, q > 2 then there is at least one other small prime b of order r where r is even such that b does not belong to the set [20,21, 22, 23,..., 2k] but  br/2  mod p*q is a lonely square.


Claim: If p, q > 2 then there are at least 4 lonely squares.


Claim: If ds mod p*q is a lonely square then there is another lonely square c where:

c = p*q - ds  



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