合同式の証明なんですが・・・

質問

31^2を法として3^30と1＋17・31が合同であることの証明方法がわかりません、よろしくお願いします。

回答No.1

oshiete_goo · ベストアンサー

一番平凡にやってますので，スマートな方法は詳しい方にきいて下さい．

31^2を法として，二項展開を適宜用いると

　3^30
＝27^10
＝{31＋(-4)}^10
≡10Ｃ1・31・(-4)^9＋(-4)^10　[31の2次以上のべきを因数に持つ項は落とせる・・・(＊)]
＝－10・31・4^9＋4^10
＝－5・31・2^19＋2^20
＝－5・31・32^3・2^4＋32^4
＝－5・31・(31＋1)^3・2^4＋(31＋1)^4
≡－5・31・1・2^4＋(4・31＋1)　[(＊)より，31・(31＋1)^3≡31・1，(31＋1)^4≡4・31＋1]
＝－5・31・16＋4・31＋1
＝31・(－76)＋１
＝31・(－3・31＋17)＋１
≡31・17＋１

よって　31^2を法として3^30と1＋17・31は合同．