7
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ the standard notation is just $x^{n+4}\equiv x^n\bmod 10$. When working with the modulus we only write $\bmod 10$ at the end of each line of identities, you dont need to repeat $\bmod 10$ next to every quantity $\endgroup$ – Masacroso Dec 24 '18 at 5:59
  • 1
    $\begingroup$ Sorry for a digression to the notation issues. @Masacroso I'd say that both notations are quite common: mod is sometimes used to denote a binary operation - in which case \bmod is used: $x^n \bmod 10$ $x^n \bmod 10$. But if we user congruences, the command \pmod is used to get something like $x^{n+4}\equiv x^n \pmod{10}$ $x^{n+4}\equiv x^n \pmod{10}$. $\endgroup$ – Martin Sleziak Dec 24 '18 at 8:59
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Actually, a general method requires a general result like Fermat or Euler's theorem (I show one way in my answer). The above method works only in very special cases. $\endgroup$ – Bill Dubuque Dec 25 '18 at 19:03
  • $\begingroup$ @Bill Dubuque I meant "general" in a different way, in that directly or indirectly all results boil down to ensuring all the congruence values provide desired result such as I showed. You are right that my method will not work well, or at all, in many cases such as where the modulo value is variable or a very large value. $\endgroup$ – John Omielan Dec 25 '18 at 23:35
  • $\begingroup$ Why do you only consider $x$ values 0..9? $\endgroup$ – Björn Lindqvist Dec 26 '18 at 2:15
  • $\begingroup$ @Björn Lindqvist I only consider $x$ values $0\ldots9$ since those are the only residue values $\mod 10$, i.e., any other integer has a remainder which is one of these values when divided by 10. Also, only the last digit of any one of the number affects the final last value last digit, which is why we are working with $\mod 10$. $\endgroup$ – John Omielan Dec 26 '18 at 2:17
9
$\begingroup$

$x^4\equiv1\pmod{10}$ for $x$ and $10$ coprime, by Euler's theorem, since $\varphi (10)=4$.

(The proof for $x$ not coprime to $10$ can be found in some of the other answers here.)

$\endgroup$
  • $\begingroup$ But $x$ is not assumed coprime to $10$ so the proof is either incomplete or incorrect. $\endgroup$ – Bill Dubuque Dec 25 '18 at 17:42
  • $\begingroup$ @BillDubuque. It's incomplete. It is apparent from the other answers that this is actually true in general. $\endgroup$ – Chris Custer Dec 25 '18 at 17:45
  • $\begingroup$ If your proof relies on other answers then you should explicitly mention that, Otherwise the answer could wrongly mislead readers into thinking that nothing more needs to be said (given the nuymber of votes I suspect this did actually occur). $\endgroup$ – Bill Dubuque Dec 25 '18 at 17:46
  • $\begingroup$ @BillDubuque. Ok, will do. $\endgroup$ – Chris Custer Dec 25 '18 at 17:48
  • $\begingroup$ Thanks for adding the note. Btw, note that your answer was posted first so readers could not have relied on other answers for this crucial fact. $\endgroup$ – Bill Dubuque Dec 25 '18 at 17:55
2
$\begingroup$

This is true because of the periodicity of the last digits of numbers raised to powers. if you check cor $x=2,3,4\ldots n$ you will see that after every $4$th power the last digit is the same, $2^1 = 2$ and $2^5 = 32$ thus the last digit is the same. $x^n \mod 10$ is essentially asking for the last digit. Thus, $$x^{n+4} \mod 10 = x^n \mod 10$$ Some numbers have a periodicity of $2$ when raised to powers, for example, $9$ but the unit digit is still the same as the first power as the first.

$\endgroup$
  • 1
    $\begingroup$ While your argument is true, this isn't a proof per se. $\endgroup$ – Hubble Dec 24 '18 at 5:51
  • $\begingroup$ Can it be written in such a way to make it a proof, or is just a logic? $\endgroup$ – Prakhar Nagpal Dec 24 '18 at 5:52
2
$\begingroup$

We want to show that $x^{n+4}-x^n=x^n(x^4-1)$ is a multiple of $10$.

We first notice that if $x^n$ is odd then $x^4-1$ will be even and vice versa. Consequently, the product will always be even.

If $x$ is divisible by $5$ then the product is divisible by $10$ because we have an even product which is divisible by $5$.

If $x$ is not divisible by $5$ then $x=5m+k$ for some $m$ and $k$ where $k\in\{1,2,3,4\}$.

Now, $x^4-1=(5m)^4+4(5m)^3k+6(5m)^2k^2+4(5m)k^3+k^4-1$ and every term is divisible by $5$ with the possible exception of $k^4-1$.

But there are only four values of $k$ and if you raise each to the fourth power and subtract $1$ you get a multiple of $5$. Once again, this gives us an even number divisible by $5$ which is a multiple of $10$.

