2^nをｎで割ったときのあまり

質問

ｎが素数のときは2＾ｎをｎで割ったあまりはフェルマーの小定理から2です。ｎが２のべき乗ならあまりは当然0です。
ｎが合成数のとき、あまりはｎによっていろいろですが、多くは偶数のようです。50以下ではｎ＝45のときだけ17です。ここには何か法則性はありませんか？あるいはｎによってあまりを分類できませんか？

回答No.1

muturajcp · ベストアンサー

n=25の時
2^20=1mod25
2^25=2^5=32=7mod25
だから
2^25を25で割った余りは
7
と奇数となるようですが

n=45の時
2^12=1mod45
2^45=2^9=17mod45

n=55の時
2^20=1mod55
2^55=2^(20*2+15)=2^15=43mod55

n=91の時
2^12=1mod91
2^91=2^(12*7+7)=2^7=37mod91

n=95の時
2^36=1mod95
2^95=2^(36*2+23)=2^23=13mod95

n=99の時
2^30=1mod99
2^99=2^(30*3+9)=2^9=17mod99

n=125の時
2^100=1mod125
2^125=2^(100+25)=2^25=57mod125

2^135=53mod135
2^143=85mod143
2^153=53mod153
2^161=151mod161
2^175=93mod175
2^187=161mod187
2^225=107mod225
2^235=173mod235
2^245=67mod245
2^247=193mod247
2^261=251mod261
2^273=239mod273
2^275=43mod275
2^279=233mod279
2^285=107mod285
2^289=155mod289
2^297=161mod297
2^319=105mod319
2^329=81mod329
2^333=179mod333
2^335=233mod335
2^355=103mod355
2^363=239mod363
2^369=143mod369
2^387=125mod387
2^391=179mod391
2^403=349mod403
2^407=161mod407
2^413=305mod413
2^423=89mod423
2^425=257mod425
2^429=83mod429
2^435=143mod435
2^437=279mod437
2^441=197mod441
2^459=161mod459
2^473=371mod473
2^477=35mod477
2^481=15mod481
2^483=449mod483
2^493=253mod493

お礼

500