113. 「自然数k,l」を「互いに素である自然数k,l」 としたのですが別に良いですか？ また、最後「矛盾している」と書いていますが 同じことを2回書いているように思うのですが、 2回目の「矛盾している」には何の意味があるのですか？

基本例題113 互いに素に関する証明問題 (2) 00000 自然数a,bに対して, aとbが互いに素ならば, a + b と abは互いに素であるこ とを証明せよ。 091 5: 指針a+b と ab の最大公約数が1となることを直接示すのは糸口を見つけにくい。 そこで,背理法(間接証明法)を利用する。→a+b と ab が互いに素でない,すなわち a+b と ab はある素数を公約数にもつ,と仮定して矛盾を導く。 なお、次の素数の性質も利用する。 ただし,m,nは整数である。 mnが素数」の倍数であるとき, mまたはnはかの倍数である。 CHART 互いに素であることの証明 解答 a+b と ab が互いに素でない,すなわち a + b と ab はある素 数』を公約数にもつと仮定すると a+b=pk ①, ab=pl ...... p.4762 重要 114 ①1 最大公約数が1を導く 2 背理法 (間接証明法) の利用 ② , lは自然数) to と表される。 ② から, a または6の倍数である。 aがpの倍数であるとき, a=pmとなる自然数mがある。 このとき、①から6=pk-a=pk-pm=p(k-m) となり, bもpの倍数である。 これはαとが互いに素であることに矛盾している。 bがpの倍数であるときも、同様にしてαはかの倍数であり, aとbが互いに素であることに矛盾する。 したがって, a +6 と ab は互いに素である。 [番号] 前ページの基本例題 112 (2) の結果 「連続する2つの自然数は互いに素である」は、整数 この問題を解くのに利用できることがある。 興味深い例を1つあげておこう。 各自=2や 3 などの場合で,このことを検証してみるとよい。 n₁ mとnが互いに素でない ⇔mとnが素数を公約 数にもつ k-mは整数。 TRAF a=pk-b 問題 素数は無限個あることを証明せよ。 [証明] n を2以上の自然数とする。 と+1は互いに素であるから, n2 =n(n+1) は異な る素因数を2個以上もつ。 同様にして。 ns=n(n+1)=n(n+1)(n2+1) は異なる素因数を3個以上もつ。 この操作は無限に続けることができるから、素数は無限個存在する。 =p(k-m') ( m' は整数) 素数が無限個あることの証明は,ユークリッドが発見した背理法を利用する方法が有名である け 21世紀に入って (2006年), サイダックによって提示された, とても簡潔な方 a)(w) P 481 4章 17 約数と倍数、最大公約数と最小公倍数

112.2 記述これでも大丈夫ですか？

480 00000 基本例題112 互いに素に関する証明問題 (1) (1) nは自然数とする。n+3は6の倍数であり,n+1は8の倍数であるとき, n+9 は 24の倍数であることを証明せよ。 (2) 任意の自然数nに対して,連続する2つの自然数nとn+1は互いに素であ ることを証明せよ。 ATUNATI p.476 基本事項 ② 基本 111 重要 114 CFS CITAT 指針 (1) 次のことを利用して証明する。 a, b, kは整数とするとき a,bは互いに素で, ak が6の倍数であるならば,hは6の倍数である。 TRAXE SHES OU MOC! (2) 1 +1は互いに素⇔nとn+1の最大公約数は nとn+1の最大公約数をg とすると n=ga, n+1=gb (a,b は互いに素) この2つの式からnを消去してg=1 を導き出す。 ポイントは 【CHART A,Bが自然数のとき, AB=1 ならば A=B=1 求める。(間 解答 (1) n+3=6k,n+1=81 (k, lは自然数)と表される。 n+9=(n+3)+6=6k+6=6(+1) n+9=(n+1)+8=81+8=8(1+1)+ M=5A JES RAJS a,bは 11 ak = bl ならばんは6の倍数, 1はαの倍数 互いに素 ②2 aとbの最大公約数は 1 <<549° よって 6(k+1)=8(+1) すなわち 3(k+1)=(2+1) 3と4は互いに素であるから,k+1は4の倍数である。このとき,l+1は3の倍数 したがって,k+1=4m (mは自然数) と表される。 である。 したがって, ゆえに n+9=6(k+1)=6.4m=24m +1=3m と表されるから, したがって, n +9 は 24の倍数である。 n+9=8.3m=24m (2) nとn+1の最大公約数をg とすると n=ga, n+1=gb (a,bは互いに素である自然数 と表される。 n = ga をn+1=gb に代入すると ga+1=gb すなわち g ( 6-α) = 1 g,a,bは自然数で,n<n+1より6-a>0であるから g g=1 (1) としてもよい。 KBT BOE-S) IS = よって, nとn+1の最大公約数は1であるから, nとn+1 (ST 8 は互いに素である。 )=(62. 注意 (2) の内容に関連した内容を,次ページの参考で扱っている。 BOSTOYEVS nは自然数とする。 n +5は7の倍数であり、 Ad>D An=ga, n+1=gb 積が1となる自然数は1だ けである。 08 S (()(A) n+7は5の倍数であるとき、

112.1 2枚目:記述はこれでも問題ないですか？ 3枚目:l+1が3の倍数であることを示さなくても良い理由は こう（赤ペンで書いているところ）だからですか？？

480 00000 基本 例題112 互いに素に関する証明問題 (1) (1) nは自然数とする。 n+3は6の倍数であり,n+1は8の倍数であるとき、 n+9 は 24の倍数であることを証明せよ。 (2) 任意の自然数nに対して, 連続する2つの自然数nとn+1は互いに素であ 重要 114」 ることを証明せよ。 指針 (1) 次のことを利用して証明する。 α, b, kは整数とするとき p.476 基本事項 ②. 基本 111 a,bは互いに素で, akbの倍数であるならば, kは6の倍数である。 (2) +1は互いに素⇔nとn+1の最大公約数は 1 nとn+1の最大公約数をgとすると n=ga, n+1=gb (a,bは互いに素) この2つの式からnを消去してg=1 を導き出す。 ポイントは A,Bが自然数のとき, AB=1 ならば A=B=1 [CHART CAUCA a,bは ①1 ak=blならばんは6の倍数,はαの倍数 互いに素 ②2 aとbの最大公約数は 1 解答 (1) n+3=6k, n+1=81(k, lは自然数) と表される。 n+9=(n+3)+6=6k+6=6(k+1) n+9=(n+1)+8=8l+8=8(+1) よって 6(k+1)=8(+1) すなわち 3(k+1)=4(+1) ! 3と4は互いに素であるから, k+1は4の倍数である。 したがって, k+1=4m (mは自然数) と表される。 ゆえに n+9=6(k+1)=6.4m=24m したがって, n +9は24の倍数である。 (2) とすると n+1の最大公約数をg n=ga, n+1=gb (a,bは互いに素である自然数) と表される。 n=ga を n +1=gbに代入すると ga+1=gb すなわち g (b-α)=1小 g, a,b は自然数で, n <n+1 より 6-α>0であるから g=1 よって, nとn+1の最大公約数は1であるから, nとn+1 は互いに素である。 注意 (2) の内容に関連した内容を, 次ページの参考で扱っている。 練習 ②112 +12を35で割った余りを求めよ。 1+1は3の倍数 このとき, (2)を自然数とするとき 2n-1と2は である。 したがって, l+1=3m と表されるから、 n+9=8.3m=24m としてもよい。 (1) nは自然数とする。 n +5 は 7の倍数であり, n +7は5の倍数であるとき, ◄n=ga, n+1=gb 積が1となる自然数は1だ けである。 基 指針 C L a- と (2 a こ t 0 C

111. 指針についてです。 a=6k,b=6l,c=6mとしたとき k,l,mは互いに素であるとは言えないのは なぜですか？？

る。 見 I t 基本 例題 111 最大公約数・最小公倍数と数の決定 (2) 00000 次の (A),(B), (C) を満たす3つの自然数の組(a, b, c) をすべて求めよ。ただし, a<b<c とする。 (A) a,b,c の最大公約数は 6 STRE JUH (B) bとcの最大公約数は 24, 最小公倍数は 144 (C) aとbの最小公倍数は 240 解答 Ⅱ (B) の前半の条件から, b=24b', c=24c′ と表される。 ただし いに素な自然数でB'<c'′ ...... [専修大] (0) 14 p.476 基本事項 3, 基本 110 JANSS 指針 前ページの基本例題110と同様に, 最大公約数と最小公倍数の性質を利用する。 2つの自然数 α, 6 の最大公約数をg, 最小公倍数を1,a=ga', b=gb' とすると Ca' と'は互いに素 2 l=ga'b' 3 ab=gl (A)から,a=6k,b=6l,c=6mとして扱うのは難しい (k, l, m が互いに素である,とは 仮定できないため)。 (B)から6, c, 次に, (C)からαの値を求め、最後に (A) を満たすものを 解とした方が進めやすい。 このとき, b=246', c=24c′' (b', c'′ は互いに素でB'<c') とおける。 最小公倍数について 240'c'=144 これからB', c'を求める。 (ｴ) ......... 1=a+a)= (+ TRAHO 47

111. これは解答と違う解き方をしていた 途中まで記述です。 b',c'が間違っているのですが ここまでの過程でどこがいけないですか？

る｡ 現 文と [最大] <b' ると, 基本例題111 最大公約数 最小公倍数と数の決定 (2) 次の(A), (B), (C) を満たす3つの自然数の組(a,b, c) をすべて求めよ。 ただし, a<b<c とする。 (A) a,b,c の最大公約数は 6 (B (C)α ともの最小公倍数は240 24, 最小公倍数は 144 とCの最大公約数は • 指針 前ページの基本例題110 と同様に, 最大公約数と最小公倍数の性質を利用する。 2つの自然数a,b の最大公約数をg, 最小公倍数を 1,a=ga′', b=gb' とすると 11α'と6'は互いに素 2 l=ga'b' 3ab=gl これと ① を満たすB', 'の組は LAE2 (A)から,a=6k,b=6l,c=6mとして扱うのは難しい (k, l, m が互いに素である,とは 仮定できないため)。 (B) から 6, c, 次に, (C) からαの値を求め, 最後に (A) を満たすものを 解とした方が進めやすい。 このとき, b=246', c=24c' (b', c'は互いに素でB'<c') とおける。 最小公倍数について 246'c' =144 これから6', c'を求める。 解答 Ⅱ (B)の前半の条件から, 6= 246',c=24c′ と表される。自 ただし, 6', c'は互いに素な自然数で b'<c′ (B)の後半の条件から246'c'=144 すなわち 6 (b', c')=(1, 6), (2, 3) ゆえに (A)から,αは2と3を素因数にもつ。 練習 111 (b, c)=(24, 144), (48, 72). また, (C) において 240=24・3･5 [1] b=24(233)のときaと24の最小公倍数が240 であ るようなαは a=24・3･5 これは,α<bを満たさない。 S&TAN: [2] 6=48(=24･3) のとき, αと48の最小公倍数が240 であ FURA るようなαはa=2P・3・5 ただし [p=1, 2,3,4 a=30 a<48 を満たすのはp=1の場合で,このとき 30,48, 72 の最大公約数は 6 で, (A) を満たす。 以上から (a,b,c)=(30,48,72) p.476 基本事項 ③3 基本110 数は21, 最小公倍数は 294 [専修大] hcの最大公約数は7 ◄gb'c'=l <b=246′,c=24c 最大公約数は 623_ ◄ 240=24・3･5 [1] b=23.3 [2]. b=24.3 これからαの因数を考え RENO る。 次の (A), (B), (C) を満たす3つの自然数の組(a,b,c) をすべて求めよ。 ただし, a<b<cとする。 SITO 479 4章 17 約数と倍数、最大公約数と最小公倍数

写真についてですが、「左辺がpの倍数でqがpと互いに素であることから、3はpの倍数である」と書かれていますが、「pは3の倍数」であるという見方をできないのはなぜでしょうか？

9. 3 の約数 2x+11x2-3=0 ・・・ ④ の有理数解は ± 土2の約数 以外にはない ことを示しましょう。 有理数(p,q は互いに素な整数)が④の解であるとき q 3 2(e)' +11(e)-3=0. 20 2p³+11p²q-3q³=0. 31 EM (5) [p(2p²+11pq)=3q³, lg(3q²-11p²)=2p³. 6 ⑤において,左辺はpの倍数だから,右辺もの倍数しかるにg はかと 互いに素だから3の方がpの倍数.つまりは3の約数 ⑥から同様にし ては2の約数

急ぎです！ なぜ青の四角でかこった式になるのか教えてください！

562 第9章 整数・数 Think 例題269 不定方程式 57x+13y=1 の整数解を求めよ。 1 考え方 例題268のように特殊解を求めたいが, CE 方程式の整数解(3) Focus 係数が大きいため実際に値を代入して求めるのは困難である. 57 × (整数)+13×(整数) = 1 の式を作るために, ユークリッドの互除法を用いる。 pe TERY 解答 方程式 57x+13y=1 ...... ① の係数 57 と 13 について ユークリッドの互除法を用いる. 57=13×4+5 より, 13=5×2+3 より, 5=3×1+2 より, 3=2×1+1 より, ⑤ に ④ を代入して, m 3-(5-3×1)×1=1 3 ×2-5×1=1 これに3③ を代入して, ( 57-13×4=5 13-5×2=3 5-3×1=2 ...... ④ したがって, ①-⑥ より, ST ( 13-5×2)×2-5×1=1 mmm 13×2-5 ×5=1 これに② を代入して, 3-2×1=1….....⑤ 13 ×2-(57-13×4)×5=1 ax ...... 57 × (−5)+ 13×22=1 ARPETUSS 57(x +5)+13(y-22)=0 ·② ・③ HAI y=-57k+22 at S+AT=N ENSJAASEEBR 6 x+5=13k, すなわち, x=13k-5 これを⑦に代入すると, 57×13k=13(22-y) 57k=22-y より, よって, 求める一般解は, x=13k-5, y=-57k+22 (kは整数) 57(x+5)=13(22-y) ......7v 57 13 は互いに素であるから.x+5は13の倍数となる. したがって, kを整数として 5-3×1 I 1-7 | 13–5x 3 X2- |x= ① の (特殊

129. 記述これでも大丈夫ですか？？

JUL 510 OS 00000 基本例題1291次不定方程式の応用問題 3で割ると余り, 5 で割ると3余り, 7で割ると4余るような自然数nで最小の ものを求めよ。 指針▷ 基本 127,128 が共通の数。 8が最小である。 3で割ると2余る自然数は 2,5, 8, 11, 14, 17, 20, 23, 5 で割ると3余る自然数は 3, 8, 13, 18,23, よって、「3で割ると2余り, 5 で割ると3余る自然数」を小さい順に書き上げると 3と5の最小公倍数 15 ずつ大きくなる。 A8, 23, 38, 53, 68, また, 7で割ると4余る自然数は B 4, 11, 18, 25, 32, 39,46,53, A,B から、求める最小の自然数は53 であることがわかる。 このように、書き上げによって考える方法もあるが,条件を満たす数が簡単に見つからな い (相当多くの数の書き上げが必要な) 場合は非効率的である。 -110/ そこで,問題の条件を1次不定方程式に帰着させ、その解を求める方針で解いてみよう。 CTORUTSJEFE 解答 nはx,y,zを整数として,次のように表される。 注意x+2=5y+3 3)=0 S&TS 5y+3=7z+4 n=3x+2, n=5y+3, n=7z+4 小 3x+2=5y+3 から 3x-5y=1 x=2, y=1は, ① の整数解の1つであるから 3(x-2)-5(y-1) = 0 すなわち 3(x-2)=5(y-1)x 3と5は互いに素であるからんを整数として, x-2=5kと表 される。よって x=5k+2(kは整数) ② bom) 3(5k+2)+2=7z+4 ② を 3x+2=7z+4に代入して ゆえに z=-8, k=-4 は、 ③の整数解の1つであるから 7(z+8)-15(k+4)=0 すなわち 7(z+8)=15(+4) 7と15 は互いに素であるから, lを整数として,z+8=157 と 表される。 よって z=151-8 (Zは整数) (Thom) これをn=7z+4に代入して n=7(157-8)+4=1057-528 最小となる自然数nは, l=1 を代入して 53 TE bom) 85-= として解いてもよいが,係 数が小さい方が処理しやす い。 このときy=3k+1 x-7z=2から 7z-15k=4...... ③③ A+ASA-=(A+10)-06-3(x-3)−7(z−1)=0 ゆえに, Zを整数として x=7l+3 これと x=5k+2 を等置し て 5k+2=7l+3 よって5k-71=1 これより, k, lが求められ るが, 方程式を解く手間が 1つ増える｡ 検討 百五減算 2+(3=376)00=1+00=178 ある人の年齢を3,5,7でそれぞれ割ったときの余りをa,b,c とし, n= 70α+216+15c とす る。このnの値から 105 を繰り返し引き, 105より小さい数が得られたら、その数がその人の年 齢である。 これは 3,5, 7で割った余りからもとの数を求める和算の1つで、 百五減算と呼ばれ る。なお,この計算のようすは合同式を用いると,次のように示される。 求める数をxとすると, x=a (mod3), x=6 (mod5) x=c (mod7) であり, n=70a=1•a=a=x (mod 3), n=21b = 1.b = b = x (mod 5), n=15c=1+c=c=x (mod 7) よって, n-xは3でも5でも7でも割り切れるから, 3, 5, 7 の最小公倍数 105 で割り切れる。 ゆえに,を整数として, n-x=105k から x=n-105k このkが105を引く回数である。 TRON 練習 3で割ると2余り,5で割ると1余り, 11で割ると5余る自然数nのうち (3) 129 1000 を超えない最大のものを求めよ。 どのよう できない 3m よー 解答 mnは食 [1] n= よって, x=3m- [2] n= ここで. よって ......) [3] n= ここで よって ......) [1]~[3] 形に表す よって, したが一 (検討 次ペー しかし 然数も なお、 a

このやり方で答えは合ってますか？

練習 255 ポー 次の不定方程式の整数解を求めよ. (1) 2x+11y=5 ル(文字の (2) 4x+

126.1 解説の3行目以降の()は何をしているのですか？

504 00000 基本例題126 互除法の応用問題 (1) 2つの整数m,nの最大公約数と3m+4n, 2m+3n の最大公約数は一致す ることを示せ。 (2) 7 +48 +5 が互いに素になるような 100 以下の自然数n つあるか。 指針 最大公約数が関係した問題では, p.501 基本事項 ① (*)で示した, 右の定理を利用して,数を小さくし ていくと考えやすい。 本問のように,整式が出てくるときは,まず, 2つの 式の関係をa=bg+r の形に表す。 次に, 式の係数や次数を下げる要領で変形していくとよい。 解答 2 数A, B の最大公約数を (A,B) で表す。 口 (1) 3m+4n=(2m+3m) ・1+m+n, 2m+3n=(m+n) ・2+n, m+n=n·1+m よって (3m+4n, 2m+3n)=(2m+3n, m+n) =(m+n, n)=(n, m) したがって,m,nの最大公約数と3m+4n,2m+3nの最 大公約数は一致する。 221 DE 01 ① とおくと 2 は全部でいく p.501 基本事項 ① aとbの最大公約数 a=batr 等しい 3m+4n=a m=3a-4b [別解 2m+3n=b n=36-2a mとnの最大公約数をd, aとbの最大公約数をeとする。 ① より αと6はdで割り切れるから, dはaとbの公約数 である。 ゆえに d≤e ...... e≦d 同様に,②よりはとnの公約数で ③ ④ から d=e よって, 最大公約数は一致する。 (2) 8n+5=(7n+4)·1+n+1, 7n+4=(n+1).7-3 ゆえに (8n+5, 7n+4)=(7n+4, n+1)=(n+1, 3) 7 +4と8+5は互いに素であるとき, n+1と3も互いに 素であるから, n +1と3が互いに素であるようなnの個数 を求めればよい。 R-X10 2≦n+1≦101 の範囲に,3の倍数は33個あるから 求める 自然数は 100-3367 (個) 練習 ③ 126 (1)a,bが互いに素な自然数のとき, 3a+7b 2a+5b とrの最大公約数 差をとって考えてもよい。 3m+4n-(2m+3n) = m+n 2m+3n-(m+n)=m+2n m+2n-(m+n)=n m+n-n=m <m=dm',n=dn', a=ed', b=eb' とする ① は 'd(3m'+4n')=a d(2m'+3n')=b re(3a'-4b')=m e(36'-2a')=n ②は a=bg-r のときも (a, b)=(b, r) が成り立つ。 .501の解説 と同じ要領で証明できる。 は既約分数であることを示せ。 (2) 3n+1と4n+3の最大公約数が5になるような50以下の自然数nは全部で いくつあるか。 Op.514 EX87.88 以下 1 フ r 角 例1 た た x 例2 方 a VE x ア G C Q Ve 3