0
$\begingroup$

So i'm pretty bad at math, but trying to solve this programming problem where there are an N amount of power values in the range of 1-9 and the last number has to be found. I have checked multiple threads here and also https://brilliant.org/wiki/finding-the-last-digit-of-a-power/ and Euler Totient function. However, the truth is that i'm kinda stupid, i can do some solid head calculations up to 5 digit numbers squared. But when it comes to advanced math.. i'm way behind. So could possibly anyone out there explain to me how this works?

To be more specific: lets take $9^{4^{2^{3^5}}}$

What is k when you use modulus, and how is it used?

What is 𝜑?

Why do you get a negative number when using modulus? Shouldn't it leave a remainder instead?

TLDR; Can someone explain how to get last digit of $9^{4^{2^{3^5}}}$ for person that is pretty bad at math?

$\endgroup$
  • $\begingroup$ Welcome to MSE. Here's a tutorial on typesetting math on this site. $\endgroup$ – saulspatz Dec 11 '19 at 15:59
  • $\begingroup$ For $\phi$, Google "Euler totient." $\endgroup$ – saulspatz Dec 11 '19 at 15:59
  • $\begingroup$ Please add the tag "elementary-number-theory". Else it will get much less exposure. $\endgroup$ – Bill Dubuque Dec 19 '19 at 18:38
  • $\begingroup$ thank you @BillDubuque $\endgroup$ – Vollan Dec 19 '19 at 18:44
2
$\begingroup$

It's a bit unclear to me what you mean by "problem where there are an N amount of power values in the range of 1-9 and the last number has to be found". Is this to say you're dealing with a power tower of integers in the range 1-9?

In any case, to find the last digit of $9^{4^{2^{3^5}}}$, we want to "reduce it mod $10$". First, some notation. \begin{equation*} a \equiv b \pmod{10} \end{equation*} means that "$a$ is congruent to $b$ modulo $10$". This means that they differ by a multiple of $10$, or equivalently, they leave the same remainder when divided by $10$. Hopefully you agree that if some integer \begin{equation*} n \equiv 3 \pmod{10} \end{equation*} then the last digit of $n$ must be $3$.

Now, we also have that if $a \equiv b \pmod{10}$ and $c \equiv d \pmod{10}$, then $ac \equiv bd \pmod{10}$. Maybe this is obvious to you already, if not, you can prove it from the "differ by a multiple of $10$" definition. Using this, any power of $9$ is congruent to $-1$ raised to that same exponent. So \begin{equation*} 9^{4^{2^{3^5}}} \equiv (-1)^{4^{2^{3^5}}} \pmod{10} \end{equation*} But the value of $(-1)^{4^{2^{3^5}}}$ just depends on whether $4^{2^{3^5}}$ is even or odd. Since this is some power of $4$, which is even, it is clearly even (since it is not $4^0$), so $(-1)^{4^{2^{3^5}}} = 1$, so the last digit of $9^{4^{2^{3^5}}}$ is $1$.

An alternative approach would just be to look at powers of $9$ mod $10$, and notice that they are congruent to $1$, $9$, $1$, $9$, ... and take it from there.

To generalise this approach for some kind of program requires looking at the periodicity of the powers of the base modulo $10$, and then recursing into the power tower to reduce the subtower modulo the period of the powers of the base. (Particularly, not all numbers are as nice as $9$, which only has period $2$)

Proof of $a \equiv b \pmod{10}$ and $c \equiv d \pmod{10} \implies ac \equiv bd \pmod{10}$.

Have $a = b + 10n$, $c = d + 10m$ for some $n, m \in \mathbb Z$ by definition.. Then \begin{align*} ac &= (b + 10n)(d + 10n) \\ &= bd + 10(n + m + 10nm) \\ &\equiv bd \pmod{10} \quad \text{by definition} \end{align*}

Proof of $a \equiv b \pmod{10} \implies a^n \equiv b^n \pmod{10}$:

The base case $n = 0$ is trivially true. Then \begin{align*} a^{n + 1} &\equiv a \cdot a^n \\ &\equiv b \cdot a^n \quad \text{by assumption} \\ &\equiv b \cdot b^n \quad \text{by inductive hypothesis} \\ &\equiv b^{n + 1} \end{align*}

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You lost me But the value of $(-1)^{4^{2^{3^5}}}$ just depends on whether $4^{2^{3^5}}$ is even or odd. Since this is some power of $4$, which is even, it is clearly even (since it is not $4^0$), so $(-1)^{4^{2^{3^5}}} = 1$, so the last digit of $9^{4^{2^{3^5}}}$ is $1$. here... Also, how to make this more generic? beginning with 9 was just an example, lets say you start with 8 or 4, (i guess 5 always end with 5...) $\endgroup$ – Vollan Dec 11 '19 at 15:59
  • $\begingroup$ $-1$ raised to any odd power is $-1$, and raised to any even power is $1$, so we only need to know whether or not the bit on top is even or odd. As for generic, that's what the last paragraph was trying to get at. If the base is $8$, you can calculate that the powers of $8$ go $1$, $8$, $4$, $6$, $2$, $8$ and repeat from there. Then you just need to know if the power you're raising it to is congruent to 0, 1, 2, or 3 mod 4. $\endgroup$ – Izaak van Dongen Dec 11 '19 at 16:03
  • $\begingroup$ Right, so how do i know if a number $8^{9^{9^9}}$ which result in a 369 million digit power off is congruent to 0,1,2 or 4? Edit: Sorry, as i mentioned above, i'm not that skilled when it comes to math $\endgroup$ – Vollan Dec 11 '19 at 16:16
  • $\begingroup$ @Vollan, by looking at the powers of $8$ mod $4$! And those happen to all be $0$, so $8^{9^{9^9}} \equiv 0 \pmod{4}$. Basically you just apply the whole procedure again, but this time we're looking for the last digit in base 4. This is what I meant by recursing. Please don't feel the need to apologise, lord knows there's enough maths I don't understand : ) $\endgroup$ – Izaak van Dongen Dec 11 '19 at 16:20
  • $\begingroup$ @Vollan or maybe you meant what $9^{9^9}$ would be mod $4$, which is $1$, since $9 \equiv 1 \pmod{4}$ $\endgroup$ – Izaak van Dongen Dec 11 '19 at 16:25

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.