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