Mathematics, Number Theory

Numbers that are their own modular square root

In a previous post, I followed up on a method I described to obtain non-trivial modular square roots to show something that followed from the proof of that method was that certain numbers could be shown to be their own modular square roots. In particular, what I showed was that if m is an odd integer greater than 2, and d and e are coprime divisors of m such that de = m, and both d and e are greater than 1 and less than m, then the the product of d and the multiplicative modular inverse of d, mod e, is its own square root, mod m. To be more precise, given these constraints:

m = de
2 ∤ m
1 < d < m
1 < e < m
gcd(d, e) = 1
i ≡ d-1 (mod e)

then this is true:

d2i2di (mod m)

I showed this by deriving it from this congruence when x = 1:

2idx(2idx – 2x) ≡ 0 (mod m)

However, there is a more straightforward way to show that di is its own modular square root, mod m, and it doesn’t rely on m not being divisible by 2.

Let’s start with this congruence, which we know to be true from the reflexive rule:

ii (mod e)

Now if we multiply the left hand side by di, which we can do because i is the inverse of d, mod e, and thus their product is 1, we get this:

di2i (mod e)

Now because gcd(d, e) = 1, we can multiply both sides by d as well as the modulus, which gives us this:

d2i2di (mod de)

Of course, m = de, so we can now convert the modulus to m:

d2i2di (mod m)

It turns out we can also lift the restriction that d and e are greater than 1 and less than m. Because gcd(m, 1) = 1, we can also apply this to the case when d = 1 and e = m, and vice versa. It turns out these cases give us di ≡ 1 and di ≡ 0, mod m, respectively, which are clearly their own square roots, even when m is prime.

Mathematics, Number Theory

Wilson’s Theorem

Wilson’s Theorem states that for an integer, n, where n is greater than 1, the product of the positive integers less than n is congruent with -1, mod n, if and only if n is a prime. The theorem is often stated like so:

(n – 1)! ≡ -1 (mod n)

The case when n is compound is easiest to prove. If n is compound then either n is the product of two unequal integers greater than 1 and less than n, or else n is the square of a prime integer.

It is clearly true that if n has more than one distinct prime factor that n is the product of two unequal integers greater than 1 and less than n, since if n has the prime factors p and q then n is the product of p and n/p, and n/p cannot be equal to p since n/p must be divisible by q. Likewise, if n is the power of a prime integer, p, with exponent e, and e is greater than 2, then n is the product of p and pe – 1, which are unequal because e > 2 and therefore e – 1 > 1.

If n is the product of two unequal integers greater than 1 and less than n, which we can call a and b, then both of those integers will occur in the sequence of positive integers less than n. Therefore, (n – 1)! will be product of a and b and the remaining positive integers less than n. Because n is the product of a and b, n must divide (n – 1)!, from which we can conclude that (n – 1)! ≡ 0 (mod n) in this case.

If n is the square of a prime integer, p, then either p is 2 and n is 4, in which case (4 – 1)! ≡ 2 (mod 4), or else 2p < p2, which means that 2, p and 2p will occur in the sequence of positive integers less than n. Therefore, 2p2 will divide (n – 1)!, from which we can conclude that with the exception of when n is 4, (n – 1)! ≡ 0 (mod n) in this case.

The case of when n is prime is also fairly simple to prove using Legrange’s Theorem which states that if p is a prime integer and f(x) is a polynomial with integer coefficients, then either every coefficient of f(x) is divisible by p, or else f(x) ≡ 0, mod p, has at most deg f(x) incongruent solutions.

Lagrange’s Theorem is relevant because we can use it to show that there are exactly two quadratic roots of 1, mod n, when n is prime. It is perhaps not clear why that’s relevant but I’ll get to that. If it’s not obvious why Lagrange’s Theorem means that there are exactly two quadratic roots of 1, mod n, I’ll explain. If a is a quadratic root of 1, mod n, a will satisfy this congruence:

a2 ≡ 1 (mod n)

We can subtract 1 from both sides which gives us this:

a2 – 1 ≡ 0 (mod n)

Now we can use Legrange’s Theorem to known that there can be at most 2 solutions to this congruence, given that n is a prime integer. Since we know that 12 is congruent with 1, mod n, and that -12 is congruent with 1, mod n, and n is prime, Legrange’s Theorem allows us to be certain that these are the only two quadratic roots of 1, mod n.

