Question

S,Ａ

これをmodを使わないでとく方法ってありますか？
知ってる人がいれば教えてください🙏
でも、ひたすら解く以外でお願いします！

17" を 256 で割った余り を求め よ。

Answer 1

チャート

17^17
= (16+1)^17
= 16^17 + 17 C 1 ×16^16 + 17 C 2 ×16^15 + …
… + 17 C 15 × 16^2 + 17 C 16 × 16 + 1
= 16^2 × N + 17×16+1 (Nは整数)
=256(N+1) +17

よって、17^17 を256で割った余りは、17
わかりにくいところがあれば質問してください。
間違ってたらすみません。

Answer 2

LUX SIT

256=2^8, 17=2^4+1と書けることに着目しましょう.
あとは(2^4+1)^17を二項展開することで割り切れる項と割り切れない項に分離して余りを求めます.
***
(2^4+1)^17
=Σ[k=0->17]C(n,k)(2^4)^n*1^(17-n)
=Σ[k=0->17]C(n,k)2^(4n)
=Σ[k=2->17]C(n,k)2^(4n)[これらの項は2^(4*2)=2^8=256を約数にもつ]+C(17,1)2^4+C(17,0)2^0[残りの項が余りを決める]
=Σ[k=2->17]C(n,k)2^(4n)+(17*16+1)
=Σ[k=2->17]C(n,k)2^(4n)+2^8+17
ここでΣ[k=2->17]C(n,k)2^(4n)は2^(4*2)=2^8=256を約数にもつ.
したがって17^17を256で割った余りは17です.