数学
高校生

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

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

回答

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です.

この回答にコメントする

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
わかりにくいところがあれば質問してください。
間違ってたらすみません。

この回答にコメントする