Primes & Modulo

What I have observed is that for the following expression, choose a positive integer $m$, and if it is prime then for positive integers $n=1,2,3,\ldots$ the results will be $0,1,1,1,\ldots$ such that the sequence is made of $0$'s and $1$'s which repeat in a way that there is a $0$, then $(m-1)$ $\times$ $1$'s and then again $0$ and $1$'s...

$$\sum^{m-1}_{k=0} n^k\mod{m}$$

For $m=2$ we have for $n=1,2,3,\ldots$ following results: $0,1,0,1,0,1,0,1,0,1,\ldots$
For $m=3$ we have: $0,1,1,0,1,1,0,1,1,0,1,1,\ldots$
For $m=5$ we have: $0,1,1,1,1,0,1,1,1,1,0,1,\ldots$

And for non-prime numbers we get a specific mix of repeating numbers that repeat every $m$ numbers, for example:

$m=6$, We get a repeating sets of $0,3,4,3,0,1$
$m=8$, We have: $0,7,0,5,0,3,0,1$

I have accidentally stumbled upon this property, in fact I don't know if its 100% true since I've checked a handful of numbers only.


Is there an explanation for this property, why does it work for prime numbers like that?

Is there any significance or any kind of a pattern in numbers that appear for non-prime numbers?

Is there any significance to this expression, and does this expression or something similar appear somewhere in mathematics? In a specific field, equations, theorems... somewhere in the mathematical history... or simply mentioned somewhere else before?

  • $\begingroup$ The $0$ terms are probably obvious, since $p^m\equiv 0\pmod p$... $\endgroup$
    – abiessu
    Apr 10 '16 at 16:06
  • 2
    $\begingroup$ That they repeat (at least) every $m$ numbers is a consequence of modular arithmetic: If $u \equiv v \mod m$, then $\sum_{k=0}^{m-1} u^k \equiv \sum_{k=0}^{m-1} v^k \mod m$. That they are $1$'s for prime $m$ and for $n \nmid m$ follows from the geometric series formula $\sum_{k=0}^{m-1} n^k = \dfrac{1-n^m}{1-n}$ and Fermat's little theorem (which says that $n^m \equiv n \mod m$). (You need to argue that $1-n$ is coprime to $m$ and thus can be cancelled.) $\endgroup$ Apr 10 '16 at 16:08

The sum of the power series can be written as:

$$\sum_{k=0}^{m-1} n^k = \frac{n^m-1}{n-1}$$

You then need to know the result:

When $m$ prime and $n$ an integer, $n^m-n$ is divisible by $m$.

So if $n-1$ is not divisible by $m$, then $\frac{n^m-1}{n-1} = \frac{n^m-n}{n-1} + 1\equiv 1\pmod {m}$.

When $n-1$ is divisible by $m$, then $n^k-1$ is divisible by $m$ for all $k$, and thus $$\sum_{k=0}^{m-1} n^k\equiv \sum_{k=0}^{m-1} (n^k-1) \equiv 0\pmod {m}$$

  • $\begingroup$ $n=1$ is covered by the case where $n-1$ is divisible by $m$. @user254665 $\endgroup$ Apr 10 '16 at 17:25
  • $\begingroup$ I mean for the sum of the power series. I'm just nit-picking. $\endgroup$ Apr 10 '16 at 17:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.