How can one prove a recognized modulo pattern?

Suppose you need to know what the possible unit digits are for integers written on the form $$4n^2$$ for some integer $$n$$. Me myself have always just relayed on numerical investigation, i.e. compute the answer for the first few values of $$n$$ and assume that the observed pattern (if found) goes on for ever. For example.

The first few values of $$4n^2$$:

$$[4, 16, 36, 64, 100, 144, 196, 256, 324, 400]$$

Computing modulo $$10$$ of above numbers yields:

$$[4, 6, 6, 4, 0, 4, 6, 6, 4, 0]$$

And so I would just assume that the unit digit follow the pattern $$(4, 6, 6, 4, 0,...)$$ and deduce that the only possible unit digit values are $$0,4,6$$. But so far this is just an observation and one must prove that this pattern goes on forever if one is to be certain that the only unit digits possible are indeed $$0,4,6$$. How can you prove this or rather, what is the general approach for proving that patterns recognized modulo $$m$$ repeats to infinity? That is, don't get stuck on the fact that we are talking unit digits above. Another example would be $$n^2 (mod 8)$$ which gives the recognizeable pattern to prove:

$$[1, 4, 1, 0, 1, 4, 1, 0, 1, 4, 1, 0, 1, 4]$$

So to clarify, what I'm asking is: Do there exist a general approach or some tricks that are commonly used to prove that such modulo patterns continue forever? Or is it very "case specific" depending on the expression that you are working with, whereas sometimes you have to factor and other times use famous theorems etc.? Thanks.

• You can use what you know about modular arithmetic to show that if $x\equiv y\pmod{n}$ then $f(x)\equiv f(y)\pmod{n}$ for any polynomial $f$. It follows then that the pattern repeats as you suspect. – JMoravitz Aug 7 '19 at 15:32
• $4(n+5)^2=4n^2+40n+100\equiv4n^2\pmod{10}$ and $(n+4)^2=n^2+8n+16\equiv n^2\pmod 8$ – J. W. Tanner Aug 7 '19 at 15:35
• polynomial remainder theorem ? – user645636 Aug 7 '19 at 15:44
• @JMoravitz No, it doesn't follow from that since the period may be smaller than the modulus $\,n,\,$ e,g. it is $\,n/2\,$ in both of the the OP's examples. – Bill Dubuque Aug 7 '19 at 16:15

3 Answers

Let's assume that you have found the length of the recurring pattern to be $$r$$. Then you want to show that $$f(n+r) \equiv f(n) \pmod {m}$$

For example, in the case of $$f(n) = 4n^2, m = 10, r = 5$$, you want to show that $$4(n+5)^2 \equiv 4n^2 \pmod {10}$$ This can easily be seen by expanding the square to get $$4n^2+40n+100 \equiv 4n^2 \pmod {10}$$

Well, there must be a pattern and it must a length of at most $$10$$ because:

$$n = 10a + k$$ for some integer $$a$$ and $$0\le k < 10$$

So $$4n^2 = 4(100a + 20ak + k^2) =400a + 80ak + k^2 =10(40a + 8ak) + k^2$$.

So this will always be the last digit of $$k^2$$ and the values of $$k$$ repeat every ten integers.

Now notice if if $$j = 10-k$$ then $$j^2 = (10 -k)^2 = 100 - 20k + k^2=10(10-2k) + k^2$$ so $$j^2$$ will have the same last digit as $$k$$ so $$1^2$$ and $$9^2$$ have the same last digit and $$2^2$$ and $$8^2$$ will have the same last digit and so on.

At this point we can just do it, I suppose.

But we have shown the pattern will be (if we include $$4*0^2\pmod {10}$$ in the beginning) will be some $$(a,b,c,d,e,f,e,d,c,b)$$ (where it goes forward and then reverses). And that's what $$n^2\pmod {10}$$ does $$\{0,1,4,9,6,5,6,9,4,1\}$$.

But you saw $$4n^2$$ has a smaller reverse pattern: $$(0abba0abba0abba0 etc.)$$. I'm curious why that would be when we multiply by $$4$$?

Well. Consider $$j = 5-k$$. Then $$j^2=(5-k)^2 = 25-10k +k^2$$ and so the the last digit of $$j^2$$ will be the same as $$k^2$$ plus or minus $$5$$.

So we get the up-down pattern of (starting with $$0$$) $$(a,b,c,c\pm 5,b\pm 5,a\pm 5, b\pm 5,c\pm 5,c,b)$$.

And well we multiply by $$4$$, then as $$j^2 \equiv k^2 \pm 5\pmod {10}$$ then $$4j^2 \equiv 4k^2 \pm 20 \pmod {10}$$ and they will have the same last digit. Also if $$j= (5-k)$$ and the last digit of $$j^2 = 25-20k + k^2$$ has the same last digit plus or minus $$5$$... then multiplying by $$4$$ will give us $$4j^2 = 100-80 + k^2$$ and we'll have the same last digit.

