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.
