what is the remainder when 17^2^111110253 is divided by 21
please show working
#thanks
To find the remainder when a number is divided by another number, we can make use of modular arithmetic.
In this case, we want to find the remainder when 17^2^111110253 is divided by 21.
Step 1: Calculate the exponent of 17^2^111110253 modulo 21.
To simplify the calculation, we can use modular arithmetic properties. We can find the remainder of the exponent 2^111110253 when divided by the totient of 21.
The totient function phi(n) gives the count of numbers less than n that are coprime with n. For any number n that is a product of distinct prime numbers, the value of phi(n) can be obtained by subtracting one from each prime factor and taking the product. In this case, 21 = 3 * 7, so phi(21) = (3-1) * (7-1) = 2 * 6 = 12.
Step 2: Calculate the remainder of the exponent 2^111110253 modulo 12.
Since phi(21) = 12, we can calculate the remainder of the exponent by dividing 111110253 by 12, and use the remainder as our new exponent.
111110253 / 12 = 9259187 remainder 5
So, the remainder of the exponent 2^111110253 modulo 12 is 5.
Step 3: Calculate the remainder of 17^5 modulo 21.
Now, we can calculate the remainder when 17^5 is divided by 21. We can calculate this by using repeated squaring to simplify the calculation:
17^1 % 21 = 17
17^2 % 21 = (17^1 * 17^1) % 21 = (17 * 17) % 21 = 289 % 21 = 17
17^3 % 21 = (17^2 * 17^1) % 21 = (17 * 17) % 21 = 289 % 21 = 17
17^4 % 21 = (17^2 * 17^2) % 21 = (17 * 17) % 21 = 289 % 21 = 17
17^5 % 21 = (17^4 * 17^1) % 21 = (17 * 17) % 21 = 289 % 21 = 17
Therefore, the remainder of 17^2^111110253 when divided by 21 is 17.