So that is why we have the pattern $$(a,b,c,c,b)$$ repeated over and over.

As for the exact values. we have

$$4*0^2 = 4*0= 0$$.

$$4*1^2 = 4*1=0$$

$$2^2 = 4*4=16\equiv 6$$ and that's it. That's enough to get the rest.

$$4*3^2 = 4*(5-2)^2=4*(25-20 +2^2)\equiv 4(5+ 2^2)\equiv 20+ 4*2^2\equiv 4*2^2 \equiv 6$$.

$$4*(4^2)=4*(5-1)^2=4*(25-10+1^2)\equiv 4(5+1^2)\equiv 4*1^2$$

$$4*(5^2)=4*(5-0)^2 = 4*(25-0*10+0^2)\equiv 4(5+0^2)\equiv 4*0^2$$.

.... and so on.....

If $$n = 10k + a$$ and $$a=0,1,2$$ we will get

$$4*n^2 = 4*(10k + a)^2 = 4*(100k^2 + 20ka + a^2) =400k^2+80ka + 4a^2\equiv 4a^2$$.

If $$a=3,4,5$$ then $$a=5-b$$ where $$b=2,1,0$$.

And $$4*n^2 = 4(10k +(5-b))^2 =4*(100k + 20(5-b)k + 25-10b + b^2)=400k+80(5-b)k + 100 -40b + 4b^2\equiv 4b^2$$.

If $$a = 6,7$$ then $$a= 5+b$$ where $$b = 1,2$$ so

$$4n^2 = 4(10k + (5+b))^2 = 4*(100k + 20(5+b)k + 25 +10b + b^2) = 400k + 80(5+b)k + 100 + 40b +4b^2\equiv 4b^2$$

And if $$a = 8,9$$ the $$a = 10-b$$ where $$b=2,1$$ so

$$4n^2 = 4(10k + (10-b))^2 = 4*(100k + 20(10-b)k + 100 -20b+b^2)\equiv 4*b^2$$.

......

And that is why the pattern is $$0,4,6,$$ and then repeats itself down and up and down again.

Okay, that was very wordy and abstract but I hope it showed how to think about these things abstractly.

• I find the first four rows especially interesting because it gave such a clear picture to why the pattern must reapeat. Since you seem familiar with the topic I would like to ask another more general question: Is every sequence where the n:th term can be expressed in closed form bound to have a modulo m pattern? Or what are the conditions that must be satisfied if there is to exist a modulo m pattern for a given sequence? – Hassebae Aug 8 '19 at 16:32
• I'm not sure I understand your question. But if you are doing any basic arithmetic operation (except division) or combination say $f(n) = 5n^5 + 7n+3$ for example. Then if we look at the remainder after dividing by $m$ we will have $f(n + m)\equiv f(n)\pmod m$ and yes we will get a repeating pattern $m$ long. – fleablood Aug 8 '19 at 16:58
• Even tho you didn't understand the question, your answer made me realize. Thank you very much. – Hassebae Aug 8 '19 at 20:07

Just as you and some of the commenters have mentioned, the easiest way to deduce a pattern is to use the general formula $$x \equiv y (\mod m)$$. Once you've chosen an integer $$m$$ and written this modulo equation for the first term of your sequence, you calculate the units digit for subsequent terms using this equation.

Let's say you choose $$m = 10$$. Then for $$n = 1$$, $$4n^2 = 4$$, and $$4 \equiv 4 (\mod 10)$$. Then for $$n = 2$$, the equation gets multiplied by $$4$$, the right hand side becomes $$16 (\mod 10) \equiv 6 (\mod 10)$$. For $$n = 3$$, you'd get $$36 (\mod 10) \equiv 6 (\mod 10)$$. For $$n = 4$$, you'd get $$64 (\mod 10) \equiv 4 (\mod 10)$$. For $$n = 5$$, you'd get $$100 (\mod 10) \equiv 0 (\mod 10)$$. For $$n = 6$$, you'd get $$4 \times 36 (\mod 10) \equiv 4 (\mod 10)$$, at which point the whole pattern starts anew.

From this, you can infer that the pattern repeats every 5 integers. Then, notice that $$4(n + 5)^2 = 4(n^2 + 25n + 25) = 4n^2 + 100n + 100$$. Since by definition, $$100n \equiv 0 (\mod 10)$$ for all integers $$n$$, we see that $$4(n + 5)^2 \equiv 4n^2 (\mod 10)$$.

• I'm not sure I understand. How does this prove that the modulo pattern continues forever? – Hassebae Aug 7 '19 at 17:45
• This would be more clear if it was extended to one more step, showing that $4(n+5)^2 = 4n^2 \pmod {10}$. – Varun Vejalla Aug 7 '19 at 18:01
• Fixed it as you suggested. Thanks. – Amy Ngo Aug 7 '19 at 20:29