Find the remainder when 43^(43⁴) is divided by 40.

Question

Accepted Answer

3. 43 ≡ 3 (mod 40). Need 3^(43⁴) mod 40. phi(40) = 16, ord(3) divides 16. 43 ≡ 11 (mod 16). 43⁴ ≡ 11⁴ (mod 16). 11 ≡ -5 (mod 16), 11² = 121 ≡ 9 (mod 16), 11⁴ ≡ 81 ≡ 1 (mod 16). So 43⁴ ≡ 1 (mod 16) but need mod 16. Actually 43⁴ mod 16: 43 mod 16 = 11, 11²=121 mod 16 = 9, 9²=81 mod 16 = 1. So 43⁴ ≡ 1 (mod 16). Wait: we need 3^(43⁴) mod 40. The order of 3 mod 40 is 4 (since 3¹=3, 3²=9, 3³=27, 3⁴=81≡1 mod 40). Check: 3⁴=81=2*40+1=81. Yes, 3⁴≡1 (mod 40). So need 43⁴ mod 4. 43 mod 4 = 3, 3⁴ = 81 mod 4 = 1. So 43⁴ ≡ 1 (mod 4). Then 3^(43⁴) = 3^(4k+1) = (3⁴)^k * 3 ≡ 1^k * 3 = 3 (mod 40).

Find the remainder when 43^(43⁴) is divided by 40.

Solution

Related JEE Advanced Maths questions