『高校生からの挑戦状Part18』解答

◆東京都　かえる さんからの解答。

【問題２】

（１）ｐ＝２のとき

（Ｓの全元の和）＝

ｋ（Ｋ＋１） ２

が２の倍数であることが必要なので、

ｋ≡−１、０（ｍｏｄ４）が必要

ｋ＝３のとき　（１，２）（３）
ｋ＝４のとき　（１，４）（２，３）

と題意の分割ができる。

また、ｋ＝ｎで題意の分割が可能ならば、
（ｎ＋１，ｎ＋４）（ｎ＋２，ｎ＋３）をそれぞれの部分集合に加えることにより、
ｋ＝ｎ＋４のときも題意の分割が可能となる。

従って、ｋ≧３　∧　ｋ≡−１、０（ｍｏｄ４）で十分

以上より、ｋ≧３　∧　ｋ≡−１、０（ｍｏｄ４）・・・（答）

（２）ｐ≠２のとき

（Ｓの全元の和）＝

ｋ（Ｋ＋１） ２

がｐの倍数であることが必要なので、

ｐが２でない素数であることから、ｋ≡−１、０（ｍｏｄｐ）が必要

ｋ＝ｐ−１、ｐのとき題意の分割ができないことは明らか。

ｋ＝２ｐ−１のとき
　（１，２ｐ−２）（２，２ｐ−３）・・・・（ｐ−１，ｐ）（２ｐ−１）

ｋ＝２ｐのとき　
（１，２ｐ）（２，２ｐ−１）・・・（ｐ，ｐ＋１）

ｋ＝３ｐ−１のとき　

（３ｐ−１，

３ｐ−１ ２

）（３ｐ−２，

３ｐ−１ ２

＋１）・・・

ｋ＝３ｐのとき　

（３ｐ，

３（ｐ＋１） ２

）（３ｐ−１，

３（ｐ＋１） ２

＋１）・・・

と題意の分割ができる。

また、ｋ＝ｎで題意の分割が可能ならば、
（ｎ＋１，ｎ＋２ｐ）（ｎ＋２，ｎ＋２ｐ−１）・・・（ｎ＋ｐ，ｎ＋ｐ＋１）をそれぞれの部分集合に加え ることにより、
ｋ＝ｎ＋２ｐのときも題意の分割が可能となる。

従って、ｋ≧２ｐ−１　∧　ｋ≡−１、０（ｍｏｄｐ）で十分

以上より、ｋ≧２ｐ−１　∧　ｋ≡−１、０（ｍｏｄｐ）・・・（答）

◆千葉県　永山　祐介 さんからの解答。

【問題１】

おそらく、整数となるのは n = 3 の場合のみだと思います。
証明は途中までですが、いくつかの条件で整数になりえないことの証明を送ります。
あとは主に合成数の場合が上手く証明できず残ってます。

1) n = p ＞ 3（3より大きい素数）の場合

予式が整数になるならば、分子は p を因数にもつ。

分子
= 2ⁿ + 1
= 2^p+ 1
= 2^p-1*2 + 1 ( mod p )

ここで、pと2は互いに素であることから、オイラーの定理より
= 1 * 2 + 1 ( mod p )
= 3

よって n = p ＞ 3 では予式は整数にならない。

2) n = p^m(p＞3)（素数のべき乗で表せる）場合

分母 = p^2mで割り切れるならば、分子はやはり p を因数にもつ。

今、2^pm-1 + 1 が p で割り切れないと仮定する。

分子
= 2ⁿ+ 1
= 2^pm+ 1
= 2 ^{(p-1)pm-1 + pm-1}+ 1

ここで、pと2は互いに素であることから、オイラーの定理より

= 1^pm-1* 2^pm-1+ 1 ( mod p )
= 2^pm-1+ 1 ( mod p )

数学的帰納法により 2^pm+ 1 は p で割り切れない。
よって、n = p^m(p＞3) では与式は整数にならない。

◆東京都　鳥居 さんからの解答。

【問題１】

答えから示すと n＝3 のみが解となる。 これを次のステップで証明する。
◎ n の可能性は奇数。
◎ n の可能性は 3 の倍数。
◎ q を5以上の素数とするとき、n は 3q の倍数になり得ない。
◎ n は 9 の倍数になり得ない。
n は 3 の倍数でありながら、合成数になり得ないことから、n＝3 を決定する。

◎「n の可能性は奇数。」の証明
n を偶数にすると、分子は奇数、分母は偶数になって、整数にならない。
よって、n は奇数に限られる。