It happens that given a positive integer, m, the quadratic roots of 1, mod m, are exactly those integers that are congruent with their own modular multiplicative inverses, mod m. A modular multiplicative inverse of an integer, a, relatively prime to m, is defined such that the product of a and its inverse is congruent with 1, mod m. Furthermore, a can only have an inverse, mod m, if it is relatively prime to m. Given that the square of a is 1, mod m, we can conclude both that a is relatively prime to m and that a is its own inverse.

Another way of thinking about this is that if we start with this:

a2 ≡ 1 (mod m)

And then we multiply both sides of the congruence by the modular multiplicative inverse of a, mod m, we get this:

aa-1 (mod m)

So now we know, because of Legrange’s Theorem, that when n is a prime integer, only the integers congruent with 1 and -1, mod n, have inverses congruent with themselves, mod n. Let’s look now at why it is important to the proof of Wilson’s Theorem. First, while -1 is not in the set of positive integers less than n, n – 1 is in the set of positive integers less than n and n – 1 is congruent with -1, mod n.

If we examine the set of positive integers less than n, given that in this case n is a prime integer, all the positive numbers less than n are relatively prime to n and therefore each has an modular multiplicative inverse, mod n. Because the set of positive integers less than n represents exactly the reduced residue system, mod n, all of the positive integers less than n which are not congruent with their own inverse, mod n, are paired with exactly one other integer in the same set. Because the product of an integer and its inverse is 1, mod n, the product of all of these pairs is 1. Therefore, the product of all the positive integers less than n is congruent with the product of the two integers which are not paired with their inverse because they are congruent with their own inverse, those integers being 1 and n – 1. The product of these two integers is n – 1, which is congruent with -1, mod n. Thus for the case when n is prime:

(n – 1)! ≡ 1 * (n – 1) = n – 1 ≡ -1 (mod n)

Mathematics, Number Theory

Sum of powers modulo a prime

In number theory, if n is a positive integer and a is a an integer relatively prime to n, we say that the order of a with respect to n is the smallest positive integer, k, where:

ak ≡ 1 (mod n)

It is interesting to note that the order of a with respect to n divides φ(n), where φ is Euler’s Totient Function. This is because each element in the sequence of positive powers of a, mod n, is completely dependent on the previous element, except the first, which must be a. The residues, mod n, which are in this sequence must repeat with a period of k. Euler’s Theorem shows that:

aφ(n) ≡ 1 (mod n)

Therefore, φ(n) must be a multiple of k.

Here’s a fun fact: If p is an odd prime integer, and a is an integer relatively prime to p, and k is the order of a with respect to p, and k is greater than 1, the sum of the first k powers of a is congruent with 0, mod p. We can represent this statement like so:

\sum_{i=1}^{k}a^i \equiv 0 \pmod{p}

Let’s examine why this is true. First, let’s consider the case where k is even. It turns out this case is really easy to show. Because k is even, we know that k/2 is an integer. Let’s define j = k/2. Therefore:

ak = aj*aj ≡ 1 (mod p)

Thus, aj is the modular square root of 1, mod p. Because p is prime, then by Legrange’s Theorem, we know that each quadratic residue of p has at most 2 modular square roots. The modular square roots of 1, mod a prime integer, are those integers congruent with 1 and -1, mod that prime integer. We know that aj cannot be congruent with 1, mod p, because if that were true, then k would not be the least positive integer such that ak is congruent with 1, mod p. Since we defined k to be the order of a with respect to p we can conclude that:

aj ≡ -1 (mod p)

Let’s take a look at what that means for the elements of the sequence of powers of a from 1 to k. Let A represent this sequence such that A = {a, a2, …, ak-1, ak}. Now let B be the first half of the sequence A, and let C be the second half of the sequence A. There are exactly j positive powers of a in the sequence B = {a1, a2, …, aj} and there are also j positive powers of a in the sequence {aj+1, aj+2, …, ak}. From this it should be clear that the sum of the elements in B is:

\sum_{i=1}^{j}a^i

and that the sum of the elements in C is:

\sum_{i=j+1}^{k}a^i

and because A is the union of these two sequences:

\sum_{i=1}^{k}a^i = \sum_{i=1}^{j}a^i + \sum_{i=j+1}^{k}a^i

