クイズ大陸



履歴 検索 最新 出題

No. 3≫ No.4 ≫No. 5
?ゲーデル 2010/09/10 21:06
[解答]
一般に、p を p≡3 (mod 4) 型の素数とした時、p-1 個の連続した整数の積が
正の平方数にならないことを示す。
-----------------------------------------------------------------------------------------
任意の整数 n から始まる連続する p-1 個の整数の集合を G とする。
また、a = Πj∈G j とする。

G に 0 が含まれる場合、a = 0 なので、正の平方数にはならない。
G が全て正である場合に示すことができれば、G が全て負の場合も
同様に示せるので、以下、n>0 について考える。

Case1. G の中に p の倍数が含まれる場合
p の倍数は G に 1つしか含まれないため、a は p を素因子に1つしか含まず、
平方数になることはない。

Case2. G の中に p の倍数が含まれない場合
G の元は、法p の下で 1,...,p-1 (mod p) であるので、
[Wilson の定理] より、 a ≡ (p - 1) ! ≡ -1 (mod p)
さて、仮に a = s2 なる 正整数 s が存在したとする。
s と p も互いに素である。この時、p=4n+3 として、
sp-1=s4n+2=(s2)2n+1=a2n+1≡(-1)2n+1≡ -1 (mod p)
であるが、これは [Fermatの小定理] に反する。
-----------------------------------------------------------------------------------------

ちなみに、2011 は 素数で 2011≡3 (mod 4) なので、
2010個の連続した整数の積は、平方数にならないことがわかる。

===================================


*[Fermat の小定理] p が素数で p と s が互いに素 ⇒ sp-1≡1 (mod p)
[簡易証明]
G={1,...,p-1} とする。G の各元に s を掛ける操作は、法p の下で G の置換になる。
よって、置換前後の G 全体の積は法p の下で等しく、
(p-1) ! ≡sp-1 (p-1) ! (mod p) 。p と (p-1) ! は互いに素なので 1≡sp-1 (mod p)

*[Wilson の定理] p が素数 ⇔ (p-1) ! ≡ -1 (mod p)
[簡易証明]
1,...,p-1 の中で、x ≡ x-1 (mod p) を満たすのは 1 と p-1 のみ。
従って、(p-1) ! は、1 と p-1 以外は打ち消しあって p-1 ≡ -1 と等しくなる。
逆に関して。pが素数でない時、p の真の約数d が 1,...,p-1 に含まれるので、
d も p も (p-1) !+1 の約数はならない。

* a = Πj∈G j は、具体的には n(n+1)...(n+p-2) の事です。
  Σは和(Sum)を表しますが、Πは積(Product)を表します。

* a≡b (mod c) は、a - b が c で割り切れる事を表します。

*2011が素数であることは、2011が√2011=44.8.. 以下の素数
  2,3,5,7,11,13,17,19,23,29,31,37,41,43
 で割り切れないことでわかります。

*ヒント3 は、Wilson の定理 , ヒント5 は、Fermat の小定理
 ヒント4 は、2以外の素数p は、p≡1 (mod 4) と p≡3 (mod 4) しかない事,
 ヒント1,2 は、素数 2011 と素数 7 が p≡3 (mod 4) の素数である事。



★質問があればお気軽にどうぞ★

とりあえずこの問題の解答だけ・・・。一般的な解答の話は明日くらいに
大雑把な方針だけ、元のスレのコメントで説明予定です。

証明に欠陥が見つかったため、少々お待ちくださいm(_"_)m
問題は、Case 1) です。適当に考えてました。
p の偶数乗が因子の時の事を考えなくてはいけません。
大がかり的な事しないと、ダメかもしれない・・・



:追記:(9/14)
えーっと、土曜・日曜と、ちょっと急用が入って手が付けられなかったので、
昨日の夜、一生懸命解答を作り直してました。 (^^;)
で、今夜(深夜かも)に、解答を、>>6 で改めて出します。
色々簡単に出来ないか考えたんですけど、難しかったので、
(というか、Erdosの証明が頭にこびり付いて、考える方向がErdos寄りに・・・)
結局ErdosやSeimatsu のやり方を踏襲する事にしました。(-へ-;)

編集