Why do remainders show cyclic pattern?

Question

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.

Answer 1

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}$$

Answer 2

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.

Answer 3

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.

Answer 4

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$.

Answer 5

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$

Answer 6

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.

Answer 7

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?