Because aj is congruent with -1, mod p, and aj+1 is the product of a and aj, aj+1 must be congruent with –a. And because aj+1 is congruent with –a, and aj+2 is the product of a and aj+1, aj+2 is congruent with -(a2). We can continue in this way to conclude that all positive powers of a are congruent with -1 times the same power of a plus j, mod p. Put another way, if i is a positive integer, then:

ai+j = ai*aj

and because:

aj ≡ -1 (mod p)

it follows that:

ai+jai * -1 (mod p)

Now let’s look again at the sum of the elements of C. We said that the sum of the elements of C was this:

\sum_{i=j+1}^{k}a^i

Each element of C is a power of a greater than j. We can, therefore, factor out aj from each element in C so that the sum of the elements in C becomes this:

a^j * \sum_{i=1}^{j}a^i

We have now expressed the sum of the elements of C in terms of the sum of the elements in B. And because aj is congruent with -1, mod p, we can now say this about the sum of the elements in C:

a^j * \sum_{i=1}^{j}a^i \equiv -1 * \sum_{i=1}^{j}a^i \pmod{p}

Now if we substitute this for the sum of the elements of C in the equation for the sum of the elements in A, we get this:

\sum_{i=1}^{k}a^i \equiv \sum_{i=1}^{j}a^i - \sum_{i=1}^{j}a^i \equiv 0 \pmod{p}

We have now shown that the sum of the sequence of powers of a from 1 to the order of a with respect to p is congruent with 0, mod p, when the order of a is even. We have not yet discussed the case when the order of a is odd.

Note that we made a special exception for when the order of a is 1. When the order of a with respect to p is 1, the sum is 1, not 0. Only numbers congruent with 1, mod p, have order 1. No integer congruent with 1, mod another integer, is congruent with 0, mod that same other integer, except in the special case when the modulus is 1. However, we have specified that the modulus is a prime, and 1 is not prime. No integer can be congruent with 1, mod a prime, and also be congruent with 0, mod that same prime.

So let’s consider the case when the order of a is odd and greater than 1.

First, notice that we don’t need to consider any primes smaller than 7 since we defined p to be an odd prime which means it cannot be 2, and the totient of 3 is 2 and the totient of 5 is 4 and neither 2 nor 4 are divisible by odd integers greater than 1.

Next, notice that all prime numbers greater than 2 are odd and the totient of any odd prime number is an even number because:

p ≡ 1 (mod 2)

therefore:

φ(p) = p – 1 ≡ 1 – 1 ≡ 0 (mod 2)

Now, considering when p is an odd prime integer, because the totient of p is even, if k, being the order of a with respect to p, is odd, it must be the case that 2k divides φ(p).

Furthermore, though I won’t attempt to show that this is the case here, it is well known that for any divisor, d, of φ(p), where p is a prime integer, there are exactly φ(d) positive integers less than p and relatively prime to p that have order d with respect to p. Therefore, there must be φ(k) positive integers less than p and relatively prime to p with order k and φ(2k) positive integers less than p and relatively prime to p with order 2k. But because Euler’s totient function is multiplicative and 2 does not divide k and so 2 is relatively prime to k, φ(k) is equal to φ(2k), because φ(2) is 1 and φ(2k) = φ(2) * φ(k). Therefore, there are as many positive integers relatively prime to p and less than p having the order 2k with respect to p as there are having the order k with respect to p.

For the remainder of the discussion, I will redefine a to be an integer relatively prime to p and less than p having the order 2k with respect to p, where k is an odd integer. Given this, a2 has order k. This is easy to show. First, let’s re-state what we know about a:

a2k ≡ 1 (mod p)

And now let’s see what happens when we raise a2 to the k power. First, we have this:

(a2)k

Using the power rule, we can multiply the exponents, giving us 2k and we already know that a2k is congruent with 1, mod p:

(a2)k = a2k ≡ 1 (mod p)

This shows that the order of a2 is at most k, but can it be less? It cannot. All of the powers of a2 are even powers of a, meaning if i is a positive integer less than or equal to k, (a2)i = a2i, again by the power rule. That means that if the order of a2 is less than k, the order of a would have to be less than 2k. Therefore, the order of a2 is k.

Now we must show the following:

\sum_{i=1}^{k}a^{2i} \equiv 0 \pmod{p}

