質問: これをmodを使わないでとく方法ってありますか? これをmodを使わないでとく方法ってありますか? 知ってる人がいれば教えてください🙏 でも、ひたすら解く以外でお願いします!
回答: 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です.