◎「n の可能性は 3 の倍数。」の証明
以下では、n(≧3) は奇数とする。
問題を合同式を使って書き直すと、
[※] 2ⁿ≡−1 (mod n²)
を満たす n を求めることになる。

n を素因数分解して、最小の素因数を p とする。
n＝pr とおく。r が1より大きければ、最小素因数は p 以上である。
[※]を満たすためには、少なくとも下記の合同式を満たす必要がある。
2^pr≡−1 (mod p)
両辺を2乗すると
2^2pr≡1 (mod p)

一方、フェルマーの小定理より
2^p-1≡1 (mod p)

法 p の下における 2 の位数を e とすると、下の事実が成立する。
・ e は pr を割り切らない、e は 2pr を割り切る、e は p−1 を割り切る。
p は n＝pr の最小素因数としたから、p−1 は p とも r とも互いに素である。
よって、e＝2 しか成立しない。
2^e≡1 (mod p)
より、p＝3 しか成立しない。
これは、n が 3 の倍数しかあり得ないことを意味する。

◎「q を5以上の素数とするとき、n は 3q の倍数になり得ない。」の証明
以下では、n は 奇数で、3 の倍数で、合成数とする。
ただし、n は 9 の倍数ではないと仮定する。
この仮定に基づき、n を素因数分解したとき、3 の次に小さい素因数を q とする。
n＝3qs とおく。
q は5以上、s が1より大きければ、最小素因数は q 以上である。

[※]を満たすためには、少なくとも下記の合同式を満たす必要がある。
2^3qs≡−1 (mod q)
両辺を2乗すると
2^6qs≡1 (mod q)

一方、フェルマーの小定理より
2^q-1≡1 (mod q)

法 q の下における 2 の位数を f とすると、以下の事実が成立する。

・f は 3qs を割り切らない、f は 6qs を割り切る、f は q−1 を割り切る。
q は qs の最小素因数としたから、q−1 は　q とも s とも互いに素である。
よって、f＝2,6 しか成立しない。

2^f≡1 (mod q)
より、5以上の q としては、q＝7 しか成立しない。

ところが、q＝7 に対しては、
2¹≡2, 2²≡4, 2³≡1 となって、f＝3 である。
矛盾が生ずるため q＝7 は不適当である。

従って、満足する q は存在しないことになり、n は 3q の倍数になり得ない。

◎「n は 9 の倍数になり得ない」の証明
以下では、n は 奇数で、9 の倍数とする。
n を 3 の累乗で可能な限り割り算を行い、その累乗数を m とする。
n＝3^mt とおく。
m は2以上、t が1より大きければ、最小素因数は5以上である。

[※]を満たすためには、少なくとも下記の合同式を満たす必要がある。

2^3mt≡−1 (mod 3^2m)

両辺を2乗すると
2^{2(3^m)t}≡1 (mod 3^2m)

ここで、法 3^k (k≧1) の下における 2 の位数を g_k とする。
このとき、g_k＝2*3^k-1 となることを数学的帰納法で示す。

法 3¹ の下では、2¹≡2, 2²≡1 となるので、位数は 2 である。
このとき、法 3² の下では、2²≡4＝1＋3¹ となることに注目しておく。
次に、2^g_k≡1＋3^k (mod 3^k+1) であると仮定する。
法 3^k+2 の下では、2^g_k≡1＋3^k＋h*3^k+1 (mod 3^k+2) とおくことができる。
この両辺を2乗すると、2^2*g_k≡1＋2*3^k＋3^2k＋2h*3^k+1 (mod 3^k+2)
となり、法 3^k+1 の下で 1 と合同にならず、2*g_k は位数 g_k+1 になり得ない。
3乗すると、2^3*g_k≡1＋3*3^k＋3*3^2k＋3h*3^k+1≡1＋3^k+1 (mod 3^k+2)
となって、法 3^k+1 の下では 1 と合同になり、g_k+1＝3*g_k となる。
そして、仮定した式は k+1 のときも成立することが示される。

満たされるべき合同式に戻ると、
法 3^2m の下での 2 の位数は 2*3^2m-1 であり、
この値は 2*3^mt を割り切る必要がある。

t は3の倍数でないから、これを満たす m は 1 のみである。
しかし、ここでは m≧2 と仮定していたため、満足する m は得られないことになる。
よって、n は 3²＝9 の倍数になり得ない。

問題の条件を満たすためには、少なくとも S の和が p の倍数であることが必要である。

S の和＝1＋2＋…＋k＝

k(k＋1) 2

◎ p＝2 のとき
k≡−1,0 (mod 4) が解の候補である。
k＝3 のとき、{1,2}, {3} のようにできる。
k＝4 のとき、{1,4}, {2,3} のようにできる。
以下、数学的帰納法を使って証明する。

