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)

Leave a Reply

Your email address will not be published. Required fields are marked *