Why do remainders show cyclic pattern?

Let us find the remainders of $\dfrac{6^n}{7}$,

Remainder of $6^0/7 = 1$
Remainder of $6/7 = 6$
Remainder of $36/7 = 1$
Remainder of $216/7 = 6$
Remainder of $1296/7 = 1$

This pattern of $1,6,1,6...$ keeps on repeating. Why is it so? I'm asking in general, that is for every case of type $a^n/b$'s remainder keeps on repeating as we increase $n$.

P.S: This is a follow up question of my previous question.

• Start at Fermat's little theorem, then Euler's theorem. Jul 28, 2015 at 20:34
• The remainder (or more precisely modular arithmetic) commute with powers. So, what you're looking at is the image of the remainder in the multiplicative group mod $n$. A group generated by an element is a cyclic group and this is why the sequence of remainders is cyclic. Jul 28, 2015 at 20:36
• A related phenomenon is the eventually repeating decimal expansion of any rational number. Jul 28, 2015 at 20:38
• IMO using groups to explain this to someone who doesn't fully understand modular arithmetic is pretty overkill. Jul 28, 2015 at 20:46
• Note that $6$ is one less than $7$. So I'll call $6$ by the name $[-1]$ instead, to emphasize this. And I'll call your remainder $[1]$ instead of $1$. So, curiously, multiplying by $[-1]$ repeatedly bounces back and forth between $[1]$ and $[-1]$. Weird! Jul 28, 2015 at 20:47

First, let me address a simpler question: why is there a pattern to the remainders at all?

Suppose I have any positive integer $b$ (in your case $b=7$). Then remainders respect multiplication: if $x, x'$ are positive integers which yield the same remainder when divded by $b$, and $y, y'$ are positive integers which yield the same remainder when divded by $b$, then $xy$ and $x'y'$ yield the same remainder when divided by $b$.

This is modular arithmetic: for a positive integer $b$, we can develop arithmetic on the set $R_b=\{0, 1, 2, . . . , b-1\}$ by interpreting elements of $R_b$ as remainders. For instance, any time I multiply two even numbers I get an even number; this is represented as $$0\times 0=0 \quad \mbox{(in R_2)}.$$ Because remainders respect multiplication, this makes sense and works the way we want it to.

So what does this have to do with powers? Well, fix $b$, and consider the sequence $a, a^2, a^3, . . .$. Since $R_b$ is finite there are some $m<n$ such that $a^m$ and $a^n$ leave the same remainder when divided by $b$. Once this happens, the remainders will repeat: the remainder of $a^{n+1}$ when divided by $b$ will be the same as the remainder of $a^{m+1}$ when divided by $b$, etc. So the sequence of remainders of powers of some number will always be eventually repeating.

Note that "eventually" is crucial here: consider $a=3$, $b=27$. Then the sequence of remainders is $3, 9, 0, 0, 0, 0, . . .$. Similarly, if we take $a=2$ and $b=12$ we get $2, 4, 8, 4, 8, 4, 8, . . .$ This happens because $a$ and $b$ share prime factors. Euler's theorem says that if, by contrast, $a$ and $b$ are coprime (have no factors besides $1$ in common), then this pattern is just repeating, full stop, and in fact tells us how long it will take to repeat.

• What do you mean by respect in the phrase remainders respect multiplication? And why do remainders respect multiplication? Jul 29, 2015 at 14:44
• I mean exactly what follows: if $x, x'$ are positive integers which yield the same remainder when divded by $b$, and $y, y'$ are positive integers which yield the same remainder when divded by $b$, then $xy$ and $x'y'$ yield the same remainder when divided by $b$. As to why this is the case: suppose $x, x'$ yield remainder $r$, and $y, y'$ yield remainder $s$, when divided by $b$. Then we have $x=ib+r$, $x'=jb+r$, $y=kb+s, y'=lb+s$ for some integers $i, j, k, l$. Multiply out: we get $xy=(ikb+is+rk)b+rs$ and $x'y'=(jlb+js+lr)b+rs$. Do you see how to go from here? Jul 29, 2015 at 19:04
• Ok, since $x=a^m$ and $x'=a^n$ have same remainders and $y=a$ and $y'=a$ have same remainders, $xy=a^na$ and $x'y'=a^ma$ will also have same remainders. This process will continue for $a^na^2$ and $a^ma^2$ and so on. Jul 30, 2015 at 9:01
• From what I see is that all these answers boil down to Euclid division. Yves's answer relies on $a^na \pmod b = r_na \pmod b$ and if for some $m$, $a^m \pmod b = a^n \pmod b = r_n$ then $a^ma \pmod b = a^na \pmod b$ and this will cause repetition for $a^ma^2$,$a^ma^3$ and so on. But your method seems to be more general. Jul 30, 2015 at 9:14

