kadai78

平成２１年１１月２２日

[流れ星]

　　　　　第２３３回数学的な応募問題

　　　　　　＜解答募集期間：11月22日～12月13日

［６ｎー１の素数］

皆さん、今年の千葉大学入試問題の中で、素数の関する問題がありました。

（１）５以上の素数は、ある自然数ｎをも用いて６ｎ＋１または６ｎ－１の形に表されることを示せ。

（２）Ｎを自然数とする。６Ｎ－１は、６ｎ―１（ｎは自然数）の形で表される素数を約数にもつことを示せ。

（３）６ｎ―１（ｎは自然数）の形で表される素数は無限に多く存在することを示せ。

NO1「uchinyan」 11/22 16時15分受信更新12/13

第２３３回数学的な応募問題
［６ｎー１の素数］

(1)
4 以上の整数は，必ず，n を自然数として，6n-2，6n-1，6n，6n+1，6n+2，6n+3 と表せますが，
5 以上の素数は，2 の倍数でも，3 の倍数でもないので，必ず，6n-1 又は 6n+1 の形になります。

(2)
6N-1 が 6n-1 型の素数を約数もたないとします。
すると，(1)より，6n+1 型の素数だけを約数，素因数，にもつことになりますが，一般に，
(6k+1)(6m+1) = 6(6km+k+m)) + 1
となり， 6n+1 型の素数をいくら掛けても 6 で割って +1 余る数しかできず，6N-1 型の整数になりません。
そこで，少なくとも 1 個，一般には奇数個，の 6n-1 型の素因数，つまりは約数，を必ずもつことになります。

(3)
6n-1 型の素数が有限個しかないとします。そして，それらの積を N とします。N はもちろん自然数です。
ここで，6N-1 という整数を作ると，有限個のどの 6n-1 型の素数で割っても，N を割り切ってしまい，
6N-1 自体を割り切ることはありません。
ところが，(2)より，6N-1 は 6n-1 型の素数を必ず約数にもちます。
これは矛盾です。
したがって，6n-1 型の素数は無限個あることになります。

(考察)
6n+1 型の素数に関しては，少なくとも，上記の方法では有限個か無限個か分からないようです。
6n-1 型の素数を偶数個掛けると 6n+1 型の整数になってしまうので。
少し考えてみたのですが，こんな感じでどうでしょうか。

6n+1 型の素数が有限個しかないとします。そして，それらの積を N とします。N はもちろん自然数です。
ここで，(6N)^3 + 1 という整数を作ると，有限個のどの 6n+1 型の素数で割っても，N を割り切ってしまい，
(6N)^3 + 1 自体を割り切ることはありません。
ここで，もし，(6N)^3 + 1 自体が素数ならば，
(6N)^3 + 1 = 6 * (6^2 * N^3) + 1 > N > 既存の 6n+1 型の素数
で，新たな 6n+1 型の素数になり，6n+1 型の素数が有限個であったことに矛盾します。
(6N)^3 + 1 自体が素数でない場合は，(6N)^3 + 1 が p という素因数をもつとします。明らかに p は 5 以上です。
すると，mod p で考えて，
(6N)^3 + 1 ≡ 0
(6N)^3 ≡ -1
(6N)^6 ≡ +1
ここで，p が 6N を割り切ることはないので，p が素数であることから，p と 6N は互いに素となり，
フェルマーの小定理から，
(6N)^(p-1) ≡ +1
このことと先ほどの式から，q を 0 以上の整数，r を 0 <= r <= 5 の整数，として，
p-1 = 6q + r
(6N)^(p-1) ≡ +1
(6N)^(6q + r) ≡ +1
((6N)^6)^q * (6N)^r ≡ +1
1 * (6N)^r ≡ +1
(6N)^r ≡ +1
・r = 0 の場合
(6N)^0 ≡ +1
p-1 = 6q，p = 6q + 1
これは，OK。
・r = 1 の場合
(6N)^1 ≡ +1
(6N)^3 ≡ +1
これは，(6N)^3 ≡ -1 と矛盾するので，不可。
・r = 2 の場合
(6N)^2 ≡ +1
p-1 = 6q + 2，p = 6q + 3
p は 5 以上の素数でなければなりませんが，そのような p は存在しません。
・r = 3 の場合
(6N)^3 ≡ +1
これは，(6N)^3 ≡ -1 と矛盾するので，不可。
・r = 4 の場合
(6N)^4 ≡ +1
p-1 = 6q + 4，p = 6q + 5
その一方で，
(6N)^2 ≡ (6N)^2 * (6N)^4 ≡ (6N)^6 ≡ +1
つまり，r = 2 の場合にも帰着してしまい，p = 6q + 3 にもなります。
このような p は存在しません。
・r = 5 の場合
(6N)^5 ≡ +1
p-1 = 6q + 5，p = 6q + 6
p は 5 以上の素数でなければならないので，不可。
結局可能なのは，p = 6q + 1 の場合だけです。
つまり，(6N)^3 + 1 は 6n+1 型の素数で割り切れます。
これは，既存のどの 6n+1 型の素数も (6N)^3 + 1 を割り切らなかったことに矛盾します。

