◆大阪府 らぶりぃナナちゃん さんからの解答。
a+1が合成数の時、a+1=x*yとすると、
GDC(a+1-x,x)=x＞1より、条件を満たさない。
a+1が素数で、あるIに対してGDC(1+I,a-I)=g＞1とすると、
J=1+Iとして、g=GDC(J,a+1-J)=GDC(J,a+1)
ところで、a+1は素数だからg=1 or a+1であるが、
g＞1であり、かつJ＜1+I＜a＜a+1より、矛盾。
よって、a+1が素数の時、かつその時のみ条件を満たす。
◆広島県の高校生 おってい さんからの解答。
ａが１でない奇数のとき、２ｎ+１(ｎは自然数)とすると
i=ｎのとき（ｎ＋１、ｎ＋１）となって不適。
よってａは偶数で２ｎ（ｎは自然数）とする。
ａが条件を満たすかどうかを調べるには、ｉは０からｎ−１としてよい。
（なぜならｉを大きくしていっても同じ組が得られるのみである）
このとき一般的な組は（２ｎ−ｉ、１＋ｉ）と表されるが
ｋ＝１＋ｉ とすると（２ｎ＋１ーｋ、ｋ）で表せる。
しかしユークリッドの互除法により
ＧＣＤ（２ｎ＋１−ｋ、ｋ）＝ＧＣＤ（２ｎ＋１、ｋ）であるから、
１からｎまでが２ｎ＋１までが互いに素であればよい。
条件を満たすときエラトステネスの篩により２ｎ＋１は素数である。
逆に２ｎ＋１が素数のとき、条件を満たす。
よってａの条件は「素数ー１」である。
◆茨城県 こんにちは さんからの解答。
i+1とa-i(i = 0,1,…, a-1)がすべて互いに素となるための必要十分条件は
a+1が素数である事である。
a+1が素数のとき
i+1とa-iの最大公約数をdとおくと
i＋1=d*s，a-i=d*t (s,tは整数)
よってa+1=d*(s+t)
a+1は素数だからd=a+1あるいは1
d=a+1と仮定すると
a-i=(a+1)t
| よってt= | a-i a+1 | となるが |
| 0＜ | a-i a+1 | ＜1より0＜t＜1となって不合理 |
よってd=1となる。
これはi+1とa-iは互いに素である事を意味する。
よって、a+1が素数のときi+1とa-i(i = 0,1,…, a-1)がすべて互いに素となる
a+1が合成数のとき
a+1=b*c(ただしb,cはb,c＞1を満たす自然数)と書ける
i=c-1とおくとi+1=c=1*c
a-i=a+1-c=b*c-c=(b-1)*c
よってi=c-1のときi+1とa-iは1より大きい公約数c(＞1)を持つ
i+1とa-i(i = 0,1,…, a-1)がすべて互いに素とはならない。
◆東京都 かえる さんからの解答。
ｉ＋１とａ−ｉが互いに素（ｉ＝０,１,・・・,ａ−１）
⇔
ｉ＋１と（ｉ＋１）＋（ａ−ｉ）＝ａ＋１が互いに素
（ｉ＝０,１,・・・,ａ−１）
⇔
ａ＋１と１,２,・・・,ａが全て互いに素
⇔
ａ＋１が素数・・・【答】
◆千葉県の高校生 Playcity さんからの解答。
予想：ａは素数−１
両辺の和が一定であるから、以下のように証明する。
ただし、２つの数とは、ｉ＋１、ａ−１を示す。
@）ａが素数−１⇒互いに素
両辺の和はａ＋１だから、ａが素数−１のとき、２つの数の和は素数である。
このとき、２つの数が互いに素でないように分解できると仮定すると、
それらの２つの数は同じ数ｋ（ｋ≧２）を因数にもつことになり、ある自然数ｍ、ｎを用いて
ｋｍ、ｋｎと分解できる。
この２つの数の和はｋ（ｍ＋ｎ）となり、明らかに両辺の和が素数であるという仮定に反するから、常に互いに素となる。
つまり、２つの数の和が素数、すなわちａが素数−１のとき題意を満たす。
A）ａが素数−１でない⇒互いに素にはできない
２つの数の和はａ＋１だから、ａが素数−１でないとき、２つの数の和は合成数である。
このとき、両辺の和を２つの２以上の自然数ｍ、ｎを用いて
ａ＋１＝ｍｎと示せる。
このときｎ≧２だから、必ずｍ、ｍ（ｎ−１）と分解することが可能だから、２つの数の和が合成数、
すなわちａが素数−１でないときは、ｍ（ｍ≧２）を因数にもち、題意は明らかに満たせない。
Ｑ．Ｅ．Ｄ．
◆岩手県 utu さんからの解答。
条件を満たす必要充分条件は「ａ＋１が素数である」
以下証明
２数の和は必ずａ＋１になる。
この２数を「ａ＋１の二分割数」と呼ぶことにする。
【必要性について】
ａ＋１が素数でないならば、素数ｐと２以上の整数ｂを用いて
ａ＋１＝ｂｐ
と表される。
すると、
ｐ，（ｂ−１）ｐ
という二分割数が存在し、これは互いに素ではない。
したがって、ａ＋１が素数である必要性が示された。
【十分性について】
ａ＋１が素数のとき、二分割数の中に互いに素でないものが存在するならば、その二分割数は素数ｐと２以上の整数ｂ、ｃを用いて、
ｂｐ，ｃｐと表される。
この二数の和がａ＋１なので、ａ＋１が素数であることに反する。
したがって、ａ＋１が素数であれば、二分割数はすべて互いに素である。
よって十分性が示された。
ａについて考えてると、訳判りませんが、＋１したら明解でした。
◆東京都 T.Kobayashi さんからの解答。
a+1 が素数の時、またその時に限って「全て互いに素」となる。
a+1 が素数のとき、i + j = a+1 として、(i, j) = d ＞ 1 とすると、
1 ＜ d＜ a+1 で、d|a+1 となって a+1 が素数であることに矛盾する。
よって「全て互いに素」。
全て互いに素のとき、a+1 = p * q (p, q > 1) が合成数とすると、
p(q-1) + p = a+1 で、gcd(p(q-1), p) = p ＞1 となって矛盾する。
よって a+1 は素数である。
# a+1 ≧ 2 だから a+1 は素数か合成数かのどちらかです。
◆出題者のコメント
たくさんの解答ありがとうございます。
みなさん正解だと思います。
特にかえるさんの解答が簡潔でわかりやすかったです。
らぶりぃナナちゃんさん、おっていさんの解答も同様にi+1とa+1に着目するアプローチですね。
これに対し他のみなさんはより直接的な証明という感じでしょうか。
私も出題後に以下のように解きました。
十分性)
「2数の和((i+1)+(a-i)=a+1)が素数ならば、どのiに対しても2数が互いに素」の対偶
「あるiに対して2数が共通因数を持つならば、2数の和(a+1)は合成数」を示す。
必要性)
「2数の和(a+1)が合成数ならば、互いに素ではない2数を選べる」ことを示す。
対偶を使うまでもなかったですね。
我ながら回りくどいことをしたものです。
しかも必要性の証明が必要なことを友人に指摘されるまで気付かないというお粗末さでした…。
ちなみにこの問題、有理数の集合と自然数の集合の濃度が等しいことを説明するときに使う有理数を2次元に並べた表をExcelで作っていて、
既約分数が斜めに途切れずに並んでいるのを見て思いつきました。