合同

質問

整数a,bに対し、差a-bが正の整数nで割り切れる時、a,とbはnを法として合同であるという。
30を法として(2＾30)と合同である整数のうち最小値の正の整数を求める問題

(2＾30)-n=30N
(20＾30)=m(mod30)の2つの表した方が分かりません。

(2＾30)
=(2＾5)＾6
=(32)＾6
=(30＋2)＾6
から
30K＋64とさらに計算して30(K＋2)＋4になることが分かりません。

回答No.3

ujitaka

2^30を変形すると、(2^30)＝(2^5)^6＝(32)^6となります。この右辺を30を法として変形します。
(32)^6≡2^6≡64≡60＋4≡4
ｎ＝４が求める数では？

回答No.2

amanita

訂正

＞大事なのは、一番左の項以外は、全部の項がaで割り切れることです。

↓

大事なのは、一番右の項以外は、全部の項がaで割り切れることです。

回答No.1

amanita

(a + b)^n は　展開すると、

a^n + αa^(n-1)・b　+　βa^(n-2)・b　+　…　+　ωa・b^(n-1) + b^n

の形になります。

各項の係数は、パスカルの三角形になりますが、ここではどうでもいいです。
大事なのは、一番左の項以外は、全部の項がaで割り切れることです。

だから、(30＋2)＾6　は　30K＋2^6　に変形できます。