ヒミツ

ヒミツ

ヒミツ

ヒミツ

ヒミツ

まず(6)より。
題意は結局次のように書き換えられる。

二つの自然数A,Bに対し、次の集合Pを考える。
P={x=mA+nB|m,nは任意の非負整数}
この集合に含まれない非負整数の集合をQとすれば、Qの要素の数とQの中の最大値を求めることを考える問題となる。

A,Bが互いに素でないとき、最大公約数をdとし、A=da,B=dbとすると
x=mA+nB=d(ma+nb)
となるので、Pに含まれる要素はすべてdの倍数である。
したがってdの倍数ではない自然数はPに絶対に含まれないので、自然数全体で考えると、dの倍数ではない自然数は無限個あり、最大となる自然数はない。
次の「A,Bの少なくとも一方が1の場合」と区別して言うなら最大値は無限大。

A,Bの少なくとも一方が1のとき。
例えばA=1のとき、n=0とすれば
x=mA=m
であり、任意の非負整数を表すことができる。
このときQの要素の数は0個で、最大値は存在しない。

A,Bどちらも2以上で、A,Bが互いに素なときを考える。
modAで考えると任意の整数nは
n≡0,1,2,...,A-1
のいずれかの値をとり、それに対応するnBについても
nB≡0,1,2,...,A-1
のいずれかである。
ただしnBが0からA-1までのA通りの値すべてをとりうるかどうかは定かではない。

ここで次のことを証明する。
�@二つのn1,n2=0,1,2,...,A-1に対し、n1*Bとn2*Bを考えると
n1=n2⇔n1*B≡n2*B
�An*B≡n'となるnはn=0,1,2,...,A-1の中でただ一つに定まり、n'が異なれば定まるnの値も異なる。
�BnB≡{0,1,2,...,A-1}のA通りの値すべてをとるとき、nも{0,1,...,A-1}のA通りの値すべてをとる。

�@の証明
n1=n2のとき、n1*B≡n2*Bは明らか。
n1*B≡n2*Bのとき、(n1-n2)B≡0である。
すなわち(n1-n2)*BはAの倍数であるが、今A,Bが互いに素であるから、n1-n2がAの倍数、すなわちn1-n2≡0である。
n1,n2=0,1,...,A-1であるから、n1=n2が成り立つ。
したがって「n1=n2⇔n1*B≡n2*B」は真である。

�Aの証明
�@より「n1≠n2⇔n1*B≢n2*B」も真であるから、当然「n1≠n2⇒n1*B≢n2*B」も真である。
すなわちnが異なればnBも異なる。
n=0,1,2,...,A-1のA通りの値をとるので、nBも異なるA通りの値を持つ。
nBはmodAでは、とりうる値は0からA-1までのA通りなので、n同様やはりnB≡0,1,2,...,A-1のすべての値をとりうる。
さらに「n1*B≢n2*B⇒n1≠n2」も真であるから、nBが異なればnも異なり、nBが0,1,...,A-1のうちのいずれかの値をとるようなnがただ一通りに決まる。

�Bの証明
�Aより、nBは{0,1,2,...,A-1}のすべての値をとり、nBが異なればnも異なるので、nBをAで割った余りが{0,1,2,...,A-1}のすべての値をとるとき、nも{0,1,2,...,A-1}のすべての値をとりうる。


xが集合Pに含まれるとき、
x=mA+nB
と表すことができる。
xをAで割った余りをrとすると、両辺modAで考えると、x≡r≡nBである。
r=0,1,...,A-1までのいずれかの値をとり、�AよりnB≡rとなるnが0,1,2,...,A-1の中でただ一つに定まる。
そのようなnをn(r)とすると、
n=kA+n(r)
と表せて、
x=mA+(kA+n(r))*B=(m+kB)A+n(r)B
である。
k,mは非負整数なので、k=0とすれば
x=mA+n(r)B≧n(r)B
である。
したがって、Aで割って余りがrであるような自然数は、mが非負整数なのでn(r)B以上であれば、そのような自然数をすべて表すことができるが、n(r)B未満のものは表せない。
また�@よりnが異なればnBも異なるので、n(r)とは異なるnで余りがrのものは表すこともできない。
したがってn(r)B未満の余りがrの自然数は集合Pには含まれない。

