+0

# Modular Arithmetic

0
53
2

What is the remainder when $$99^{36}$$ is divided by 100?

Apr 8, 2023

#1
0

To find the remainder when 99^36 is divided by 100, we can use modular arithmetic.

Breaking down 99 and 100 into their prime factors, we have 99 = 3^2 * 11 and 100 = 2^2 * 5^2. We can use the Chinese Remainder Theorem to deal with the prime factorization of 100.

First, we can find the remainder when 99^36 is divided by 4, which is the highest power of 2 that divides 100. Since 99 ≡ -1 (mod 4), we have:

99^36 ≡ (-1)^36 ≡ 1 (mod 4)

Therefore, the remainder when 99^36 is divided by 4 is 1.

Next, we can find the remainder when 99^36 is divided by 25, which is the highest power of 5 that divides 100. Since 99 ≡ -1 (mod 5), we have:

99^36 ≡ (-1)^36 ≡ 1 (mod 5)

By applying Euler's totient theorem, we can further simplify the exponent:

99^36 ≡ 99^(20 + 16) ≡ (99^20)(99^16) ≡ (1)(-1)^16 ≡ 1 (mod 25)

Therefore, the remainder when 99^36 is divided by 25 is also 1.

Now, we can use the Chinese Remainder Theorem to find the remainder when 99^36 is divided by 100. Since 4 and 25 are relatively prime, we can express the remainder as:

99^36 ≡ A(25)(25 inverse) + B(4)(4 inverse) (mod 100)

where A and B are the remainders when 99^36 is divided by 25 and 4, respectively, and (25 inverse) and (4 inverse) are the modular inverses of 25 and 4, respectively.

Since 25 inverse ≡ 21 (mod 4) and 4 inverse ≡ 1 (mod 25), we have:

99^36 ≡ 21(25)(1) + 1(4)(21) ≡ 546 ≡ 46 (mod 100)

Therefore, the remainder when 99^36 is divided by 100 is 46.

Apr 8, 2023
#2
+1

$$\displaystyle 99 \equiv -1\bmod(100), \\ 99^{36}\equiv(-1)^{36} \bmod(100) \equiv 1\bmod(100).$$

.

.
Apr 9, 2023