4.9.16

A Square of A Square

In my Recurring Oddities entry I talked about a recurrence relation where each subsequent term was equal to the previous term plus an odd integer, which I calculated using the index of the previous term and I claimed that this recurrence relation generates the sequence formed by squaring integers consecutively:

1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225,... [A000290]

9 = 4 + (2*(3-1) + 1)
16 = 9 + (2*(4-1) + 1)
25 = 16 + (2*(5-1) + 1)
.
.
.

Claim: If a2 = 4 then ai = ai-1 + (2*(i-1) + 1) where i > 2 generates the sequence formed by squaring integers consecutively.

Proof: Although I never proved this when I first made this claim, the proof of this is very simple and it involves basic algebra.

Since ai = n2 , ai-1 = (n-1)2 , and (i-1) = (n-1), the ai = ai-1 + (2*(i-1) + 1) recurrence relation becomes:
n2 = (n-1)2 + (2*(n-1) + 1)
     = (n2 - 2*n + 1) + (2*n - 2 + 1)
     = n2 - 2*n + 2*n - 2 + 2
     = n
     .'.

I used this recurrence relation to find the smallest square root of ((n+1)/2)2 mod n, which I then used to find lonely squares, or integers k such that k2 = 1 mod n where n is the product of distinct primes because I claimed a lonely square is just 2 times the smallest square root of ((n+1)/2)2 mod n.



There are also another type of interesting integers, which I endearingly call foursome squares.

Definition: A foursome square is an integer k such that  k2 = 4 mod n

Example: Let n = 35, then k = 23 since 232 = 4 mod 35 but also 122 = 4 mod 35 and also 22 = 4 mod 35 and 332 = 4 mod 35

Claim: If n is the product of 2 distinct odd primes and k is a foursome square, then k*((n+1)/2) mod n is a lonely square.