【合同式】33^20を90で割った余り

最近は「巨大な数の割り算の余りを合同式を用いて解く」のにハマっている。

YouTubeでこんな問題を見つけた。

合同式を使って解いてみた。

答案

33を因数分解してみる。

33 = 3 × 11

だ。

33²⁰を90で割るので、「9」がほしい。

なので33を2乗してみる。

33² = (3 × 11)² = 9 × 121 = 9(110 + 11) = 990 + 99

990は90で割り切れるので、合同式で表すと、

33² ≡ 99 ≡ 9 (mod 90)

これでほぼ解けた。

余りを求める

33² ≡ 99 ≡ 9 (mod 90)　より、

33²⁰ = (33²)¹⁰ ≡ 9¹⁰

9² = 81 は90で割ると余りは81だが、-9とも表せる（81 = 90 × 1 – 9）。

よって、

9² = 81 ≡ -9

∴ 33²⁰ ≡ 9¹⁰

= (9²)⁵

≡ (-9)⁵

= -9⁵

= -(9²)² × 9

≡ -(-9) × 9

= 81

求める答えは、81。