︵ 畔

＼

︱

′ ノ ヽ

ｔ ｒ リ

商 一 ｂ

Ｉ

       

＞ 一            １

１            

＋

＜

＞

１

︲ ＞

第

4章  Popoviciuの

定理

       75

証明

 

^η

=α

^η

+9と

お く.ただ しη∈

Z,o≦ g<α

_とする.α ≠0よ り 里

=2+1

α       α

と表せ る.こ こで

9は

^0≦

9<α

^{だか ら}

0<1<  1<1

α     α

である.よ って

を得 る。

       

^□

定理 4.4.5α_,bを互 い に素である自然数 とす る^.この とき_,α,bのFrobenius 数 は αb― α―bであ る

.,

証明

 

晨ら^b}(αb一α―

b)=0で

あることと任意の自然数 ηに対 して晨α

"}(α b―

α一b tt η

)>0が

成 り立つことを示せばよい。

補題4.4.3よ り

晨^Qb}(α

+b)+晨

_α,b}(α^b― _(α

+b))=1

である。しか し明 らかに 晨Qb}(α

+b)≧

1だ か ら

Pれ_,b}(α

+b)=1,PIα

_ル}(α^♭―_(α tt b))=0

解

^.1の

を得 る。また_,α′

,わ′をそれぞれ αα′≡1(mod b),わ^b′ ≡

1(mod 

_{α)を 満た}

す 自然数 とす る。この とき定理4.3.6と補題4.4.4よ り

■

^%b}(αb―

α― b+η

₎

=αb―

α ― _{b+η ̲{ろ} ′

_(α

_{b α b+η)}̲{α} ′

_(α

_{b α} ^b+η _)}+1

≧

(1‑:一 :+島 )一 (1‑:)― (1‑:)+1

=嘉 >0

となる。

      

□ 定理 ^4。4.6(SylveSterの 定理_)α,bを 互いに素である自然数 とす る。この と き 1≦ η≦ α^b― α―

b+1を

満たす η∈

Nの

うち,ち ょうど半数 が α,bで 表現可能である。

１ 一 一 α

一

﹇ 一α

＜ 一

Ｖ″ 一 α

ヽ

＞ Ｊ

η 一α

ｒ り ヽ ｔ

第

4章  Popoviciuの

定 理

       76

証 明

 1以

^{上 α}

b以

下 の 自然数 の集合 を ν

,1以

^{上 αb以}下 の 自然数 の うち αの倍数 で も らの倍数 で もない 自然数 の集合 を1イ′

,そ して 1以上_(αb―α―

b+1)以

下 の 自然数 の集 合 を Ⅳ とす る。

gCd(α

,b)=1よ

^り,/1/fの元 の うちで αまた は らの倍 数 は α

+b‑1個

^あ

る

.よ

って ν ′の元 の個数 は αb― _(α

+b‑1)=(α ‑1)(b‑1)個

で あ る^. ここでAイ′の任意 の元 を

mと

お くと補題4.4.3よ り,

■α

^,み}(αb―

m)+晨 _{α ,b}(m)=1}

が成 り立つか らν′の元の半数 が α,bで 表現可能でない。したがって,Aイ′ の元の うち α,わ で表現可能でない 自然数 の個数 は_:(α ^‑1)(わ

‑1)個

であ る。また_,α の倍数 と らの倍数 は明 らか に α,bで 表現可能であるか ら

,ν

の元の うち α,bで 表現可能でない自然数の個数 も ぅ^(α

‑1)(b‑1)個

であ る

.さ

らに定理4.4.5よ り_,(αb― α一

b)+1以

上 α

b以

下 の 自然数 は全て α,bで 表現可能 だか ら,Ⅳ の元の うち α,bで 表現可能でない 自然数 の個数

もち

^(α

^{‑1)(b‑1)個} である。したがってⅣの元のうちα

,bで

表現可能で ある自然数の個数は

(αb―

α―♭ +1)一

_:(α

‑1)(b‑1)=ち

_(α

‑1)(b‑1)

個 で あ る。

4.5  問題 1.1.1の 考察

先 に述べた ように,補題 4.4.3は,α,ろが互いに素な とき,αでも うでも割 りきれない 自然数 ηに対 して_,αb― ηか ηの どち らか一方が必ず α,bで 表 現可能であ り,も う一方は表現可能でないことを表 してい る.こ の ことか ら_,αb―ηが α_,ろ で表現可能であることと

,2が

α,bで 表現可能でないこ とは同値であると言 える。そ こで本節ではこの考 え方を用 いて,本^論文冒 頭で提示 した問題 ^1.1.1を考察 したい。

問題 ^1.1.1は,

自然数 αl,α2,…・,αdの 最小公倍数 を ν とす る。この とき

″

1+2+…

_{.十 聾}

=

^{ν ‑1}

αl   α2 l ^αd ν

とな る非負整数 χl,″2,・ …,″

dが

^{存在す るか。 また}

,存

^{在 の判定法及び解} を見つ けるアル ゴ リズムは存在す るのか,と い うものであった。ここでは α_l,α2,…・,α

dが

^どの

2つ

も互いに素 として上記 の問題 1.1.1を考察す るこ

とにす る.こ の場合

,ν

=αl,α2,…・,αdと な る^.

□

第

4章  Popoviciuの

定理

       77

4.5。

l 

α

=2の

場 合

α,ろ を互いに素な自然数 とし,α ≧

2,b≧

2とする。このとき

:+:=7

を変形 して,

b"+α

_ν=α

b‑1

を満 たす χ,ν ∈N。 の有無 を調 べ る。α≧

2,b≧

2よ り

1は

_{α,bで 表現 可} 能 で ない。よって,補^{題 4.4.3か らbχ}+αν=α

b‑1と

な る ″_,ν c NOは^唯 一つ存在 す る^.

以 上 か ら次 が成 り立 つ^.

定理 ^4.5。lα,bを 互 い に素 な 自然数 と し^,α ≧

2,b≧

2とす る.こ の とき

ドキュメント内 与えられた単位分数の和で表せる数について ： 数学理科甲子園の問題から (ページ 75-78)