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