Wednesday, 10 August 2016

elementary number theory - Proof that $x^{(n+4)} bmod 10 = x^n bmod 10,$ for $,nge 1$



While solving a programming challenge in which one should efficiently compute the last digit of $a^b$, I noticed that apparently the following holds (for $n > 0$)



$x^{(n+4)} \mod 10 = x^n \mod 10$




How can this be proven?


Answer



Consider how the difference, i.e.,
$$x^{n + 4} - x^{n} = x^{n} \left( x^4 - 1 \right) = x^{n} \left( x^2 - 1 \right) \left( x^2 + 1 \right)$$
behaves for all cases of $x \mod 10$ from $0$ to $9$, inclusive. For $x$ being $0$, the result is $0$. For $x$ being an even positive value, then $x^n$ is a multiple of 2, while either $x^2 + 1$ or $x^2 - 1$ is a multiple of 5, so together are a multiple of $10$. Finally, for $x$ being an odd value, consider the cases:



$1$: $x^2 - 1$ is $0$



$3$: $x^2 + 1$ is $10$, i.e., $0 \mod 10$




$5$: $x^n$ is a multiple of $5$ and $x^2 - 1$ is a multiple of $2$, so together shows congruent to $0$



$7$: $x^2 + 1$ is $50$



$9$: $x^2 - 1$ is $80$



This shows that the result is congruent to $0$ in all cases. The other answers here are generally shorter and simpler, so they're better if you're able to use them. However, this is a fairly general way to check basically any congruence operation where ever it can be relatively easily used (e.g., where the mod divisor is not a variable or too large).


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...