Question

Remainder when 43^43^43 is divided by 40

Answer 1

27

Answer 2

We want to find the remainder when $43^{43^{43}}$ is divided by 40. This is equivalent to finding $43^{43^{43}} \pmod{40}$.

Step 1: Simplify the base modulo 40.

$43 \equiv 3 \pmod{40}$. So, $43^{43^{43}} \equiv 3^{43^{43}} \pmod{40}$.

Step 2: Apply Euler's totient theorem for the modulus 40.

The modulus is $n=40$. The base is $a=3$. Since $\gcd(3, 40) = 1$, we can use Euler's theorem. First, calculate $\phi(40)$. The prime factorization of 40 is $2^3 \times 5^1$. $\phi(40) = \phi(2^3) \times \phi(5^1) = (2^3 - 2^2) \times (5^1 - 5^0) = (8 - 4) \times (5 - 1) = 4 \times 4 = 16$. By Euler's totient theorem, if $\gcd(a, n) = 1$, then $a^{\phi(n)} \equiv 1 \pmod{n}$. Here, $3^{16} \equiv 1 \pmod{40}$.

Step 3: Evaluate the exponent modulo $\phi(40)=16$.

We need to find the value of the exponent $43^{43}$ modulo 16. Let $E = 43^{43}$. We need to find $E \pmod{16}$.

Step 4: Simplify the base of the exponent modulo 16.

$43 \equiv 11 \pmod{16}$. So, $43^{43} \equiv 11^{43} \pmod{16}$.

Step 5: Apply Euler's totient theorem for the modulus 16.

The modulus is $m=16$. The base is $b=11$. Since $\gcd(11, 16) = 1$, we can use Euler's theorem. First, calculate $\phi(16)$. The prime factorization of 16 is $2^4$. $\phi(16) = 2^4 - 2^3 = 16 - 8 = 8$. By Euler's totient theorem, $11^8 \equiv 1 \pmod{16}$.

Step 6: Evaluate the exponent of the exponent modulo $\phi(16)=8$.

We need to find the value of the exponent 43 modulo 8. $43 = 5 \times 8 + 3$. So, $43 \equiv 3 \pmod{8}$.

Step 7: Use the result from Step 6 to simplify $11^{43} \pmod{16}$.

Since $11^8 \equiv 1 \pmod{16}$ and $43 \equiv 3 \pmod{8}$, we can write $43 = 8q + 3$ for some integer $q$. $11^{43} = 11^{8q + 3} = (11^8)^q \times 11^3$. $11^{43} \equiv (1)^q \times 11^3 \pmod{16}$. $11^{43} \equiv 11^3 \pmod{16}$.

Step 8: Calculate $11^3 \pmod{16}$.

$11^1 \equiv 11 \pmod{16}$. $11^2 = 121$. Dividing 121 by 16 gives $121 = 7 \times 16 + 9$. So, $11^2 \equiv 9 \pmod{16}$. $11^3 = 11^2 \times 11 \equiv 9 \times 11 = 99 \pmod{16}$. Dividing 99 by 16 gives $99 = 6 \times 16 + 3$. So, $11^3 \equiv 3 \pmod{16}$.

Step 9: Conclude the value of the exponent modulo 16.

From Step 4 and Step 8, $E = 43^{43} \equiv 11^{43} \equiv 3 \pmod{16}$. This means the exponent $43^{43}$ can be written in the form $16j + 3$ for some non-negative integer $j$.

Step 10: Use the result from Step 9 to evaluate the original expression modulo 40.

We need to calculate $3^E \pmod{40}$, where $E \equiv 3 \pmod{16}$. Substituting $E = 16j + 3$, we get $3^{16j + 3} \pmod{40}$. $3^{16j + 3} = 3^{16j} \times 3^3 = (3^{16})^j \times 3^3$. From Step 2, $3^{16} \equiv 1 \pmod{40}$. So, $(3^{16})^j \equiv 1^j \equiv 1 \pmod{40}$. Therefore, $3^E \equiv 1 \times 3^3 \pmod{40}$. $3^E \equiv 27 \pmod{40}$.

Step 11: State the final remainder.

The remainder when $43^{43^{43}}$ is divided by 40 is 27.