The answer is $$6 = -1 \pmod 7.$$ Therefore, you have $(-1)^{n}$ and it depends only on $n$ and it $-1$ or $1$.

More detailed theory you can find following this link: Modular arithmetic

P.S. $number \pmod 7 = remainder$

• I have read wikipedea. They don't prove or at least explain nothing. Jul 28, 2015 at 20:48
• @user103816 Actually that article explains quite a few things, although it is true that it is quite hard to understand without a few basics. Still, keep in mind that the often best part of the mathematics articles on Wikipedia are actually the references. ;)
– A.P.
Jul 28, 2015 at 20:53
• @user103816 Wikipedia is an encyclopedia, not a text book. Their main goal is to record knowledge, not teach it. This is not a bad thing for the professor seeking information. It is often a bad thing for a student seeking help. Jul 29, 2015 at 1:52
• How is $6^n( \mod 7)= (-1)^n( \mod 7)$? Are you using binomial theorem for $6^n=(7-1)^n$, but this will give negative coefficients for $1^n$. We will have something like $(7-1)^n=7(T)-1^n$. What is the reminder of (-1)/7 and how can we prove that rem(a-b)/m = rem(a/m)+rem(-b/m)? Jul 29, 2015 at 7:37
• @StevenGregory & AlonzodelArte: Wikipedia is not a text book, but it's not an encyclopedia either! It's a drama board, maybe even an MMPORPG. Maybe you read the modular arithmetic article and decide it's not complete garbage, it just needs some little improvements. Next thing you know, you're sucked in, whining to ArbCom about banned users changing commas around. (I wish that example was fictional!) Jul 29, 2015 at 21:21

Note that as you find more and more powers, you'll eventually run out of remainders. So you'll come back to a previous number, and since exponentiation is repeated multiplication, you'll generate the cycle again. As an example, let's look at powers of $2$ modulo $7$. We have \begin{align*} 2^1 &\equiv 2 \pmod{7} \\ 2^2 &\equiv 2\cdot 2 \equiv 4 \pmod{7} \\ 2^3 &\equiv 4 \cdot 2 \equiv 1 \pmod{7} \\ 2^4 &\equiv 1 \cdot 2 \equiv 2 \pmod{7} \\ 2^5 &\equiv 2 \cdot 2 \equiv 4 \pmod{7} \\ 2^6 &\equiv 4 \cdot 2 \equiv 1 \pmod{7} \end{align*} Hopefully, this clarifies how multiplication works in modular arithmetic too.

• Which formula did you use? Are you using 8 (mod 7) = 1? Jul 28, 2015 at 20:47
• If $a \equiv x \pmod{m}$ and $b \equiv y \pmod{m}$, then $ab \equiv xy \pmod{m}$. That is, for example, since $2^5 \equiv 4 \pmod 7$ and $2 \equiv 2 \pmod 7$, we have $2^6 \equiv 2^5 \cdot 2 \equiv 4 \cdot 2 \equiv 8 \equiv 1 \pmod 7$. Jul 28, 2015 at 20:49
• Why are we running out of remainders? And I am still confused about how $ab \equiv xy \pmod{m}$. As you shown here $ab$ must be equal to $xy(\mod m)$ not equivalent to. And how in general we'd show that for every number $a$ and $b$ $a^n \over b$'s reminders will repeat? Jul 28, 2015 at 21:17
• Note that the only possible remainders are 0,1,2,3,4,5,6. So you'll eventually have to repeat one of them. This is a variant of the pigeonhole principle. Jul 28, 2015 at 23:56
• "since exponentiation is repeated multiplication": this is not enough as an explanation.
– user65203
Jul 29, 2015 at 10:08

The reason is simple: a remainder can be expressed as a function of the previous remainder alone.

Indeed, let $r_n=6^n\bmod 7$, i.e. $6^n=7q_n+r_n$.

Then $\color{blue}{r_{n+1}}=6^{n+1}\bmod 7=(6\cdot6^n)\bmod 7=(42q_n+6r_n)\bmod 7=\color{blue}{(6r_n)\bmod 7}.$

As there is a finite number of possible remainders, the sequence must be periodic.

\begin{align}1&&\to1\\6&\to6\cdot1&\to6\\36&\to6\cdot6&\to1\\216&\to6\cdot1&\to6\\1296&\to6\cdot6&\to1\\\cdots\end{align} or if you prefer \begin{align}1&\to1\\6\cdot1&\to6\\6\cdot6&\to1\\6\cdot1&\to6\\6\cdot6&\to1\\\cdots\end{align}

