整数の求めかた

質問

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

(2＾(30))-n=30N
(2＾(30))≡n(mod30)
(2＾(30))＝３０Ｋ＋64
=30(K＋2)＋4

の意味（式）がよく分かりません

回答No.3

noname#52504 · ベストアンサー

意味（式）がよく分かりませんでは何がわからないのかよくわかりませんが…。

★第２式は第１式を定義通り合同式に書き直しただけです。

整数a,bに対し、差a-bが正の整数nで割り切れる時、aとbはｎを法として合同であるという（定義）
→整数2^30，nに対して、差2^30-nが正の整数30で割り切れるから、2^30とnは30を法として合同である。

aとbがｎを法として合同であるとき、a ≡ b (mod n )と書く（定義）
→2^30とnが30を法として合同であるから、2^30 ≡ n （mod30)

★第３式の変形
2^30 = (2^10)^3 = 1024^3 = (30・34+4)^3 = 30K+4^3 = 30K+64 = 30(K+2)+4

★ここでいきなりn=4と書いてもよさそうな気もしますが、以降の処理をじみ～に書くならば…

2^30 = 30(K+2)+4　
2^30 -4 = 30(K+2)
よって、
2^30 ≡ 4 (mod30)　（定義通り)

2^30 ≡ 4 (mod30)　および
2^30 ≡ n （mod30) より　(対称律・推移律が使えるので）
n ≡ 4 (mod30)

定義より
n-4 = 30M （M：整数)
n = 30M+4

これを満たす最小の正の数nはM=0のとき4(Ans.

質問文の書き方からみて、合同の定義を習った直後のように感じました。
季節を考慮しても、オイラーの定理が出てくるのはしばらく先の話でしょう、たぶん。
1024を使っているのは、
「2^nのうち、高校卒業生が覚えていると期待できる最大の値」
だからでは？

回答No.4

noname#52504

#3です。
第３式の式変形の意図は
2^30 = (2^5)^6 = (30+2)^6 = 30K+2^6 = 30K+64
ですね、たぶん。

…って#2さんが既に書いておられるし（恥

お礼

みなさんどうもありがとうございました。

回答No.2

kabaokaba

> の意味（式）がよく分かりません

こじつけてみましょう
2^30= (1020 + 4)^3
1020 = 34 * 30 なので，適当な自然数Kをつかって
2^30 = (34*30+4)^3 = 30K+4^3 = 30K+64
=30(K+2)+4
と表せます．
よって，答えは 4 です

私なら1024は使わずにこうしますが．
2^n で30に一番近いのは 2^5=32 です．
これを手がかりにします．
mod 30 は省略します
2^30 = (2^5)^6 = (32)^6
≡ 2^6 = 2 (2^5) = 2(32)
≡ 2・2 = 4
だから
答えは 4

回答No.1

koko_u_

他に何の解説もなし？

普通にやるなら オイラーの定理を使うので、

2^φ(15) ≡ 1 (mod 15) すなわち 2^8 ≡ 1 (mod 15)

よって 2^30 = 2^(3*8+6) ≡ 2^6 = 64 ≡ 4 ( mod 15 ) だけど。