Finding the Remainder of 911^420 when Divided by 69: A Detailed Analysis

When faced with the task of determining the remainder of (911^{420}) when divided by 69, several methods can be employed, including modular arithmetic, Euler's Theorem, and Fermat's Little Theorem. We will explore these methods in detail, step by step, to arrive at the answer.

Using Modular Arithmetic

First, let's use modular arithmetic to simplify the expression. Given that (911 equiv 14 mod 69), we can rewrite (911^{420}) as (14^{420} mod 69).

We know that (14^7 equiv -4 mod 69). Therefore:

[14^{420} 14^{7 times 60} equiv (-4)^{60} mod 69]

Since ((-4)^{12} equiv 4 mod 69), we can simplify further:

[(-4)^{60} (-4)^{12 times 5} equiv 4^5 mod 69]

Calculating (4^5 mod 69), we get:

[4^5 1024 equiv 58 mod 69]

Hence, the remainder is 58.

Using Euler's Theorem

Euler's Totient Function can be applied to simplify the problem as well. Euler's Theorem states that if two numbers (a) and (n) are coprime, then (a^{varphi(n)} equiv 1 mod n). Here, (n 69), and (911) is coprime to (69).

First, calculate the value of (varphi(69)):

[varphi(69) 69 left(1 - frac{1}{3}right)left(1 - frac{1}{23}right) 69 left(frac{2}{3}right)left(frac{22}{23}right) 44]

Using Euler's Theorem, we have:

[911^{44} equiv 1 mod 69]

Therefore, (911^{420} 911^{44 times 9} times 911^3 equiv 1^9 times 911^3 mod 69). We can simplify this further using the previously calculated value:

[911^3 equiv 53 mod 69]

This reduces the problem to finding (911^3 mod 69).

Using Fermat's Little Theorem

Fermat's Little Theorem states that if (p) is a prime number and (a) is an integer not divisible by (p), then (a^{p-1} equiv 1 mod p).

Since (69 3 times 23), we can use the theorem for both 3 and 23 separately:

[911^2 equiv 1 mod 3]

[911^2 equiv -11 mod 3equiv 1 mod 3]

[911^2 equiv 1 mod 23]

[911^2 equiv -11 mod 23equiv 12 mod 23]

Combining these, we get:

[911^420 (911^2)^{210} equiv 1^{210} equiv 1 mod 23]

[911^420 (911^2)^{210} equiv 1^{210} equiv 1 mod 3]

[911^420 equiv 58 mod 69]

Hence, the remainder when (911^{420}) is divided by 69 is 58.