• I understood upto $r_{n+1}=(6r_n) \mod 7.$ But then you say "there is a finite number of possible remainders". Why are there only finite number of remainders. Jul 29, 2015 at 11:12
• $0,1,2,3,4,5,6$.
– user65203
Jul 29, 2015 at 11:22
• But why? ${}{}{}{}{}$ Jul 29, 2015 at 11:24
• Check the definition of the remainder.
– user65203
Jul 29, 2015 at 11:25
• Yes, every number is possible, but not required. A cycle can be shorter. Consider the extreme case of $7^n/7$.
– user65203
Jul 29, 2015 at 12:08

For me the most intuitive way to answer this question is to work modulo 7, so we are looking at powers of $-1$, which renders the alternating pattern familiar immediately. But perhaps you have never seen modulo arithmetic before. I tell a lie here: if you are used to the time 5 hours after 10 o'clock being 3 o'clock then you are already well familiar with modulo 12. But perhaps modulo 7 is less familiar to you. I tell a lie again: what is the day seven days after Monday? What is the day twenty-eight days after Monday? What is the day twenty-nine days after Monday? So perhaps you already know modulo 7 too, albeit you didn't realise it.

But I shall suggest a different way of looking at the problem, which is to write the number in a different base system. You are used to the number 437 base 10 being made of four hundreds i.e. $4 \times 10^2$, three tens i.e. $3 \times 10^1$ and seven units i.e. $7 \times 10^0$. To write numbers in base 10 we occupy those place-value columns for $10^0, \, 10^1, \, 10^2, \, \dots$ with digits between 0 and 9. If instead we work in base 7 we fill place-value columns for $7^0, \, 7^1, \, 7^2, \, \dots$ with digits from 0 to 6. So the number $251_7$ (the subscript is to inform us of the base) is

$$\color{red}{2}\color{blue}{5}\color{orange}{1}_7 = \color{red}{2} \times 7^2 + \color{blue}{5} \times 7^1 + \color{orange}{1} \times 7^0 = \color{red}{2} \times 49 + \color{blue}{5} \times 7 + \color{orange}{1} \times 1 = 134$$ when we work in base 10. To get a bit of familiarity with how the system works, let's do some counting in base 7: $0_7$, $1_7$, $2_7$, $3_7$, $4_7$, $5_7$, $6_7$, $10_7$, $11_7$, $12_7$, $13_7$, $14_7$, $15_7$, $16_7$, $20_7$, $21_7$, $22_7$, $23_7$, $24_7$, $25_7$, $26_7$, $30_7$ ... which gets us as far as the number we'd write as $3 \times 7 = 21$ when we are working in base 10.

Now here is the six times table, with answers in base 7, as far as $7 \times 6$. In fact we really only need to go as far as $6 \times 6$ to be able to do long multiplication base 7, for the same reason we only need to go up to $9 \times 9$ to do long multiplication in base 10: the highest digit we will encounter in base 7 is a "6", like the highest digit in base 10 is a "9".

$$\\0 \times 6 = 00 = 0 \times 7 + 0 = 00_7 \\1 \times 6 = 06 = 0 \times 7 + 6 = 06_7 \\2 \times 6 = 12 = 1 \times 7 + 5 = 15_7 \\3 \times 6 = 18 = 2 \times 7 + 4 = 24_7 \\4 \times 6 = 24 = 3 \times 7 + 3 = 33_7 \\5 \times 6 = 30 = 4 \times 7 + 2 = 42_7 \\6 \times 6 = 36 = 5 \times 7 + 1 = 51_7 \\7 \times 6 = 42 = 6 \times 7 + 0 = 60_7$$