以上より，6n+1 型の素数は無限個あることがいえました。

(感想)
これは，有名な，ユークリッドによる素数は無限個あることの証明の類似版ですね。
誘導形式になっているので，考えやすかったです。

NO2「kashiwagi」 11/25 07時33分受信更新12/13

233回解答

（1）

ｎの値に応じた表を作成すると確かに素数はこの2タイプで表される。但し、黄色で塗りつ

ぶした数値は素数ではない。

（2）上表より、各々の素数は自らを約数にもつので条件を満たしている。問題は素数で無いものだが、35＝5×7、65＝5×13、77＝7×11、95＝5×19、119＝7×17、161＝7×23・・・・というように6ｎ-1タイプの素数5、11、17、23・・・を約数に持つことが分かる。

（3）このタイプの素数が有限だとすると、一番大きな素数が存在する。その素数をＡとし、このタイプの素数全ての積をＢとすると、

Ｂ＝5×11×17×23×・・・・・・・×Ａと表せる。ここで、Ｂに1を加えた数をＣとすると、

Ｃ＝5×11×17×23×・・・・・・・×Ａ＋1となる。

このＣは5,11,17・・・・Ａのどの数でも割り切れず、1余る。即ち、Ｃはこれら素数の約数ではない。即ち、Ｃは素数であり、Ｂより大きな数となる。これは最大の素数はＡであるという前提と矛盾する。因って、6ｎ-1タイプの素数は無限に存在する。

NO3「ｽﾓｰｸﾏﾝ」 12/02 22時59分受信更新12/13

お久しぶりです ^^;
今回は手が出そうだったので...トライします Orz～

（１）５以上の素数は、ある自然数ｎをも用いて６ｎ＋１または６ｎ－１の形に表さ
れることを示せ。

素数を含めたあらゆる5以上の数は、
6n
6n±1
6n±2
6n±3
のいずれかで表わされる...
が...
素数とすると...
明らかに...6n±1 の形でしかありえない。

（２）Ｎを自然数とする。６Ｎ－１は、６ｎ―１（ｎは自然数）の形で表される素数
を約数にもつことを示せ。

5以上の自然数 6N-1 は、(1)から...合成数なら...あらゆる5以上の素数が 6n±1 で
表わされるのだから...
それらの素数の積で表わされる。6n+1 だけの積では...6N+1 になるので...奇数個の
6n-1
型の素数を因子に持つことが言える。

（３）６ｎ―１（ｎは自然数）の形で表される素数は無限に多く存在することを示せ
。

有限のm個しかないとすると...
(6n_1-1)(6n_2-1)・・・(6n_m-1)-1 という数は...
(2)から...6n-1 という素因数を少なくとも1個 or 奇数個持っているはずだが...
それは、6n_1-1～6n_m-1 の m個の素数ではないので...
新しい素数ということになり...これは有限のm個しかないことに矛盾する。
つまり...6n-1 型の素数は無限であるといえる。

ユークリッドさんの素数の無限の証明法の踏襲ですね...^^;v

今年もカウントダウンとなりましたが　少し早いけど...よいお年をお迎えください
ませ～^^
来年もできるだけチャレンジしたいと思います m(_ _)mγ
また、よろしくお願いいたします～～～♪