3
$\begingroup$

I'm a little bit stuck with this problem I hope you can help. I want to find the last digit of a power tower using Euler's theorem: \begin{align} q &= 10, \\ \varphi(q) &= 4, \\ \varphi(\varphi(q)) &= 2, \\\varphi(\varphi(\varphi(q))) &= 1. \end{align} \begin{align} 625703 ^{\displaystyle 43898 ^{\displaystyle 614961 ^{\displaystyle 448629}}} &\equiv (625703 \bmod 10)^{\displaystyle (43898 \bmod \varphi(10))^{\displaystyle (614961 \bmod \varphi(\varphi(10)))^{\displaystyle (448629 \bmod \varphi(\varphi(\varphi(10))))}}} \mod 10 \\ &\equiv 3^{\displaystyle 2^{\displaystyle 1^{\displaystyle 0}}} \mod 10 \\ &\equiv 3^{\displaystyle 2^{\displaystyle 1}} \mod 10 \\ &\equiv 3^{\displaystyle 2} \mod 10 \\ &\equiv 9 \mod 10 \end{align} According to this approach the last digit of the power tower must be 9. However, the right solution is 1 (see here) - what am I doing wrong?

This approach is based on the following two answers

computing ${{27^{27}}^{27}}^{27}\pmod {10}$

What's a general algorithm/technique to find the last digit of a nested exponential?

$\endgroup$
3
  • 1
    $\begingroup$ First note that $3^{4n}\equiv 1 \pmod {10}$. Then note that your exponent is clearly divisible by $4$. $\endgroup$
    – lulu
    Nov 1, 2020 at 18:41
  • 1
    $\begingroup$ Please don't maek nontrivial changes to your question after answers have appeared since this may invalidate answers. If you have a question about an answer then ask it in comments on the answer. If you have another question then pose it anew. I have reverted to the originla question. $\endgroup$ Nov 1, 2020 at 21:03
  • $\begingroup$ Okay sorry my fault $\endgroup$
    – Jan L
    Nov 1, 2020 at 21:10

3 Answers 3

2
$\begingroup$

What am I doing wrong?

Euler's theorem assumes that the base and the modulus are relatively prime.

In your problem, that is not the case: $43898$ is not relatively prime to $4$.

In fact, $43898^n\equiv0\pmod4$ for $n\ge2$.

Can you solve it now?

$\endgroup$
7
  • $\begingroup$ Thank you very much. Can I use at this point the euler's theorem shortcut?> If $a$ and $m$ are arbitrary positive integers and $b\ge\varphi(m)$, then > $$ a^b \equiv a^{\varphi(m)+(b\bmod\varphi(m))} \pmod m$$ $\endgroup$
    – Jan L
    Nov 1, 2020 at 19:23
  • $\begingroup$ That should work $\endgroup$ Nov 1, 2020 at 19:27
  • $\begingroup$ I updated my answer using the shortcut, however I still have one question could you please have a look? Thank you so much for you help appreciate it! $\endgroup$
    – Jan L
    Nov 1, 2020 at 20:42
  • $\begingroup$ I think the "shortcut" holds whether or not $a$ and $m$ are co-prime $\endgroup$ Nov 1, 2020 at 20:57
  • $\begingroup$ Okay but why am I allowed to use euler's theorem in the first place \begin{align} (625703 \bmod 10)^{\displaystyle (43898 \bmod \varphi(10)} \end{align} whereas when I move the tower up : \begin{align} {\displaystyle (\varphi(\varphi(10)) + 614961 \bmod \varphi(\varphi(10)))^{\displaystyle (448629 \bmod \varphi(\varphi(\varphi(10))))}} \end{align} I mustn't use it (however 614961 and $\varphi(\varphi(10))$ are coprime). If I use \begin{align}{\displaystyle (448629 \bmod \varphi(\varphi(\varphi(10))))}\end{align}. My result is wrong. Can you explain this to me? $\endgroup$
    – Jan L
    Nov 2, 2020 at 13:23
2
$\begingroup$

Hint: $ $ notice that: $\ n\ge 2\,\Rightarrow\, \color{#c00}{(2k)^n\bmod 4 \,\equiv\, 0}\ $ so by $ $ modular order reduction

$\!\!\bmod 10\!:\ 3^{\large \color{#c00}4}\equiv 1 \Rightarrow\ 3^{\large \color{}{(2k)^{\large n}}}\!\!\!\equiv 3^{\large \color{#c00}{(2k)^{\large n}\bmod 4}}\!\equiv 3^{\:\!\large\color{#c00} 0}\equiv 1,\ $ and

$\!\!\bmod 10\!:\ 625703\equiv 3\Rightarrow 625703^N\!\equiv 3^N\,$ by the Congruence Power Rule.

Remark $ $ The oversight is: Euler's theorem $\,a^{\phi(m)}\equiv 1\pmod{\!m}\,$ has hypothesis $\,\gcd(a,m)= 1\,$ so it does not apply to $\,(2k)^n\pmod{\! 4}.\,$ In such cases we can pull out the gcd of $\,a^N$ and $\,m\,$ using the mod Distributive Law, reducing to the coprime case where Euler applies, e.g. see here. Though it is overkill in this case, we could apply it above to factor out the common factor $2^2$ as follows

$$\quad\ \color{#0a0}{n\ge 2}\,\Rightarrow\,\color{#c00}{(2k)^{\large n}\!\bmod 4} \,=\, 2^2 (k^2 (2k)^{\large \color{#0a0}{n-2}}\!\bmod 1) \:\!=\:\! 2^2(0) \:\!=\:\! 0$$

Using this idea in your recursive algorithm then allows you to handle arbitrary power towers.

$\endgroup$
1
$\begingroup$

\begin{align} 625703^{43898^{\scriptstyle614961^{\scriptstyle448629}}}\mkern-18mu\bmod 10&= (625703\bmod 10)^{43898^{\scriptstyle614961^{\scriptstyle448629}}\bmod\varphi(10)}\\ &= 3^{43898^{\scriptstyle614961^{\scriptstyle448629}}\mkern-12mu\bmod4}=3^{2^{\scriptstyle614961^{\scriptstyle448629}}\mkern-12mu\bmod4}=3^0. \end{align}

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .