赤阪 正 純 (httμ グ nupn web.fc2.com) ー■ ヽ１ノ ｒ 互 R素 のあ41 1ヽ Rス ター よ し うミ V'77- そ こで次 の よ うに定 め ます ―J>Pointく (「 互 い に素」 の新定 義 )一 あ ります α,う が互 い に素 で あ る とは,α ,ι が 共通 の 素 1 因数 「Eい に 素 」 と は まずは「互いに素」の意味を確認しよう 一般的 pを もたな いことで あ る 素因数 とは素数 の約数 のこと つ まり,公 約数 を 単 に 「1以 外 の整数」とするのではな く,「 素数 Jと には次 の よ うな定 義 にな るで し ょう 定義するのです.よ って,「 互いに素であること」を intく (「 互いに素」 の定義 証明す るには,「 互 いに素 ではない」つ ま り「共通 の素因数 pを もつ」と仮定 して矛盾 を導 けばよいの みが互いに素であるとは , 定義 ① α,ι が 1以 外 の公約数 をもたない 定義 ② α,ら の最大公約数 が 1で ある です int ☆ 「互いに素」であることの証明方法☆ 要す るに,「 共通 に割れ る 2以 上の整 数 がない 」 例 えば,8や 15は 素数 で はあ りませ んが ,8と 15は 互 いに素 です しよう 注意 もちろん,2つ の異 なる素数 は「互 いに素」 ヽ 力/ち がヽ です p いわ ば ,素 数 の 力 こ道 りて証 明す るのです この 考 え 方 はす ご く大 事 で ,こ の証 明 方法 を用 い る と 「互 いに素」 の証明方法 うま くい く場 合 が多 いで す (も ち ろん例 外 もあ りま す 上手くいかないときに最初の定義 ① や,定 義 おそ ら く,次 の ような論 法 にな るで しよう ておこう これらの基本性質は,ほ とんど全ての整 数問題に関係するといっても過言ではありません Pointく (整 数 の基本性質 ス と 3が 互いに素 な整数 の とき,И Cが 割 り切れ るな らば,Cは ☆定義 ① を用 いた証明方法☆ 3で 3で 割 り切れ る ３ Bで 割 り切れ るとき,4身 は整 数 になる が,ス と Bが 互いに素 なので約分 できないか ら,C スCが 盾 を示す れで ミ ☆定義② を用いた証明方法☆ α,う の最大公約数 を Gと おいて G=1で ■■や 民 る ことを示す が β で割 り切れなければな らない とい うことです あ ― >PoinN(素 数 の基本性質) こ しか し,実 際 夕 を素数 とす るとき,α らが っの倍数ならば,α または うが pの 倍数 である 特 に ,α ,bが 自然 数 で αう =ρ の とき (α ,う , )=(1,p)ま たは (p,1) これ らの性 質 を うま く利用 して,互 いに素である _ こ との 証 明 を します まずは,典 型的な証明方法を θ猟 これ らの証 明 の筋 道 は間違 いで はあ りませ ん λ ＾ α,ろ が 1以 外 の公約数 aを もつ と仮定 して矛 角υおか こ との 証 明 は どの よ うに な るで し ようか ります ヽ ンも 力1明 す 「互いに素Jの 証明の前に,次 の基本定理を確認し で は ,上 の よ うに定義 した場合 ,互 い に素 であ る の 方法 で上 手 くい く場 合 もあ ります キ散1 ② による証明や別証明を考えよう) て し'Jtヽ け ―′ 2 つ ま り,α ,ろ が共通の素数 . の 注 「互 いに素」を「互いに素数 Jと 勘違 い して いる人 が意外 と多 いです 背理法 による ・ サ11纂 κヽ で害」り切れると仮定 して矛盾を示す とい うことです (1 '｀ 素」 で あ るか ど うかが重要 な意 味 をも つ ことが 多 々 こン フム や モリ ＋し 整数 問題 の様 々 な 場面 で ,2つ の 整数 が 「互 い に ａ Ｐ ／１ヽ 互 いに素 互 いに素 (Part.1) 互いに素(Part l)Pボ inupri.web fc2 com) 赤阪 正 純 (httpソ フ と な な②よ ま d動 が 先α 聾I割 り /驚 具体例 を通 して覚 えて しまお う 1 例題 次 の こ とを示せ ￨(1)連 続する 2つ の 自然数 は互いに素である ￨ ￨(2)連 続する 2つ の奇数 は互いに素 である ￨ 考え方 共通 の素因数 pを もった と仮定 して矛 る場 合 も同様 であ る したが って ,α +う , αわは互 い に素 で あ る 盾 を示 します ■ 続 す る 2つ の 自然数 π と π+1が 0 (1)連 互 いに素 でない と仮 定す る と,共 通 の 素因数 pが 存 在し (2)α 2+b2, αろが互 い に素 で な い と仮 定 す る と,共 通 の素 因数 pが 存 在 し , , π=pα π+1=pβ となる このとき,p(β ―α)=1と なるので p≧ 2 よって,連 続する 2つ の 自然数 は互いに より矛盾 素である . の 注 次 の紹介す る mも よって bも つ で 害」り切 れ る こ とにな り,α ,ι が互 重要な論法です 囲田 πの素因数 を小 さいほ うか ら順番 に,A, p2,… ,p々 とする.こ れ ら全 ての素因数 で π+1 を割 ると,い ずれ の場合 も 1余 る よって ,π と い に素 であ る こ とに矛盾 す る うが pで 割 り切 れ る 場 合 も同様 で あ る したが って ,α 2+ぅ 2, αゎは互 い に素 で あ る ″+1に 共通 の素因数 は存在 しないので,互 いに素 ■ である ″注 ■ (2)連 続 す る 2つ の 奇数 2た -1と 2た 互 いに素 でない と仮定 す る と,共 通 の 素因数 +1が pが 存 も し 「素 因数 Jで はな く,単 な る 「公約数 」 と設定 した らど うな っていたで し ょうか ち ょっ と や って み ま し ょう が互いに素でないと 仮定する 巨垂∃ α+み ,α ら と,1以 外 の 公約数 グ が存 在 し 在し , , 2λ -1=pα 2々 +1=pβ α+う =dπ … (D αb=ご π ・② となる このとき,p(β ―α)=2 pは 奇素数な ので 夕≧3よ り矛盾.よ って,連 続する 2つ の奇 るわ けな い 数は互いに素である αまたは bが αで割 り切れ る とは限 りません い 静聟炒御 ■ となる.② より,α または うが ごで割 り切れ 2 α,う が互いに素であるとき , (1)α 十 う,α うは互いに素 で ある ことを示せ (2)α 2+ι 2,α ぅは互いに素であることを示せ 考え方 つ ま り,共 通 の素 もちろん背理法です 数 pで 割 り切れ ると仮定 して矛盾 を示そ う 0 (1)α +ι ,α うが互いに素 でない と仮定す ると,共 通 の素因数 pが 存在 し , α+b=p勿 ― ① αb=ク π… ② … !!!α ろが整 数 αで書」り切れるとき , 例 えば,α うが 6で 割 り切 れ るとき,α または わが 6 で割 り切れるとは限 りません 例題 9 ゑ αがpで 割り切れるとき,① よりb=pπ 一α 官ぇ〕ごと だから,う もっで割り切れることになり,α ,ろ が み子 互いに素であることに矛盾する.ι がクで割り切れ 先ほ どの Oの よ うに,公 約数 を 「素数」 と設定 していれば話が進み ますが,α は素数 ではないので,話 が全 く進 まない ことがわかるで しょう 多 注 上の 例 題 2 は逆 も成立 します つま り,必 要十分条件 です α十 う, αbが 互 いに素 ←⇒ α,う は互いに素 α2+ι 2, αらが互いに素 ←⇒ α,う は互いに素 証 明 は対偶 を とることで簡単 に示 せ るので各 自で い っ と て だ い や く さ .θ _ぃ ′ び
© Copyright 2024 ExpyDoc
