1

The question is to find $2^{3^{100}} \pmod 5$ and its last digit.

I think we have to find $2 \pmod 5$ and $3^{100}\pmod 5$ separately, right?

$$2 = 2 \pmod 5$$ $$3^4 = 1 \pmod 5$$ $$3^{100} = 1 \pmod 5$$ $$2^{3^{100}} = 2^1 = 2 \pmod 5$$

Is this solution correct? And to find the last digit do we just solve modulo $10$?

Adam Hughes
  • 36,777
Borat Sagdiyev
  • 537
  • 3
    If $p$ is a prime number, then $$2^{p-1} = 1\text{ mod } p$$ This means that in the exponent, you need to reduce modulo (p-1) and not modulo p. – Count Iblis Oct 21 '15 at 20:06
  • It's not correct - $a\equiv b\pmod n$ doesn't imply $c^a\equiv c^a\pmod n$. – Wojowu Oct 21 '15 at 20:07

2 Answers2

2

Yes, you solve modulo $10$ for the last digit. Note that the number is even, so its last digit is taken from $2, 5, 6, 8$--it's not divisible by $5$ so the last digit cannot be $0$. Your original solution is a bit off, though $3^4\equiv 1\mod 5$, but in the exponent it's every $4$ which gives $1$, so we want $3^2\equiv 1\mod 4$. Then $3^{100}\equiv 1\mod 4$. So

$$2^{3^{100}}=2^{4k+1}\equiv (16)^k\cdot 2\mod 5$$

which gives the same result, but by sounder methods. Since it is $2$ mod $5$ as you have said, the only choices are $2$ and $7$. $7$ is odd, so it must be $2$.

Adam Hughes
  • 36,777
  • Is it true in general that $;a^n\equiv a^{n\bmod (p-1)}\mod p$ ? For any natural number a? – Borat Sagdiyev Oct 21 '15 at 20:27
  • 1
    @E.A. When $p$ is prime, yes. – Adam Hughes Oct 21 '15 at 20:28
  • Thank you. And for the last digit, since we know that $2^{3^{100}} = 2 \pmod 5$ and $2^{3^{100}} = 2 \pmod 2$ can we conclude that $2^{3^{100}} = 2 \pmod {10}$ ? But how would knowing that it's congruent 2 modulo 10 give us the last digit? – Borat Sagdiyev Oct 21 '15 at 20:37
  • @E.A. as I said, being $2$ mod $2$ just means you're even. So you're looking for an even digit which is $2$ mod $5$, the only choice is $2$. And note that if your digits are $0\le d_i\le 9$ with $0\le i\le n$ then your number $k=10^nd_n+10^{n-1}d_{n-1}+\ldots+10d_1+d_0$ then the last digit $d_0$ is the same as $k$ mod $10$. – Adam Hughes Oct 21 '15 at 20:39
0

Hint for the first question:

By Little Fermat, $\;2^4\equiv 1\mod 5$, hence $\;2^n\equiv 2^{n\bmod 4}\mod 5$. Also $3^2\equiv 1\mod 4$.

Second question:

Use the Chinese Remainder theorem: $\;\mathbf Z/10\mathbf Z\simeq \mathbf Z/2\mathbf Z\times\mathbf Z/5\mathbf Z$.

Bernard
  • 175,478