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

シェアする

スポンサーリンク

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

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

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

スポンサーリンク

答案

33を因数分解してみる。

33 = 3 × 11

だ。

3320を90で割るので、「9」がほしい。

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

332 = (3 × 11)2 = 9 × 121 = 9(110 + 11) = 990 + 99

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

332 ≡ 99 ≡ 9 (mod 90)

これでほぼ解けた。

余りを求める

332 ≡ 99 ≡ 9 (mod 90) より、

3320 = (332)10 ≡ 910

92 = 81 は90で割ると余りは81だが、-9とも表せる(81 = 90 × 1 – 9)。

よって、

92 = 81 ≡ -9

∴ 3320 ≡ 910

= (92)5

≡ (-9)5

= -95

= -(92)2 × 9

≡ -(-9) × 9

= 81

求める答えは、81

スポンサーリンク

シェアする

twitterをフォローする
twitterをフォローする

ブログを購読する
ブログを購読する

follow us in feedly RSS