Note how multiplying by 7 just appends a zero in base 7, the same as multiplying by 10 just appends a zero in base 10. The similarity is even more extreme when I point out that 7, when written in base 7, is simply $10_7$! And you may spot the pattern of digits increasing in one column and decreasing in the next resembles how the nine times table works when written in base 10: this pattern in the multiplication tables occurs because both numbers are one less than the base we are writing in. (We don't actually need the leading zeroes in 00 and 06 but I have put them there to help the alignment, and remind us that when we are doing long multiplication we need not carry anything to the next place-value column.)

We should now be able to perform long-multiplication by six while working in base 7! For instance let us try $251_7 \times 6_7$, which is equivalent to $134 \times 6$ when we work in base 10. The digit $1$, times $6$, makes $6$ with nothing to carry. The digit $5$, times $6$, makes $42_7$ so we need to write a $2$ and carry $4$. The digit $2$, times $6$, makes $15_7$ but we must add the four that we carried to get $22_7$. The final answer will be therefore be $2226_7$. We can check this in base 10: our answer is $2 \times 7^3 + 2 \times 7^2 + 2 \times 7^1 + 6 \times 7^0 = 804$, which is indeed $134 \times 6$.

A useful observation is that the final digit, base 7, is simply the remainder when our number is divided by 7. This works for the same reason that the final digit, base 10, is simply the remainder when our number is divided by 10. This is why I wanted to work base 7 in the first place: it makes it far easier to spot the remainders than when we worked base 10.

Since we can multiply by six in base 7, and we know how to spot the remainder when our number is divided by 7, we can now look at the remainders of the powers of six.

For starters there is ${6_7}^1 = 6_7$ which has remainder $6$.

Next comes ${6_7}^2= 6_7 \times 6_7 = 51_7$ which has remainder $1$.

Then we have ${6_7}^3= 6_7 \times 51_7 = 426_7$ which has remainder $6$ again.

One more for luck: ${6_7}^4= 6_7 \times 426_7 = 3531_7$ which reverts to remainder $1$.

Now if you were doing those long multiplications by hand, you'd have spotted that the final digit on each power of six only depended on the final digit of the previous power of six. This is why the remainders are in a cycle: if the final digit base 7 of $6^n$ is $6$ then the final digit of $6^{n+1}$ base 7 is $1$, and vice versa. Since the next final digit only depended on the previous final digit, and it was only the final digits I cared about (since they told me the remainder), I might as well only have bothered writing the final digits down: by doing so I would essentially be working modulo 7, like the other answers. But I thought I would show you how the question looks much more "obvious" if we switch the base of the number system we use to write the question in.

Here are some questions you should now be able to answer for yourself by considering multiplication base 10 (i.e. what you've already been used to). Can you see why the final digit of $21^n$ is always one, or the final digit of $65^n$ is always five, for positive integers $n$? Can you therefore see that the remainder of $21^n$, when divided by ten, is always one? Or that the remainder of $65^n$, when divided by ten, is always five? Or if you want to see a short cycle, can you see what happens to the remainder of $4^n$ when it is divided by ten?

• I stuck at 0*6=00=0*7 + 5.. Jul 29, 2015 at 12:20
• @user103816 You have spotted a typo! I introduced it when I copy-and-pasted... it should be fixed now. Jul 29, 2015 at 12:24
• How can we prove in general that in a number system with base $N$, the last digit of the number $(Tb\times ab)$ is same as that of $(b^2)$, $T$ and $a$ can be more than one digit. I tried $Tb \times ab = (TN+ b)(aN+b) = ....$ But lost. Jul 29, 2015 at 12:47
• @user103816 Good idea! Remember that any term with an $N$ or $N^2$ in it will have zero in the final place-value column when you write it in base $N$. (For instance, that $10_7$ is actually $7$, and that $100_7$ is actually $7^2 = 49$, perhaps a point I should have made more clear in my answer.) Jul 29, 2015 at 12:51
• Yeah got it. $Tb \times ab = N^2aT+N(Tb+ab)+b^2$. Since $T$'s will have 0 at last the final digit of $b^2$ will match with the final digit of $Tb \times ab$. Now how can we make the base switching argument more rigorous? We are kind of using binomial expansion method. $6^n=6 \times 6^{n-1}$ by breaking $6^{n-1}$ into $7q_n+r_n$. The underlying concept seems quite similar to Yves's answer. But how can we generelize it for, for example $a^n/b$ where $a>b$. Jul 29, 2015 at 13:01

Looking at remainders after division by 7 is called arithmetic modulo 7.

You are regarding powers of 6, modulo 7. But $6$ is $-1$, modulo $7$. This is written: $$6 \equiv -1 \pmod 7$$

But the powers of $-1$, that is the numbers $(-1)^n$, simply alternate: $1,-1,1,-1,1,\ldots$.

• why is 6 mod 7 = (-1)mod 7. I know that 6=(7-1), but why does modulo operation follow distributivity for negative numbers? Jul 29, 2015 at 11:31

Using your example, there are only $6$ possible remainders. I am excluding $0$ because $6^n$ will never be a multiple of $7$.

So you start with $6^0 = 1$.

Then $6^1 \equiv (6^0)\times 6 \equiv 1\times 6 \equiv 6 \pmod 7$

Then $6^2 \equiv (6^1)\times 6 \equiv 6\times 6 \equiv 1 \pmod 7$

And we are back to $1$ and we are now forced into a repeating pattern. Since there are only $6$ possible remainders, we are going to have to repeat a remainder by at most the $6$'th computation. From that point on, we must have a repeating pattern.