赤阪正純 (httμ nupri.Web fc2 com) 余 りの美 しさ (1)

赤阪正純 (httμ nupri.Web fc2 com) 余 りの美 しさ (1)

な んの t,ち ゃ ^?

υ

1ト ッ ′ ヾツ ヵ今らん

いきな りですが ,「 余 り」についての とて も不思 議で美 しい定理 を紹介 しよう

この定理 はとても重要でいろいろな場面で活躍す るので ,こ こでは「基本定理」と呼ぶ ことにしよう

それに しても本当にこんなことがおこるので しょ うか   ち ょっと信 じがたいですが ,  まずは具体的な 数字で確認 してみよう

  ご フ そぅι量す

:ま へ

具体 例 での確認

まずは互いに素な 2数 として ,α =3,う =8と

よう  7個 の整数

1× 3, 2× 3,3× 3, 4× 3, 5× 3,6× 3, 7× 3

を ,8で 割 った余 りを求 め る と

1× 3=3 ‑―

2× 3=6 ‑

3× 3=9 ‑

4× 3=12 ‑一

5× 3=15 ‑

6× 3=18 ‑

7× 3=21 ‑→

確 か に ,余 りに ,1, 2, 3,

1回 ずつ現れています

lへ 7ま ^7ち

なりぶ

な守みメ

栞しぃ ^r(

6, 7が

次に ,互 いに素でない 2数 として ,α =6,ι =

の場合で基本定理 を確認 してみよう  7個 の整数

1× 6, 2× 6, 3× 6, 4× 6, 5× 6, 6× 6, 7× 6

を 8で 割 った余 りを求めると

α _,み が互いに素であるとする

この とき ,ι ‑1個 の相異なる整数

を みで割った余 りには ,1か ^らι ‑1ま での整 数が 1回 ずつすべて (順 不同で)現 れる

余 りの美 しさ

1× 6=6

2× 6=12

3× 6=18

4× 6=24

5× 6=30

6× 6=36

7× 6=42

とな り ,余 ^りは 0,2,

tせ ヒ

群 )が

ちがう f…

(う フ ア ι ツ ⁷

なんZkマ 4,6

余 り6 余 り 4 余 り 2 余 り ⁰ 余 り6 余 り4 余 り ² しかあ りませ ん

なん とも不思議 な結果 ですね   ど うして こんな こ とが起 こるので し ようかね (他 の数 字 の場 合 も試 し て み よ う   や れ ばや るほ ど不 思 議 さが実 感 で き る

し ょう )

それ で は基本 定理 を証 明 しよ う

基 本定理 の証 明

b‑1個 の整数

lα , 2α , 3α ,   ,

をうで割った余りは , 1, れ か の数 で あ る   よって

なるだここ進小幽￡ましヽ

ι α ,π ^α (1≦ ι <π _≦π ‑1)を うで割った余 りが同 じであると仮定す ると

ι α =ι91+γ

πα =う92+γ

(π ― ι _)α =ι (92 91)

α と うが互 い に素 なので ,π ― ιは bの 倍数 で あ る   と こ ろ が ,1≦ ι <π ≦ ι ‑1よ り

1≦ π 一 Z≦ ι ‑2だ か ら ,″ ^― Jは ら の倍 数 にはな らない   よって ,矛 盾

したが って ,う ‑1個 の整 数

lα ,2α ,3α ,  ^… ,(b‑1)α

を うで割 った余 りは全 て異 な るので ,題 意 は証 明 さ れ た

R翻 ^4ζ プ鮮 写・

(b‑1)α

2,  ^¨ ,  ^う ‑1の いず わ ‑1個 _{の余 りが全て異}

クばず

赤阪正純 (httpン フ inupri web fc2 com) _{余 りの美 しさ} (2)

(ら いう

ことか 〜

υ

f・

・ 7卜

'

珍注   この証明の最大のポイン トは最初の部分で す   どうして 「ιで割った余 りが ,1か らι ‑1ま

での整数が 1回 ずつすべて _(順 不同で)現 れること

が ,「 余 りが全部異なること」を示すことで証明で きるのか分か りますか

ら ^‑1個 の箱に国 から わ ‑1の _カードを

枚ずつ入れる ,  とイメージ しよう

「どの箱 にも違 うカー ドが入る Jな らば ,1枚 ^ず

つ全部バ ラバ ラに入 ることにな ります   箱の個数 と カー ドの枚数が同 じであることが重要なのです

いずれ にしても ,こ の証明の考 え方がとても重要 なので ,  しっか りと理解 しておこう .マ ジで大切

さて ,基 本定理か ら導かれ る重要な性質 を 2つ 紹 介 しよう

α _,み が互いに素のとき ,基 ^{本定理 よ り}

の中に ,ク で割 ると余 りが 1に なるものが必ず存在 す る   それ を 々α ,そ のときの商 を 9と ^{お くと}

たα =ι 9+1

∴   ^α力 +ι (― ,)=1

ここで _,た =″ ,‑9=υ とおけば題意は成立する

α _,う が互 いに素でない と仮定する と ,共 通 の素 因数 pが _{存在 し ,α} =ク ^{α ′} ,b=pb′ ^{となる   この}

とき

α ″ +bυ =1       _{もち方向は}

←⇒ pα 句十 ^pι ′

υ =l      ヵ ^)タ ン

⇔メぬ ^+ゆ =l   _θ

pは _{素数なので ,こ の式は矛盾である}    うγ千〜

α ,  ιが互いに素

⇔ α″ +ι υ =1

する

19̀

つ まり ,例 ^えば

3″ +5υ =1

のような不定方程式は ,式 の数 よ り文字の数が多い にもかかわ らず ,必 ず整数解 ″,υ をもつのです どんな整数解 なのか は分 か りませ んが ,と にか く

「存在す る」 ことが保証 されたわ けです   これ はす ごいことです

このように ,基 本定理 はただ単に余 りが全部異な ることを主張 しているだけではな く ,「 余 りが 1に なるものが必ず存在すること」の証明にもなってい

ます   つま り ,基 本定理 を利用すれば ,具 体的にい つ余 りが 1に な るかは分か らないが ,「 必ずある」

とい うことは断言できるのです

このような 「存在証明」は数学の中でも難問の部 類に入 りますが ,そ の攻略方法 として この基本定理 が有効であることをしっか り頭に入れておこう

多注 上にあげた 定理① を互いに素であるこ

との定 義 とす る場 合 もあ ります

① α × (一 α )十 (α 2+1)× 1=1よ り

α″ +(α 2+1)y=1を _{み た す整 数 ″ ,υ が存 在}

す るので ,α と α 2+1は 互 い に素 で あ る

■ 一般 に 「互 い に素 であ るこ とを証 明せ よ」 と言わ れ た ら ,こ の方法 で証明 す る ことは避 けた ほ うが良

簿ですが,互 いに素であるかどうかチェックする手

法 として知 ってお くと便利で しょう

定理 ① か ら次の事実が導 き出され ます Point

定理 ②

α _,ろ が互いに素であるとき,α″ +う _{υ (″} ,υ は整数 )は 任意の整数値 をとることができる つま り ,α ″十ιυの形ですべての整数 を表現す

―

ることがで きる

ど 珂 t

"''ン

′らんぃか (1,tッ 1例 題   αを2以 上の自然数とするとき ,α と

し 2+1は 互いに素であることを 定理 ① を利

用して示せ