How can one prove a recognized modulo pattern?

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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.