You will see why in a moment, but let’s briefly examine which of the values of 2i are less than k+1 and which are greater than or equal to k+1 as i goes from 1 to k. 2i is equal to k+1 when i is equal to (k+1)/2. k is odd, so k+1 is even and so (k+1)/2 is an integer. Therefore, for values of i less than (k+1)/2, 2i will be less than k+1 and for values of i greater than or equal to (k+1)/2, 2i will be greater than or equal to k+1. We can now rewrite the congruence of the sum of powers of a2:

\sum_{i=1}^{k}a^{2i} = \sum_{i=1}^{(k-1)/2}a^{2i} + \sum_{i=(k+1)/2}^{k}a^{2i}

This is important because as we have already found, the numbers in the second half of the sequence of powers of a from 1 to 2k are congruent with the negation of the numbers in the first half of that sequence with an offset of k. Therefore, for each of the powers of a2 from (k+1)/2 to 2k, we can reduce the power of that element by k and multiply by -1 when evaluating the sum. We can now rewrite the above statement as a congruence:

\sum_{i=1}^{(k-1)/2}a^{2i} + \sum_{i=(k+1)/2}^{k}a^{2i} \equiv \sum_{i=1}^{(k-1)/2}a^{2i} - \sum_{i=(k+1)/2}^{k}a^{2i-k} \pmod{p}

We can simplify the second term on the right hand side of this congruence:

\sum_{i=(k+1)/2}^{k}a^{2i-k} = \sum_{i=1}^{(k+1)/2}a^{2i-1}

This gives us:

\sum_{i=1}^{(k-1)/2}a^{2i} + \sum_{i=(k+1)/2}^{k}a^{2i} \equiv \sum_{i=1}^{(k-1)/2}a^{2i} - \sum_{i=1}^{(k+1)/2}a^{2i-1} \pmod{p}

What this shows us is that the sum of first k powers of a2 is congruent with the sum of the first k powers of a, mod p, except that the odd powers are subtracted rather than added. In case this isn’t clear, let’s briefly look at the case when k is 5 and 2k is 10. The sum of the first 10 powers of a is:

a + a2 + a3 + a4 + a5 + a6 + a7 + a8 + a9 + a10

And the sum of the first 5 powers of a2 is:

a2 + a4 + a6 + a8 + a10

But because a6 ≡ –a and a8 ≡ -(a3) and a10 ≡ -(a5), mod p, we can do this:

a2 + a4 + a6 + a8 + a10 ≡ –a + a2a3 + a4a5 (mod p)

So you can see that the sum of first 5 powers of a2 is congruent with the sum of the first 5 powers of a, mod p, but with the odd powers of a within that range negated.

Because -1 raised to an odd power is -1 and -1 raised to an even power is 1, we can restate the sum of the first k powers of a2 like this:

\sum_{i=1}^{k}a^{2i} \equiv \sum_{i=1}^{k}(-1)^i*a^i \pmod{p}

Let’s look now if we shift the range of powers up by 1, meaning rather than summing the first k powers of a with odd powers negated, we will sum the k powers of a from a2 to ak+1. Because ak+1 is congruent with –a, and because k+1 is even, we will wind up removing the subtraction of a at the beginning but we will at the same time be adding –a at the end. The result is that the sum of this sequence is also congruent the sum of the first k powers of a2. We can continue increasing both the start and ending sequence positions as many times as we wish and the sum will always be congruent with the sum of the first k powers of a2, mod p. Therefore, if n is a non-negative integer:

\sum_{i=1}^{k}a^{2i} \equiv \sum_{i=n+1}^{n+k}(-1)^i*a^i \pmod{p}

Let’s consider specifically the case when n = k. When n = k, we have this:

\sum_{i=1}^{k}a^{2i} \equiv \sum_{i=k+1}^{2k}(-1)^i*a^i \pmod{p}

But remember, again, that ak+x is congruent with -(ax), mod p, where x is a positive integer. Therefore:

\sum_{i=k+1}^{2k}(-1)^i*a^i \equiv \sum_{i=1}^{k}(-1)*(-1)^i*a^i \pmod{p}

We can factor out the -1 from the terms in the sum on the right hand side of this congruence which gives us this:

\sum_{i=k+1}^{2k}(-1)^i*a^i \equiv -\sum_{i=1}^{k}(-1)^i*a^i \pmod{p}

Now if we define h to be:

h = \sum_{i=1}^{k}(-1)^i*a^i

We can combine the two congruences we have for the sum of the first k powers of a2:

\sum_{i=1}^{k}a^{2i} \equiv h \equiv -h \pmod{p}

