◆愛知県 重永 大介 さんからの解答。
(１)
問題の等式を変形して
Ａn+1−１＝(Ａn−１)× Ａn
Ａn−１＝(Ａn-1−１)× Ａn-1
Ａn-1−１＝(Ａn-2−１)× Ａn-2
・
・
Ａj+1−１＝ (Ａj−１)× Ａj
両辺をそれぞれかけた後、
(Ａn-1ー１)×(Ａn-2ー１)× ･･･×(Ａj+1ー１)で両辺を割って
(p≧2，Ａnは単調増加列なので、これは０ではない)
Ａn−１＝(Ａj−１)× Ａn-1× Ａn-2× ･･･ × Ａj
Ａn＝((Ａj−１)× Ａn-1× Ａn-2× ･･･ Ａj+1)× Ａj ＋１
よって、ＡnをＡjで割ったときの余りは１である。
(２)
(１)より Ａn＝ｋ×Ａj＋１と書ける。
最大公約数をｍとすると
Ａn＝ｍ×ａ、Ａj＝ｍ×b、(ａ，ｂは互いに素)と書ける。
ｍ×ａ＝ｋ×ｍ×b＋１
(ａ−ｋ×b)× ｍ＝１
ｍ≧１だから、ａ−ｋ×b＝１，ｍ＝１
となり、ＡnとＡjの最大公約数は１である。
(３)
Ａ1、Ａ2、･･･を素因数分解すると、
各Ａnに対し少なくとも１つの素数が対応している。
しかも(２)よりこれらの素数はすべて異なる。
不等式でいえば、Ａ1、Ａ2、･･･ Ａn までを考えると
(Ａ1、Ａ2、･･･ Ａnを素因数分解して出てくる素数の数)≧ｎ
Ａnは無限にあるのだから素数も無限にある。
<コメント>
はじめこの問題を見て、「Ａ1が素数なら、すべてのＡnは素数になる」ことが証明できると勘違いしていました。
もしこんな数列が発見されたのなら大変なことですよね。
(2)で多くの記号を使ったのが悔やまれます。
もっときれいな解答がありそうです。
証明を見やすくするため、いちいち正であることや整数であることを断りませんでした。
【コメント】
非常に巧妙な証明ですね。
ソ連のマチアセビッチは１９７１年に全ての素数を生み出す式を完成したそうですが、コメントを読んでふとそのことを思い出しました。
１９変数の多項式で、１９個の任意の自然数を代入したときに、値が正の数の場合は素数になるそうです。
もし詳しい方がおいでたら教えてください。
◆東京都の中学校１年生 安里歩安彼 さんからの解答。
（１）答え：１
帰納法で示しましょう。
まず、An+1＝An2-An+1≡１(mod An)
さて、An+kまで示されているとして、
An+k+1
＝An+k2-An+k＋１
≡１×１−１＋１≡１（mod An)
となって、示された
（２）１より直ちに、最大公約数は１とわかる。
（３）問題で構成されている数列の、任意の二つの項は互いに素である。
しかし、素数が有限個しかないと、どの２つをとっても互いに素であるような集合の要素の数は高々有限個にとどまるので示された。
◆京都府 新庄 さんからの解答。
素数が有限であると仮定し、その最大のものをNとする。
ａ、b、cを自然数とした場合、すべてのａについて
Ｎ＋ａ＝b＊cとなるｂ、ｃが存在する。
この式を変形すると
Ｎ＝ｂ＊ｃ−ａとなる。
ところがａ＝ｂの場合、ａはＮの約数となり最初の仮定と矛盾する。
よって素数は無数にある。
◆京都府 ＹＯＳＹ さんからの解答。
素数が有限であると仮定し、その最大のものをＮとする。
この場合、すべての自然数Ｘに対して
Ｎ＋Ｘ＝ＹＺを満たす自然数解Ｙ,Ｚ(ともに≧２)が存在しなければならない。
Ｎ＋Ｘ＝ＹＺの解は、ＹＺ軸上に
（Ｙ,Ｚ)＝（√(Ｎ＋Ｘ),√(Ｎ＋Ｘ)）を頂点とする
双曲線を形成する。
Ｙ,Ｚの値は頂点を中心に対称形になるので、
調べるべきＹ,Ｚの
値は２以上、√(Ｎ＋Ｘ)以下の自然数であり
Ｙ＝２…Ｚ＝(Ｎ＋Ｘ)/２
Ｙ＝３…Ｚ＝(Ｎ＋Ｘ)/３
：
となる。
これから判るように、ＸがＮの倍数となる場合は自然数解が存在する。
したがってこれ以外の場合について自然数解の存在を確認すればよい。
いま、Ｎ＋ＸをＸ−Ａで割った余りを考えてみる。
ここでＡは０以上Ｘ未満の整数
とする。
したがってＸ−Ａは１以上Ｘ以下の自然数となる。
√(Ｎ＋Ｘ)の値は、ＸがＮよりも充分に大きい場合においてＸよりも小であるから、
調べるべきＹ,Ｚの値を含んでいる。
剰余定理により
Ｆ(Ｘ)＝Ｎ＋ＸをＸ−Ａで割った余りは、Ｆ(Ａ)＝Ｎ＋Ａとなる。
したがって、自然数解が存在するためには、Ｎ＋Ａ＝０となる必要がある。
これはＡ＝−Ｎであることを意味し、０≦Ａ＜Ｘの範囲では、すべての自然数Ｘに
対する自然数解は存在しない。
したがって、素数が有限であるという仮定は誤りである。