"Tomohiro Yamada" <y64k@chive.ocn.ne.jp> wrote in message news:bj6l6h$3f4$1@nn-os105.ocn.ad.jp...
> "GON" <gon@mocha.freemail.ne.jp> wrote in message
> news:bj2ne0$m28$1@news511.nifty.com...
> > "Tomohiro Yamada" <y64k@chive.ocn.ne.jp> wrote in message
> news:bi1ebp$2tl$1@nn-os104.ocn.ad.jp...
> > > 　整数n≧1に対して, P(n)をnの最大の素因数とする. このとき,
> > > 2. n≧240ならばP(n^2+1)≧17となることを示せ.
> >
> > 証明はわかりませんが、この対偶をとって
> >
> > 「P(n^2+1)<17ならばn<240」
> >
> > を示せばよい感じはします。言い換えれば
> >
> > 「P(n^2+1)≦13ならばn<240」
> >
> > ですね。１３以下の素数は２、３、５、７、１１、１３の６通りしかありません
> > から場合分けをして調べれば証明できそうな気はします。
> >
> > で、実際にMathematicaで次のような関数を作ってP(n^2+1)を調べてみたら
> > P(n^2+1)=3,7,11を満たすnはn<240では１つもありませんでした。
> 
> 　実際, n^2+1の素因数は2か4m+1に限られることが証明できます.
> （平方剰余の第一補充法則）
>  実際p≠2をp|(n^2+1)となる素数とするとn^2≠1, n^4≡1(mod p)
> となるので、nのmod pにおける位数は4ですから, Fermatの定理
> より4|(p-1)になります.

なるほど。

当方、数論は専門でないのであまりよく知りません。フェルマーの小定理や原始根
あたりはちょっと読んだ程度で知ってますが具体的な証明問題などはあまりフォロー
してません。

和田秀男著「数の世界」岩波書店

を見返してみたら上の定理がありました。２次合同式の話なんですね、これって。
「平方剰余の相互律」がキーワードなのかなぁ。

そこらへんを勉強しとくと簡単に証明できるようになるんでしょうか？

> 　で, もとの問題ですが, ヒントを一つ.
> 
> n^2+1=2^e 5^f 13^g（e, f, gは非負の整数）とおくと,
> n^2-Am^2=1（A, mは2, 5, 13のみを素因数にもつ整数）となります.
> 
> ここでLucas数列の整数論的性質を調べれば答えが出てくる
> はずです.

Lucas数列なんて数論やってる人間でないとわからない知識ですね。
それらにはいろいろな性質があるんでしょうね。勉強になります。

でも、数論って先の本を読み返してみると結構面白いですね。

ある数を７で割ったときの余りの計算例が先の本に載ってましたが結構
目から鱗です。ポイントは７×１１×１３＝１００１になることを利用して
３桁ごとに計算するってことです。

つまり、

７×１１×１３＝１００１≡０　（Ｍｏｄ７）

ですから

１０＾３≡−１　（Ｍｏｄ７）

これを利用して任意の数を３桁ごとに１０進展開すると、例えば

８２５９３６３７８
＝８２５×（１０＾３）＾２＋９３６×１０＾３＋３７８　（Ｍｏｄ７）
≡８２５×（−１）＾２＋９３６×（−１）＋３７８　（Ｍｏｄ７）
＝８２５−９３６＋３７８　（Ｍｏｄ７）
＝２６７　（Ｍｏｄ７）
≡１　（Ｍｏｄ７）

こんな感じで任意の数を３桁ごとに交互に足したり引いたりして
出てきた数を７で割れば余りが求まります。

７×１１×１３でしたから１１や１３で割った余りを求めるのも
同じ方法でできます。

それとＭｏｄを使って簡略化される計算ってＦＦＴ（高速フーリエ変換）にも
使われてますよね。

数論って初歩的なものは結構理解しやすくて神秘性を感じさせるものが
ありますね。２ｃｈとかに出てたＱ（√（−１６３））の性質とか素数を出す式で
p(n)=n^2+n+41がn=0〜39のすべてで素数を出すこととＱ（√（４１））の性質が
関係しているとか、etc。

「ある性質を満たすものが有限個しかない」なんて言われると何か神秘性を
感じちゃいますね。

っと、脱線しちゃった。（＾＾；）