素数の余り

問 aは素数であり、a>3とする時、a^2を24で割った余りを求めよ。

答えは1なのですが、解き方が分かりません。
a^2 = 24k+1であることを証明すればいいのですが…

偶然の解として、a⇒6k±1(kは適切な数とし、+-1のうち適当な方を取るとする)とおけ、
a^2⇒(6k±1)^2 = 36k^2±12k+1 = 12k(3k^2±1)+1,3k^2±1のどちらかは2の倍数だから、a^2 ⇒24k+1、という形は出せましたが、a⇒6k±1が証明できません。また、a⇒6k±1に脈絡性がないです。

綺麗な解き方があれば、ご教授願います。

No.7 回答者： staratras 回答日時： 2013/09/07 20:35

No.6です。

少し補足します。

n,k,rを整数とすると、（nk+r)^2=n^2・k^2+2nkr+r^2)なので、nが偶数であればn^2がnの偶数倍となるため、n^2・k^2+2nkrは必ず2nの倍数になります。

この問題ではa^2を24で割った余りを考えるので、n=12とすればn^2・k^2+2nkrは必ず24の倍数になることを利用して計算を楽にしました。もちろんn=24としても解けますが、rの場合分けが増えて計算が煩雑です。

この回答への補足

なるほど。この考え方が、自分にとっては一番「しっくり」来ますね。
数学はつくづく感性の学問だと思います。

補足日時：2013/09/07 21:03

No.6 回答者： staratras 回答日時： 2013/09/07 15:44

愚直に解いてもあまり手間はかからないと思いますが…。

a=12k+r とおく、kは負でない整数、aはa>3の素数なので、k≧１のときr=1,5,7,11、k=0のとき5,7,11のいずれかの値をとる。(rは3の倍数にはならない)

a^2=144k^2+24k+r^2=24(6K^2+k)+r^2 だから　a^2を24で割った余りはr^2を24で割ったあまりに等しい。

1^2=1=24×0+1,
5^2=25=24×1+1
7^2=49=24×2+1
11^2=121=24×5+1 なのでいずれも24で割った余りは１である。

したがってa>3 である素数aについてa^2を24で割った余りは常に１である。

この回答への補足

なぜ12kなのですか?
(24は大変だから、でも理由の説明にはなりますが…)

補足日時：2013/09/07 18:09

No.5 回答者： naniwacchi 回答日時： 2013/09/07 14:44

#1です。

もしかして「a⇒6k±1」とは
「aが素数ならば、a＝ 6k±1と表せる。」という意味ですか？
この表現ではその意は汲み取れませんし、そもそも表現がなっていません。
（てっきり a＝ 6k±1（とおける）のことだと思ってました。）

素数を表す多項式はあるにはありますが、こんな簡単な形では表せません。
「素数ならば～である」ことを証明するときに、
・2の場合と3以上の奇数について成り立つことを示す
・3の倍数ではないことから、n＝ 3k±1とおいて成り立つことを示す

等として示すことはよくあります。

この回答への補足

トピックスと異なりますが…

ならば、という記号が⇒で表現でき、⇔が=と同意である、という意味で利用していました。

また、今回自分で解きながら、「こんなに簡単に素数が表現できるわけがないし、素数の予測は不可能なはず」というところで引っかかりを感じていました。

>>素数を表す多項式はあるにはありますが
知らなかったです。ちょっとぐぐったらAKS素数判定法とか出てきましたが、どちらにしろ人力では無理そうな感じですね。

補足日時：2013/09/07 17:42

No.4 回答者： ask-it-aurora 回答日時： 2013/09/07 13:45

ちょっと(無駄に)高級な解き方を書いてみます．解法自体は理解できるでしょうが，これを思いつくには中国剰余定理の証明を読んだことが無ければ難しいと思います．では…

まず24 = 3*8なのでa^2を3と8で割った余りを考えてみます．
a = 3q + r ⇒ a^2 = 3(3q^2 + 2qr) + r^2
なのでr^2 = 0^2, 1^2, 2^2 ≡ 0, 1(mod 3)のどちらかです．条件からaは3の倍数でないので結局余りは1です．同様に
a = 8p + s ⇒ a^2 = 8(8p^2 + 2ps) + s^2
なのでs^2 = 0^2, …, 7^2 ≡ 0, 1, 4 (mod 8)のいずれかです．条件からaは4の倍数ではないので結局余りは1です．

以上からa^2 = 3n + 1 = 8m + 1となるn, mがあることがわかりました．ここで1 = 2*8 - 5*3となることに着目して(!)
2*8*a^2 = 24*2n + 2*8,
-5*3*a^2 = 24*(-5)m -5*3
と上の式の両辺に適当に定数倍したあと，このふたつを足すと
a^2 = 1a^2 = (2*8 - 5*3)a^2
= 24*(2*n - 5*m) + 1
となります．したがってa^2を24で割った余りは1です．

## 愚直に余りの候補を24個挙げたあとに条件からどんどん絞っていってもこの場合はあまり手間ではないでしょうけどね．

No.3 回答者： cruelman 回答日時： 2013/09/07 13:44

a+1,a-1のいずれも２の倍数であることを証明する。

かつ、いずれか一つは４の倍数であることを証明する。
a+1,a-1のいずれかが３の倍数であることを証明する。

これが出来ればa^2-1が２４の倍数であることは自明です。


大まかな方針としては上記のとおりです。
具体的に証明を書き起こすのはわずらわしいでしょうが頑張ってください。

No.2 回答者： naniwacchi 回答日時： 2013/09/07 13:38

＞残るは6k±1ですが、

＞これは、「2でも3の倍数でもない」という条件を満たしただけで、素数である、
＞という条件を満たしたとは言えないのでは。

2の倍数でも3の倍数でもない数の集合と素数の集合では、包含関係はどうなりますか？
大きい集合で満たされることが言えれば、
その中に含まれている集合については成り立ちますね。

なので、「少なくとも～」と書いたのですが。

No.1 回答者： naniwacchi 回答日時： 2013/09/07 11:36

＞a⇒6k±1が証明できません。

というより、「a＝ 6k±1と表せる」ことの根拠ですよね。

素数であるためには、少なくとも「２の倍数でも、3の倍数でもない」数でなければなりません。
2の倍数でないのであれば、a＝ 2m±1と表され、
3の倍数でないのであれば、a＝ 3n±1と表されます。

ここから考えてみればよいかと。

この回答への補足

a=6k±1 はk=4で反例が出せると思いますが…
また、2の倍数でも3の倍数でもなければ、6の倍数ではあり得ず、また、6k,6K+2,6k+3,6k+4はいずれも2か3を法として0と合同なので、残るは6k±1ですが、これは、「2でも3の倍数でもない」という条件を満たしただけで、素数である、という条件を満たしたとは言えないのでは。

補足日時：2013/09/07 13:23