Let’s examine this congruence:

h ≡ -h (mod p)

We can add h to both sides which gives us this:

2h ≡ 0 (mod p)

And now because we know that p is not divisible by 2, we can divide both sides of the congruence by 2:

h ≡ 0 (mod p)

Therefore:

\sum_{i=1}^{k}a^{2i} \equiv 0 \pmod{p}

Now let’s look at a concrete example where p is the prime integer 191, and a is 7. The order of 7 with respect to 191 is 10 and the order of 72 = 49 with respect to 191 is 5. The sum of first 10 powers of 7, mod 191, is:

7 + 49 + 152 + 109 + 190 + 184 + 142 + 39 + 82 + 1 ≡ 0 (mod 191)

Notice that the second half of the sequence of the first 10 powers of 7, mod 191, are the negated values of the first half in the same order, because 184 = 191 – 7, 142 = 191 – 49, 39 = 191 – 152, 82 = 191 – 109, and 1 = 191 – 190. Also notice that the 5th element of the sequence is 190, which is congruent with -1, mod 191. We can rewrite the sum of the first 10 powers of 7, mod 191, like this:

7 + 49 + 152 + 109 + 190 – 7 – 49 – 152 – 109 – 190 ≡ 0 (mod 191)

The sum of the first 5 powers of 49, mod 191, is:

49 + 109 + 184 + 39 + 1 ≡ 0 (mod 191)

If you compare this to the sequence of the first 10 powers of 7, mod 191, you will see that the first 5 powers of 49, mod 191, are the same as the 2nd, 4th, 6th, 8th, and 10th powers of 7, mod 191. The 6th, 8th, and 10th powers 7 of, mod 191, are the negated values of the 1st, 3rd, and 5th powers of 7, mod 191, so we can rewrite this congruence like so:

49 + 109 – 7 – 152 – 190 ≡ 0 (mod 191)

Or, if you want to see an expression that is truly amazing:

74 – 73 + 72 – 71 + 70 ≡ 0 (mod 191)

Mathematics, Number Theory

Modular square roots of compound integers revisited

In my last post, I described a method for finding the non-trivial modular square roots for a compound modulus.

I would like to follow up with a very interesting result which follows from that discussion. For review, we had a compound integer, m, with at least 2 distinct prime factors, and we said that d was an integer divisor of m greater than 1 and less than m, and e was equal to m/d, and that d and e were coprime. In summary we have:

m = de
d | m
e | m
1 < d < m
1 < e < m
gcd(d, e) = 1

We then defined id-1 (mod e) and this was used to show that:

yx – 2idx (mod m)

where y is a non-trivial solution to the congruence:

y2x2 (mod m)

Part of the proof focused on the statement that:

2idx(2idx – 2x) ≡ 0 (mod m)

Let’s take a look a little closer at this because it leads directly to the observation I want to make here. If we multiply out the terms on the left, we get this:

4i2d2x2 – 4idx2 ≡ 0 (mod m)

If we add 4idx2 to both sides, we get this:

4i2d2x2 ≡ 4idx2 (mod m)

If we now introduce an additional constraint that m is not divisible by 2 which implies that neither d nor e are divisible by 2, and we assign 1 to x, we can divide both sides of the congruence by 4 since 4 divides both sides evenly but not m, and we can remove the x2 from both sides because those evaluate to 1. This gives us:

i2d2id (mod m)

Notice now that id is its own square-root, mod m. It is trivial to find numbers which are their own square root because this is true of 0 and 1 not just in modular systems but in the set of Integers and the set of Real numbers as well.

However, id can be congruent with neither 0 nor 1, mod m. Because d is a divisor of m and greater than 1 and less than m and e = m/d, id can only be congruent with 0, mod m, if i is a multiple of e. But because i is the modular multiplicative inverse of d, mod e, i must not a multiple of e. Therefore, id is not congruent with 0, mod m.

If i could be the multiplicative inverse of d, mod m, then it would be possible for id to be congruent with 1, mod m. However, because d evenly divides m and is greater than 1, gcd(d, m) = d, therefore d does not have an multiplicative inverse, mod m, and id is not congruent with 1, mod m.

Therefore, id non-trivially has the property that it is its own square root, mod m. Of course, by the same reasoning, if j is the modular multiplicative inverse of e, mod d, then je also non-trivially has this property as well.