Quiz
Tomohiro Yamada
M_SHIRAISHI氏が最近クイズを投稿しないようなので
代わって私がクイズを出すことにしました.
話のネタにどうぞ.
問題:
整数n≧1に対して, P(n)をnの最大の素因数とする. このとき,
1. P(n^2+1)→∞(n→∞)を示せ.
2. n≧240ならばP(n^2+1)≧17となることを示せ.
3. P(n)≦7, P(n+1)≦7となる整数nを全て求めよ.
M_SHIRAISHI
Tomohiro Yamada wrote:
カカシ君、頑張ってますねぇ～。 ヽ(＾。＾)ノ
# 「継投」を有難う。 健闘を祈るよ。 ヾ(＾v＾)k
しかし、数論の問題には難問がいくらでも在り、そして
一般化が効かないケースが大半なので、よっぽどの
マニアは別として、「問題を解くのに費やす時間とか
労力のほうがもったいない」と思うのがフツーで、
多くの人の関心を引くのは難しいと思うが、どうか？
それと対照的に、「ベルトランの問題」などの場合は、
"猫"も"杓子"も興味を持つらしく、２ｃｈの ここ↓
http://science.2ch.net/test/read.cgi/math/1060617961/l50
では、御存知とは思うが、いまだにマヌケどもが
議論してるよ。 (^o^)
# まぁ、そこの連中などは「適当にあしらっておけば
いい」わけだが。 ヽ(^。^)ノ
Tomohiro Yamada
"M_SHIRAISHI" <eu...@apionet.or.jp> wrote in message
news:3F4794F0...@apionet.or.jp...
> しかし、数論の問題には難問がいくらでも在り、そして
> 一般化が効かないケースが大半なので、よっぽどの
> マニアは別として、「問題を解くのに費やす時間とか
> 労力のほうがもったいない」と思うのがフツーで、
> 多くの人の関心を引くのは難しいと思うが、どうか？
それもそうですね. 個人的にはM_SHIRAISHI氏の新理論に
基づく簡単な答えが来るのを期待していたのですが.
# 元の問題は実は比較的簡単な解法が存在するのですが,
一般の多項式については超越数論からの道具が
必要になるようです.
> それと対照的に、「ベルトランの問題」などの場合は、
> "猫"も"杓子"も興味を持つらしく、２ｃｈの ここ↓
>
> http://science.2ch.net/test/read.cgi/math/1060617961/l50
>
> では、御存知とは思うが、いまだにマヌケどもが
> 議論してるよ。 (^o^)
そちらの議論にはM_SHIRAISHI氏からの反論がないよう
ですが...
Tomhiro Yamada,
for the honor of the human mind
y6...@chive.ocn.ne.jp
Yuji Nomura
Tomohiro Yamadaさんの<bi1ebp$2tl$1...@nn-os104.ocn.ad.jp>から
> 問題:
> 整数n≧1に対して, P(n)をnの最大の素因数とする. このとき,
>
>1. P(n^2+1)→∞(n→∞)を示せ.
>2. n≧240ならばP(n^2+1)≧17となることを示せ.
>3. P(n)≦7, P(n+1)≦7となる整数nを全て求めよ.
3.の答を発見しました。
{1, 2, 3, 4, 5, 6, 7, 8, 9, 14, 15, 20, 24, 27, 35, 48, 49, 63, 80,
125, 224, 2400, 4374}
↓ここにあります。
http://www.math.niu.edu/~rusin/known-math/99/abc_easy
--
Yuji Nomura mailto:yno...@sam.hi-ho.ne.jp
Tomohiro Yamada
"Yuji Nomura" <yno...@sam.hi-ho.ne.jp> wrote in message
news:bid8cv$plb$1...@dojima-n0.hi-ho.ne.jp...
> 3.の答を発見しました。
>
> {1, 2, 3, 4, 5, 6, 7, 8, 9, 14, 15, 20, 24, 27, 35, 48, 49, 63, 80,
> 125, 224, 2400, 4374}
結論から言うと正解です. P(n), P(n+1)≦7となるnは上記の
数のみです.
さて, この結果を証明できるでしょうか?
> ↓ここにあります。
> http://www.math.niu.edu/~rusin/known-math/99/abc_easy
サイトの提示ありがとうございます.
GON
> 整数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では１つもありませんでした。ですから
これがないことを示し２，５，１３の３通りについて調べれば証明は完成する
と思います。
さぁ、どうやるんでしょうかね？
GON
> で、実際にMathematicaで次のような関数を作ってP(n^2+1)を調べてみたら
書き忘れました。以下です。
f[n_] := FactorInteger[n^2 + 1] ；n^2+1の素因数分解
P[n_] := Max[Flatten[Take[f[n], Length[f[n]], 1]]] ；n^2+1の素因数の中で最大のもの
で、n=1～300を調べてみた結果です。
Table[P[n], {n, 1, 300}]
{2, 5, 5, 17, 13, 37, 5, 13, 41, 101, 61, 29, 17, 197, 113, 257, 29, 13, 181,
401, 17, 97, 53, 577, 313, 677, 73, 157, 421, 53, 37, 41, 109, 89, 613, 1297,
137, 17, 761, 1601, 29, 353, 37, 149, 1013, 73, 17, 461, 1201, 61, 1301, 541,
281, 2917, 89, 3137, 13, 673, 1741, 277, 1861, 769, 397, 241, 2113, 4357,
449, 37, 2381, 29, 2521, 61, 41, 5477, 97, 109, 593, 1217, 3121, 173, 193,
269, 53, 7057, 3613, 569, 757, 1549, 233, 8101, 101, 1693, 173, 8837, 4513,
709, 941, 113, 29, 137, 5101, 2081, 1061, 373, 149, 661, 229, 2333, 457,
12101, 101, 193, 1277, 317, 389, 13457, 37, 557, 97, 14401, 7321, 229, 89,
15377, 601, 15877, 1613, 113, 157, 16901, 8581, 41, 61, 17957, 701, 349,
1877, 293, 9661, 1153, 9941, 109, 409, 233, 10513, 21317, 2161, 337, 653,
22501, 877, 4621, 2341, 641, 293, 24337, 29, 4993, 12641, 25601, 997, 181,
2657, 2069, 13613, 1621, 2789, 1129, 14281, 28901, 14621, 97, 73, 137, 15313,
30977, 241, 6337, 433, 32401, 16381, 53, 197, 33857, 157, 1193, 269, 7069,
337, 2777, 37, 101, 149, 617, 19013, 937, 3881, 7841, 19801, 181, 20201,
8161, 317, 41617, 21013, 42437, 857, 509, 21841, 44101, 197, 101, 349, 1117,
797, 97, 277, 1901, 23981, 1669, 24421, 9857, 4973, 50177, 1489, 3929, 5153,
281, 2017, 52901, 26681, 2153, 89, 3221, 521, 55697, 137, 11329, 13, 57601,
257, 53, 1181, 2053, 30013, 829, 6101, 12301, 1069, 62501, 109, 977, 173,
433, 61, 65537, 1321, 13313, 1973, 67601, 34061, 13729, 6917, 69697, 73, 409,
7129, 17, 373, 72901, 36721, 14797, 257, 389, 37813, 4481, 7673, 41, 38921,
78401, 3037, 3181, 8009, 80657, 2389, 521, 8237, 313, 41761, 2273, 3257,
17053, 101, 109, 821, 2137, 8821, 17761, 44701, 90001}
以上
Tomohiro Yamada
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)になります.
この結果は一般の円分多項式F_d(n)(d≧3)に拡張でき,
pがF_d(n)の素因数ならばp|dかつp≡1(mod q)（qは(q, p)=1となる
dの最大の約数）か、またはp≡1(mod d)であることが示されます.
（詳しくはNagell, Introduction to Number Theoryの
Theorem 94, 95を参照）
で, もとの問題ですが, ヒントを一つ.
n^2+1=2^e 5^f 13^g（e, f, gは非負の整数）とおくと,
n^2-Am^2=1（A, mは2, 5, 13のみを素因数にもつ整数）となります.
ここでLucas数列の整数論的性質を調べれば答えが出てくる
はずです.
GON
> "GON" <g...@mocha.freemail.ne.jp> wrote in message
> news:bj2ne0$m28$1...@news511.nifty.com...
> > "Tomohiro Yamada" <y6...@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。
「ある性質を満たすものが有限個しかない」なんて言われると何か神秘性を
感じちゃいますね。
っと、脱線しちゃった。（＾＾；）
Tomohiro Yamada
山田です. そろそろ答えを書くことにします.
定理
mを正の整数とする.
このときP(n^2±1)≦mを満たすnは有限個であり,
そのようなnは実効的に決定することができる.
証明
まず, t, u, Dを整数とし, 数列t_r, u_r（r=1, 2, ...）を
t_r+u_r.sqrt(D)=(t+u.sqrt(D))^r
を満足するものとします.
このとき(t+u sqrt(D))^r=Σ_{i=0}^{r} rCi.t^{r-i}.u^i.D^{i/2}より
u_r=Σ_{i=0}^{r} rC{2i+1}.u^{2i+1}t^{r-1-2i}.D^i,
ここでv_{ri}=rC{2i+1}.u^{2i+1}t^{r-1-2i} D^i(0≦i≦r)とおくと
u_r=v_{r0}+...+v_{rr} ...(1)
となります.
補題1. s>1が奇数でp≧5をp|Dとなる素数とすると,
m(p, ru)<m(p, rCs.u^s.D^{(s-1)/2})...(2)
が成り立つ.
（ここでm(p, x)はp^e|xとなる最大のe）
証明. m(p, r)=a, m(p, u)=bとおく. 明らかに
m(p, rCs.u^s.D^{(s-1)/2})≧m(p, rCs)+bs+(s-1)/2
=m(p, rCs)+s+(b+1/2)(s-1).
ここでm(p, s!)≦s/p+s/p^2+....=s/(p-1)より
m(p, rCs)=m(p, r!/{s!(r-s)!})≧m(p, r)-m(p, s!)≧a-s/(p-1).
よって
m(p, rCs.u^s.D^{(s-1)/2})≧a+b+(b+1/2)(s-1)-s/(p-1)
≧a+b+(s-1)/2-s/4≧a+b+1/4>a+b=m(p, ru). Q.E.D.
補題2. r≧3が奇数ならで, t^2-Du^2=±1ならば,
u_rはDを割り切らない素因数を持つ.
p|Dとすると, t^2=Du^2±1よりpはtを割り切らない. よって
m(p, ru)=m(p, rut^{r-1})=m(p, rC1.u.t^{r-1}D^{(1-1)/2}),
よってm(p, ru)=m(p, v_{r0}).
(2)よりi≧1ならばm(p, v_{r0})=m(p, ru)<m(p, v_{ri}).
よってv_{r0}=NM(NはDを割り切る素数の積, MはD
を割り切らない素数の積)と分解すると,
i≧1ならばN|v_{ri}かつ, p|D→p|v_{ri}/Nとなる.
したがって, (1)よりu_r=m(p, v_{r0})(M+L)（Lは
p|Dとなるすべての素数pで割れる整数)となる.
p|Dならば(p, M)=1かつp|Lなので, (M+L, p)=1.
他方, M+L≧1+1≧2なので, M+LはDを割り切らない
素因数を持つ. Q.E.D.
よって, t^2-Du^2=-1の最小の解をt_1, u_1とおくと,
u_r(r≧3は奇数)は常にDで割り切らない素因数を
もつことがわかります（-1を1に変えても同様）.
ですから, P(n^2+1)≦p_m（p_mはm番目の素数）
となるnすべてを決定するには, D=p_1^{e_1}...p_m^{e_m}
(e_i∈{0, 1, 2})となるすべてのDについてt^2-Du^2=-1の
最小解をすべてチェックすれば十分なことがわかります.
特に(1)の正しさがこれで証明されます.
例えば(2)を解くにはD=2, 5, 13, 2.5, 2.13, 5.13,
2.5^2, 2.13^2, 5.13^2, 2.5.13, 2^2.5.13, 2.5^2.13, 2.5.13^2,
2.5^2.13^2の14個の場合の最小の解を調べれば
十分であることが分かります(D|(n^2+1)より2^2|Dは不可能).
結局P(n^2+1)≦13を満たすnは1, 2, 3, 5, 7, 8, 18, 57, 239の
いずれかであることが示せるので, (2)が正しいことが
分かります.
また, t^2-Du^2=-1のかわりにt^2-Du^2=1を使うと
n^2-1の場合にも同様のことがわかります.
（ここまでで定理の証明は終わり）
4n(n+1)=(2n+1)^2-1より, n(n+1)についても同様のことが言え,
P(n), P(n+1)≦p_mを満たすnをすべて決定することが
できます.
P(n), P(n+1)≦7となるnをすべて決定するには
D=2^e.3^f.5^g.7^h(e, f, g, h∈{0, 1, 2}, e≠0, D≠N^2)を満たす
46個のDについてチェックすればよく,
nは1, 2, 3, 4, 5, 6, 7, 8, 9, 14, 15, 20, 24, 27, 35, 48, 49,
63, 80, 125, 224, 2400, 4374のいずれかであることがわかります.
なお, 今回の問題はC. Stoermer, Quelques theoremes sur
l'equation de Pell x^2-Dy^2=±1 et leurs applications,
Vidensk. Skrift. Mathem.-naturvid. Klasse. 1897. No. 2.
(48 p.p.)に遡る問題で, ここでP(n^2±1)≦Cを満たすnを
すべて決定する方法が記述されています.
（なお上記の証明はS. Chowla, The greatest prime factor
of x^2+1, J. London Math. Soc. 10(1935), 117-120に基づく
もので, この論文では上の方法と, Pell方程式の最小解の
大きさの上界をもちいてP(n^2+1)>Cloglognを証明しています）
一般に整数係数の多項式f(x_1, x_2, ..., x_n)に対して
P(f(x_1, x_2, ..., x_n))の大きさについて評価を与える問題は
非常に難しい問題で, n≧3の場合についてはほとんど
分かっておらず, n=2の場合も斉次式やax^p+by^qといった
特殊な形の多項式についてしか分かっていないようです.
上記のn^2±1に関する結果はこの問題に関する最初の
（部分的, かつ非自明な）結果のようです.
Tomohiro Yamada
"Tomohiro Yamada" <y6...@chive.ocn.ne.jp> wrote in message
news:bjpejl$23t$1...@nn-os102.ocn.ad.jp...
> また, t^2-Du^2=-1のかわりにt^2-Du^2=1を使うと
> n^2-1の場合にも同様のことがわかります.
と書きましたが, t^2-Du^2=1の場合の証明としては
不完全なので（3|Dの場合および補題2においてrが
偶数の場合を除外していたから）その場合について
証明します.
定理.
Dを正の整数, (t, u)をt^2-Du^2=1の最小の非自明解とし,
数列t_r, u_r（r=1, 2, ...）をt_r+u_r.sqrt(D)=(t+u.sqrt(D))^r
として定義する.
このとき, u_rのすべての素因数がDの約数ならr=1である.
補題1.
p|D, s>1が奇数かつI. p≧5, II. p=3, 9|D, III. p=3, 3|uのいずれかが
成立するなら
m(p, ru)<m(p, rCs.u^s.D^{(s-1)/2}).
（ここでm(p, x)はp^e|xとなる最大のe）
証明
I. p≧5
m(p, rCs.u^s.D^{(s-1)/2})≧m(p, rCs)+bs+(s-1)/2,
m(p, rCs)≧m(p, r)-m(p, s!)>a-s/(p-1),
よって
m(p, rCs.u^s.D^{(s-1)/2})>a+bs+(s-1)/2-s/(p-1)≧a+b+(s-1)(b+1/2)-s/4
≧a+b+(s-1)/2-s/4≧a+b.
II.p=3, 9|D
m(p, D)≧2よりm(p, rCs.u^s.D^{(s-1)/2})≧m(p, rCs)+bs+s-1,
m(p, rCs)≧m(p, r)-m(p, s!)>a-s/(p-1),
よって
m(p, rCs.u^s.D^{(s-1)/2})>a+bs+s-1-s/(p-1)≧a+b+(s-1)(b+1)-s/2
≧a+b+s-1-s/2≧a+b.
III.p=3, 3|u
m(p, rCs.u^s.D^{(s-1)/2})≧m(p, rCs)+bs+(s-1)/2,
m(p, rCs)≧m(p, r)-m(p, s!)>a-s/(p-1),
3|uよりb≧1, よって
m(p, rCs.u^s.D^{(s-1)/2})>a+bs+(s-1)/2-s/(p-1)≧a+b+(s-1)(b+1/2)-s/2
≧a+b+3(s-1)/2-s/2≧a+b. （補題の証明終）
よってI. II. III.のいずれかの条件が満たされる場合は
rが奇数の場合: 元記事と同様にして定理が証明される.
rが偶数の場合: t|u_r, (t, D)=1, t>1より定理が証明される.
残るのはp=3, 3||Dかつ3がuを整除しないときのみだが,
rが偶数ならt|u_r, (t, D)=1, t>1よりu_rについて定理は明らか.
よってu_r(r: 奇数, r>1)について定理を証明する.
D_1=D/3, D'=9Dとおく.
u_r=rut^{r-1}+D(v_{r1}+...)より3|rならば3|u_r.
よってt_{3n}, u_{3n}/3はt^2-D'u^2=1の解である.
逆に(t, u)がt^2-D'u^2=1の解ならば, (t, 3u)はt^2-Du^2=1の解,
3はuを整除しないのでt^2-D'u^2=1の解は(t_{3n}, u_{3n}/3)で与えられる.
(t, u, D)=(t_3, u_3/3, D')は補題1の条件IIを満たすので
u_{3n}(n>1)については定理は正しい.
mが3で割れない奇数のとき, u_mも3で割れない. なぜならu_mが
3で割れるなら(t_m, u_m/3)はt^2-D'u^2=1の解となるが, これは
mが3で割れないことに反するからである.
p>3は補題1の条件Iを満たすので, 元記事と同様にして
u_mはD_1を割り切らない素因数を持つことが分かる. u_mは3で
割れないので, u_mはDを割り切らない素因数を持つ.
残ったu_3の場合を確かめる. u_3の素因数が常にDを割り切ると
仮定すると,
t^2=Du^2+1より(t, D)=1, u_3=3u(t^2+D_1u^2)よりt^2+D_1u^2=1,
これは明らかに矛盾である.
これによって, 定理が証明された. Q.E.D.
Tomohiro Yamada
"Tomohiro Yamada" <y6...@chive.ocn.ne.jp> wrote in message
news:bj6l6h$3f4$1...@nn-os105.ocn.ad.jp...
>n^2+1=2^e 5^f 13^g（e, f, gは非負の整数）とおくと,
>n^2-Am^2=1（A, mは2, 5, 13のみを素因数にもつ整数）となります.
>
>ここでLucas数列の整数論的性質を調べれば答えが出てくる
>はずです.
と書きましたが, 実際にはPell方程式の解のなす数列の
整数論的性質に基づいた証明です.
# Pell方程式の解のなす数列は実質的にはLucas数列の特殊な
場合に該当しますが, 証明においてはLucas数列の性質だけ
では不足するところが出てきます. たとえば3||Dで3がuを
整除しない場合の証明はPell方程式の理論にかなり依存
しています.
この点, 表現に不適切な点がありましたのでお詫びの上,
訂正します.
なお, 一般のLucas数列の性質についても数多くの研究が
なされていますが未だに良く分かっていないことが多いようです.