k＝4n−1 (n≧1) まで成立していると仮定すると、
{4n,4n＋3}, {4n＋1,4n＋2} をそれぞれの部分集合に加えることによって、
k＝4n＋3 でも成立することがわかる。


k＝4n (n≧1) まで成立している場合も、
{4n＋1,4n＋4}, {4n＋2,4n＋3} をそれぞれの部分集合に加えることによって、
k＝4n＋4 でも成立することがわかる。

以上より、p＝2 の場合は k＝4n−1 (n≧1), 4n (n≧1) が解である。

◎ p≧3 のとき
k≡−1,0 (mod p) が解の候補である。
k＝p−1 のとき、条件を満たすようにすることは不可能。
k＝p のときも不可能。
k＝2p−1 のとき、{2p−1}, {1,2p−2}, {2,2p−3}, …, {p−1,p} のようにできる。
k＝2p のとき、{1,2p}, {2,2p−1}, …, {p,p＋1} のようにできる。
k＝3p−1 のとき、S に {0} を追加して、S の元の個数を 3p とし、これらを3個ずつの元を有する p 個の部分集合に分けることを示す。
（最終的に {0} が含まれる部分集合ができるが、この部分集合に対して {0} を除外しても元の和は変わることはなく、問題の解となる。）
S を T₀＝{0, …,p−1}, T₁＝{p, …,2p−1}, T₂＝{2p, …, 3p−1} のように3つの組に分ける。

元の数値を p で割った余りに着目すると、
T₀,T₁,T₂ ともに、{0, …,p−1} という集合になる。
ここで、p 個の集合 U₀,…,U_p-1 を以下のように定義する。

[A] 0≦i≦

p−1 2

に対して Ui＝{i,

p−1 2

＋i，p−1−2i}

[B]

p＋1 2

≦i≦p−1 に対して Ui＝{i, −

p＋1 2

＋i，2p−1−2i}

すると、どの Ui も元の和は

3(p−1) 2

となる。

また、U_i (0≦i≦p−1) の第1元に注目すると、0,…,p−1 が一通り現れる。

Ui の第2元に注目すると、[A]からは

p−1 2

,…,p−1 が一通り現れ、

[B]からは 0,…,

p−3 2

が一通り現れる。

U_i の第3元に注目すると、[A]からは 0,2,…,p−1 の偶数が一通り現れ、
[B]からは 1,3,…,p−2 の奇数が一通り現れる。

以上をまとめると、U_i の第1、第2、第3いずれの元に注目しても、
i を 0≦i≦p−1 で動かすと 0,…,p−1 が一通り現れることになる。

U_i の第1の元を T₀から、U_i の第2の元を T₁から、U_i の第3の元を T₂から持って来ると、

[A] 0≦i≦

p−1 2

に対して Si＝{i,

3p−1 2

＋i，3p−1−2i}

[B]

p＋1 2

≦i≦p−1 に対して Si＝{i,

p−1 2

＋i，4p−1−2i}

と定義して、Si (0≦i≦p−1) の3個の元の和をいずれも

3(3p−1) 2

とすることができる。

k＝3p のとき、「3p−1 のとき」で定義した S_i (0≦i≦p−1) の各元を1ずつ加えたものを考えれば、問題の条件を満たす解となる。
具体的には以下のように書ける。（S_i を再定義している。）

[A] 0≦i≦

p−1 2

に対して Si＝{i＋1,

3p＋1 2

＋i，3p−2i}

[B]

p＋1 2

≦i≦p−1 に対して Si＝{i＋1,

p＋1 2

＋i，4p−2i}

以下、数学的帰納法を使って証明する。

k＝np−1 (n≧2) まで成立していると仮定すると、
{np,np＋2p−1}, …, {np＋p−1,np＋p} をそれぞれの部分集合に加えることによって、
k＝(n+2)p−1 でも成立することがわかる。

k＝np (n≧2) まで成立している場合も、
{np＋1,np＋2p}, …,{np＋p,np＋p＋1} をそれぞれの部分集合に加えることによって、
k＝(n＋2)p でも成立することがわかる。

以上より、p≧3 の場合は k＝np−1 (n≧2), np (n≧2) が解である。

【コメント】

かえるさんの解答に沿った形で解答させていただきました。
が、かえるさんの解答で不完全に思うところがあります。
p≠2 の k＝3p−1 と k＝3p の場合で、元の分割方法が理解できません。

例えば、k＝3p−1 の場合で、1,2,…,

3p−3 2

はどこへ振り分けられるでしょうか？

　『高校生からの挑戦状Part18』へ

　数学の部屋へもどる