$\endgroup$
2
$\begingroup$

It is the special case $\,p,q,k = 2,5,4\,$ below.

Lemma $\,p\neq q\,$ primes $ $ & $\, \color{#c00}{p\!-\!1,\,q\!-\!1\mid k}\,\Rightarrow\, pq\mid\smash[t]{\overbrace{ x^n(x^k\!-\!1)}^{\large a}}\,$ for all $\,x\,$ & $\,n>0$

Proof $\ $ $\,p,q\,$ are coprime so $\,pq\mid a\iff p,q\mid a,\,$ by Euclid / unique factorization.

When $\, p\mid x\,$ then $\,p\mid x\mid x^n\mid a\,$ by $\,n>0,\,$ hence $\,p\mid a\,$ by transitivity of divisibility,

$ $ else: $\,\ p\nmid x\,$ so $\!\bmod p\!:\ x\not\equiv 0\,$ so $\,x^k \equiv (\color{#0a0}{x^{p-1}})^{\smash[t]{\Large\color{#c00}{\frac{k}{p-1}}}}\!\!\equiv\color{#0a0} 1\,$ by $\rm\color{#0a0}{Fermat},\,$ so $\,p\mid x^k\!-1\mid a$.

So in every case $\,p\mid a,\,$ so $\,q\mid a\,$ by $\,p,q\,$ symmetry (i.e. same proof works for $q). \ $


Remark $ $ Above is a special case of this generalization of Euler-Fermat - which often proves handy.

Theorem $\ $ Suppose that $\ m\in \mathbb N\ $ has the prime factorization $\:m = p_1^{e_{1}}\cdots\:p_k^{e_k}\ $ and suppose that for all $\,i,\,$ $\ e\ge e_i\ $ and $\ \phi(p_i^{e_{i}})\mid f.\ $ Then $\ m\mid a^e(a^f-1)\ $ for all $\: a\in \mathbb Z.$

Proof $\ $ Notice that if $\ p_i\mid a\ $ then $\:p_i^{e_{i}}\mid a^e\ $ by $\ e_i \le e.\: $ Else $\:a\:$ is coprime to $\: p_i\:$ so by Euler's phi theorem, $\!\bmod q = p_i^{e_{i}}:\, \ a^{\phi(q)}\equiv 1 \Rightarrow\ a^f\equiv 1\, $ by $\: \phi(q)\mid f.\ $ Since all $\ p_i^{e_{i}}\ |\ a^e (a^f - 1)\ $ so too does their lcm = product = $m$.

Examples $\ $ You can find many illuminating examples in prior questions, e.g. below

$24\mid a^3(a^2-1)$

$40\mid a^3(a^4-1)$

$88\mid a^5(a^{20}-1)$

$6p\mid a\,b^p - b\,a^p$

$\endgroup$
1
$\begingroup$

If you can prove $x^4 \equiv 1 \pmod {10}$ that's enough as $x^{n+4}\equiv x^n\cdot x^4 \equiv x^n\cdot 1\equiv x^n\pmod {10}$

If you google Euler's theorem that will be true for all numbers relatively prime to $10$. Intuitively (but hand wavy) if $x$ and $10$ are relatively prime then $x^n$ will be relatively prime. There are only $4$ possible last digits that are relatively prime to $10$ so $x^k$ will cycle through the same four digits. (More or less.)

If $x$ is even or divisible by $5$. Well, if it's both then $x \equiv 0 \mod 10$ so $x^k \equiv 0 \pmod {10}$ and $x^{n+4} \equiv x^n \equiv 0\pmod {10}$. Likewise if it's odd but divisible by $5$ then $x^k \equiv 5 \pmod{10}$ and so $x^{n+4} \equiv x^n \equiv 5 \pmod {10}$.

Now if $x$ is even but not divisible by $5$ then. Well, $x^n$ is even and there are only $4$ even digits it could end with and it cycles through them.

More to the point $2*j \pmod 10 \equiv 2*(j \pmod 5)$ and there are only $4$ non-zero classes $\pmod 5$ so $x^k$ just cycles through those.

$\endgroup$
1
$\begingroup$

Because:

$x^{n+4} = x^{n-1}x^5$
$x^n = x^{n-1}x$
($ab\mod 10) = (a(b\mod 10) \mod 10)$

... you only have to prove that $(x^5 \mod 10)=(x\mod 10)$.

... which means: $((x \mod 10)^5\mod 10) = (x \mod 10)$.

Because there are only 10 possible values for $(x \mod 10)$ these 10 values can be calculated directly:

  • $0^5\mod 10=0 \mod 10=0$
  • $1^5\mod 10=1 \mod 10=1$
  • $2^5\mod 10=32 \mod 10=2$
  • $3^5\mod 10=243 \mod 10=3$
    ...
  • $9^5\mod 10=59049 \mod 10=9$
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.