r=0,1,2,...,A-1に対し、Pの要素で最小の数を並べると
{n(0)B,n(1)B,n(2)B,...,n(A-1)B}
である。
{n(0)B,n(1)B,n(2)B,...,n(A-1)B}
をAで割った余りは順に0,1,2,...,A-1であるので、�Bより
{n(0),n(1),...,n(A-1)}={0,1,2,...,A-1}
である。

したがって
{n(0)B,n(1)B,n(2)B,...,n(A-1)B}={kB|k=0,1,2,...,A-1}
である。

n(r)BをAで割った余りはrなので、商q(r)は
q(r)=(n(r)B-r)/A
と表せる。
q(r)≧0である。
余りがrであり、Pに含まれない非負整数全体は
{x=kA+r|k=0,1,2,...,q(r)-1}
と書けて、この集合の要素の数はq(r)個である。
ただしこれはq(r)≧1の場合である。
q(r)=0のときは、Pに含まれない余りがrとなるような集合は空集合で、要素の数は0個と考えれば、やはりq(r)個と書くことができる。
結局Pに含まれない余りがrとなる自然数の数は、
q(r)=(n(r)B-r)/A（個）
と書ける。

集合Pに含まれない非負整数全体の個数Nはr=0,1,2,...,A-1までq(r)を足して
N
=Σq(r)
=Σ{(n(r)B-r)/A}
=(B/A)*Σn(r)-(1/A)Σr

Σr=0+1+2+...+(A-1)=A(A-1)/2
また�Bより{n(r)|r=0,1,2,...,A-1}={0,1,2,...,A-1}
であったので、
Σn(r)=0+1+2+...+(A-1)=A(A-1)/2

したがって
N
=(B/A)*{A(A-1)/2}-(1/A){A(A-1)/2}
=B(A-1)/2-(A-1)/2
=(A-1)(B-1)/2

Aで割って余りがrで、Pに含まれないような自然数が存在するとき、その中で最大となるものはn(r)B-Aである。
{n(r)B|r=0,1,2,...,A-1}={kB|k=0,1,2,...,A-1}
であるので、これらの中で最大となるのはn(r)=A-1のときである。
(A-1)BがAを超えない場合は、どのような余りrであっても、Pに含まれないような自然数が存在しないことになるが、A,Bが2以上の互いに素な数と考えているので、A,Bの少なくとも一方は3以上であり、
(A-1)*B-A=(A-1)(B-1)-1＞0
である。
つまり(A-1)*Bは必ずAより大きく、Pに含まれないような自然数が少なくとも一つ存在し、それは(A-1)*B-Aである。

結局Pに含まれないような自然数で最大となる数Mは
M=(A-1)B-A=AB-B-A=(A-1)(B-1)-1
である。

MとNには
M=2N-1
の関係がある。

(1)A=3,B=6のとき。
A,Bが互いに素ではないので、Mはなし（強いて言うなら無限大）。
Nは無限個。

(2)A=5,B=7のとき。
A,Bはともに2以上で互いに素であるから、
M=(5-1)*(7-1)-1=23
N=(5-1)*(7-1)/2=12（個）
実際に求めると{1,2,3,4,6,8,9,11,13,16,18,23}である。

(3)M=11のとき。
最大値が存在するので、A,Bは互いに素な2以上の自然数。
M=(A-1)(B-1)-1=11
(A-1)(B-1)=12
A≦Bで考えると、A-1,B-1はA-1≦B-1の自然数であるから、
(A-1,B-1)=(1,12),(2,6),(3,4)
(A,B)=(2,13),(3,7),(4,5)
これらはすべて互いに素である。
またNはA,Bの値によらず
N=(M+1)/2=6
である。

答え、(A,B)=(2,13),(3,7),(4,5)、いずれの場合もN=6

(4)N=9
Nが0ではない有限の値を持つので、A,Bは2以上の互いに素な自然数。
N=(A-1)(B-1)/2=9
(A-1)(B-1)=18
(3)と同様にしてA≦Bとなる(A,B)の組を求めると
(A,B)=(2,19),(3,10),(4,7)
これらは全て互いに素である。
またA,Bの値によらずM=2N-1=17である。

答え、(A,B)=(2,19),(3,10),(4,7)、いずれの場合もM=17

(5)A=10,B=13のとき、A,Bは互いに素。
M=(10-1)(13-1)-1=107
N=(10-1)(13-1)/2=54（個）

予想は先に(6)を解いて答えを知っているので略。

ヒミツ

ヒミツ

ヒミツ

ヒミツ

ヒミツ

ヒミツ

ヒミツ

ヒミツ