(３)についてです。 なぜa=の式ではなくb=の式を代入するのでしょうか 逆ではダメなのですか？

は0でない とろがともに3の倍数ならば,7a4bも3の倍数であることを証明せよ。 ひと 40 がともに整数であるようなαをすべて求めよ。 a もの倍数で,かつがαの倍数であるとき, aを6で表せ。 aがろ 「αがもの倍数である」ことは, 「bがαの約数である」 ことと同じであり,このとき, 整数を用いて a=bk と表される。このことを利用して解いていく。 (2)αは5の倍数で,かつ40の約数でもある。 ( a, b が3の倍数であるから, 整数k, lを用いて) よって a=3k, b=31と表される 7a-46=7・3k-4・3l=3(7k-4l) 7k-41 は整数であるから,7a-46 は3の倍数である。 A (2) ゆえに,kを整数としてα=5k と表される。 -が整数であるから,αは5の倍数である。 40_40_81001) って 5kk a P.516 基本事項 ■ b は αの約数 a=bk Labの倍数 1年 整数の和差積は整数 である。 <a=5k を代入。 (C) a が整数となるのは, kが8の約数のときであるから k=±1, ±2, ±4, ± 8 したがって a=±5, ±10, 20, ±40 αがbの倍数, bがαの倍数であるから, 整数k, lを 用いて a=bk,b=al a=bk を b=al に代入し,変形すると b = 0 であるから kl=1 とされる。 b(kl-1)=0 負の約数も考える。 <a=5kにkの値を代入。 αを消去する。 k, lはともに1の約数で ある。 4 章 18 約数と倍数 最大公約数と最 k, lは整数であるから k=l=±1 したがって a=±b 倍数の表し方に注意! 上の そば (1) で a=3k, b=3kのように書いてはダメ! あは別々の

(3)を教えてください。

のとき, n2-1は8の倍数である。 (2) すべての整数nは 3k, 3k+1,3k+2 (kは整数) のいずれかの形で表される。 [1] n=3k のとき n²=(3k)²=9k=3.3k² [2] n=3k+1 のとき n²=(3k+1)=9k²+6k+1=3(3k²+2k)+1 [3] n =3k+2 のとき n2=(3k+2)²=9k+12k+4=3(3k²+4k+1)+1 よって,n2を3で割ったときの余りは0か1である。 終 n は整数とする。 次のことを証明せよ。 練習 22 (1)奇数のとき, n2+3は4の倍数である。 (2)n(n+1)を3で割ったときの余りは0か2である。 (3)+3m²+2n は6の倍数である。 第1節 約数と倍数 117

（2）の解説をお願いします。（1）をどうやって使おうか、などの思考の流れが知りたいです。

13 次の問に答えよ。 (1) 次の条件 (*)を満たす3つの自然数の組(a,b,c) をすべて求めよ。 (*) a<b<c» + + ===// ²0 1 1 1 a b C である。 (2) 偶数 2n(n≧1) の3つの正の約数か.q.rpgとptgtr = n を満たす組 (p,q,r) の個数をf(n) とする。 ただし、条件を満 たす組が存在しない場合は, f(n)=0とする。 nが自然数全体を動く ときのf (n) の最大値 M を求めよ。 また, f(n) = M となる自然数nの 中で最小のものを求めよ。

フォーカスゴールドの問題なのですが、問題文の意味から分かりません。解説をお願いしたいです、、。

は、 保 Check 例題 243 互いに素な自然数の個数 力を自然数とする。(m≦nでmとnが互いに素である自然数mの個数 *** をf(n)とするとき,次の問いに答えよ. (1) f(15) を求めよ. (2) f(pg) を求めよ.ただし, b, q は異なる素数とする. (3) f(p) を求めよ。ただし、pは素数,kは自然数とする。(名古屋大・改) 考え方 (1) 15 であるから, f(15) は, 15以下の自然数で15と互いに素,つまり,3の倍 ま数でも5の倍数でもない自然数の個数を表す. (2) は異なる素数であるから、 と互いに素である自然数は,かの倍数でもgの 倍数でもない自然数である. 互いに素である自然数は,かの倍数でない自然数である。 よって (3) 解答 (1) 15=3.5 であるから, 15と互いに素でない自然数, すなわち, 3の倍数または5の倍数であり, 15以下の より、自然数は, 3, 6, 9, 12,15, 5, 10 の7個である. よって, 15 と互いに素な自然数の個数は、 150 f(15)=15-7=8 その他の 練習 1 約数と倍数 Focus 13 NE-A 実は (2) p, gは異なる素数であるから, pg と互いに素でな い自然数, すなわち, pの倍数またはαの倍数であり、 pg 以下の自然数は, pq+10+1 Dの倍数 1p,2p,.... (g-1) p, pg ⑨個 ⑨の倍数 1・g, 2g, ..., (p-1)q, pq p の1個 pg の倍数 pg より, (q+p-1) 1 0103 よって, pg と互いに素な自然数の個数は, bb. f(pq) = pq-(g+p-1)-DALS)-(6-8-S (8) = pg-p-g+1=(p-1)(g-1) (3) p, 自然数であるから、が以下の自然数はがきが 個ある. この結果は素数であるから,以下の自然数での倍数 カー1(個) 「互いに素である」の 否定 「互いに素でな 「い」を考える. このf(n) をオイラー 関数という. (p.432 Column 参照) (1)を一般的に考える. p=3,g=5としてみ ると見通しがよくなる. pq÷p=q (1) pg÷g=p(個) は全部で, したがって f(p") = pk-pk-1 ES AICI IT TO .80 (85)5√3 ST=N 、電 互いに素である自然数の個数は、補集合の考えを利用せよ SON YASSKOR LUSHAJAJ 例題243のf(n) について次の問いに答えよ.ただし, p q は異なる素数 ( ^^)とする 431 第8章

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 約数と倍数、最大公約数と最小公倍数

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 約数と倍数、最大公約数と最小公倍数

107. n>0,m>0よりm-n>0という書き方は問題ないですか？ また、m-n≧1というのは m,nはともに自然数だからm+n,m-nは自然数。 自然数×自然数=40（自然数）になるとき m-nは1以上でないと 自然数×自然数は自然数にならないからですか？ （わかりやす... 続きを読む

107 √2次式の値が自然数となる条件 n²+40 が自然数となるような自然数n をすべて求めよ。 3 重要 例題 指針> √n²+40= よって ここで, A,B,Cが整数のとき, ABCならば A,BはCの約数 を利用して, ① を満たす整数m+n, m-nの組を考える。 (は自然数)とおき,両辺を平方して整理すると²-n²=40 (m+n) (m-n)=40 ・① このとき,0,n>0より+n>0であるから,①が満たされるときm-n>0 更に,m+n>m-nであることを利用して,組の絞り込みを効率化するとよい。 CHART 整数の問題 (積)=(整数)の形を導き出す 1 - (2数の積)=(整数)の形。 解答 ²+40mmは自然数) とおくと n<m 平方してn²+40=m² ゆえに (m+n) (m-n)=40 mnは自然数であるから, m+n, m-nも自然数であり, 40の約数である。 また,m+n>m-n≧1であるから ① より [m+n=40 [m+n=20 m-n=1 > 一致す ... m+n=10 m+n=8 m-n=5 m-n=2'lm-n=4' 41 13 3 解は順に(m,n)=(1/2,228) (11, 9), (7,3), 39), (22.2) したがって、求めるnの値は n=9, 3 <<n=√√n² <√n² + 40 =m ①m²-n²=40 <n>0から m+n>m-n <m+n=a,m-n=bとす ると a+b 2 a-b 2 <m n が分数の組は不適。 m= n= 検討 積がある整数になる2整数の組の求め方 上の解答の①のように、積) = (整数)の形を導く 1つである。(積)=(整数)の形ができれば、指針の 答えにたどりつくことができる。 また、上の解答では、積が 40 となるような2つ の自然数の組を調べる必要があるが, そのような組 は、右の で示された, 2数を選ぶと決まる。 例えば、 140 に対して (1,40) と (40, 1) の2組 ある。 ちなみに, 「(積が40となる) 2つの整数の組」 が決まるから、条件を満たす組は全部で4×2=8 (組) という条件の場合は、負の場合も考える必要がある ため、組の数は倍 (16組) になる。 しかし、上の解答では, る。 なお、整数α bに対し (a+b)(a-b) = 26 (偶数) であるから, a+b と α-bの偶奇は そのことを利用すると, 上の解答の の組は省くことができて, 2組に絞られるか ことは,整数の問題における有効な方法の を利用することで,値の候補を絞り込み, 40 の正の約数 4023･5 から (3+1)(1+1)=8(個) 1,2,4,5,8,10, 20, 40 を利用することで, (m+n,m-n) の組を4つに絞る工夫をしてい 473 4章 17 約数と倍数、最大公約数と最小公倍数 る｡ であ であ 1, n- 音数 あ あ った 数 こ ① + PN >

103.3 答えは±a=±bでないのですか？ (k,l)=(1,1),(-1,-1)だから a=-bになることはないのに なぜa=±bとなるのですか？

暴 O 0 G 基本例題 103 約数と倍数 bは0でない整数とする。 40 がともに整数であるようなαをすべて求めよ。 a, a (1) 1号と 5 a aとbがともに3の倍数ならば, 7a-46も3の倍数であることを証明せよ。 (3) a が6の倍数で,かつαが6の約数であるとき,aをbで表せ。 指針 「αが6の倍数である」 ことは, 「 6 がαの約数である」 ことと同じであり、このとき,整数kを用いて ana=bk と表される。このことを利用して解いていく。 (1) αは5の倍数で,かつ40の約数でもある。 解答 a が整数であるから,αは5の倍数である。 ゆえに,を整数として α=5kと表される。 40 40 8 よって a 5k k 40 が整数となるのは, kが8の約数のときであるから a k=±1, ±2, ±4, ±8 したがって a = ±5, ±10, ±20, ±40 (2) a,bが3の倍数であるから, 整数k, lを用いて 0 a=3k, b=3l と表される。 よって 7a-4b=7.3k-4-31=3(7k-4l) 7k-4lは整数であるから,74-4bは3の倍数である。 (③) αがもの倍数αがりの約数であるから,整数k, lを用いて と表される。 a=bk, b=al a=bk を b=al に代入し, 変形すると b=0 であるから kl=1 BATDOOR k=l=±1 (検討 これは 誤り! 練習 Wo b(kl-1)=0 k, lは整数であるから FOR a=±b したがって p.468 基本事項 ①) bαの約数 a=bk Labの倍数 =k(kは整数)とおい 5 てもよい。 +001 <a =5k を代入。 負の約数も考える。 <a =5kにんの値を代入。 整数の和差積は整数で ある｡ αを消去する。 k,lはともに1の約数であ る。 上の解答の これではa=bとなり,この場合しか証明したことにならない。 a, 6 は別々の値をと のようにk, l (別の文字) を用いて表さなければならない。 で, lを用いずに, 例えば (2) でa=3k, b=3kのように書いてはダメ! る変数であるから、 (1) 2つの整数α, bに対して, a=bk となる整数k が存在するとき, bla と書く とき α|20 かつ 2 であるような整数αを求めよ。 a,b,c,d は整数とする。 469 4章 17 約数と倍数、最大公約数と最小公倍数

113. mとnが互いに素でないことを言い換えると mとnが素数を公約数にもつ となるのはなぜですか？ 例えばm=20,n=4のときm,nは互いに素でなく、 公約数は4で素数ではないですよね？

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

107. m-n≧1と言えるのはm,nはともに自然数で、 √n^2+40=mが成り立つ時少なくとも mとnに1以上の差はあるから、ということですか？

DOOO を求めよ。 (2) 慶応大] 基本事項 ④ は素数。 -..+x²)....... = 素数のうち、 偶数は2の みである。 とよい。 の形。 nは素数) 利用しても求め ■09 参照)。 HE ", (a")"=a™m ろを2non とし D15-101-1 05-103-1 は起こらない。 重要 例題107 2次式 の値が自然数となる条件 ²+40 が自然数となるような自然数n をすべて求めよ。 +40mmは自然数)とおき,両辺を平方して整理すると²-n²=40 (m+n) (m-n)=40 ① 指針▽ よって ← (2数の積)=(整数)の形。 ここで, A,B,Cが整数のとき, AB=Cならば A,BはCの約数 を利用して, ① を満たす整数m+n, m-nの組を考える。 このとき,m>0,n>0よりm+n>0であるから, ① が満たされるとき m-n>0 更に,m+n>m-nであることを利用して,組の絞り込みを効率化するとよい。 STEE CHART 整数問題(積)=(整数)の形を導き出す 解答 n²+40=m(mは自然数) とおくと n<m 平方してn²+40=m² ゆえに(m+n)(m-n)=40 mnは自然数であるから, m+n, m-nも自然数であり, 40の約数である。」という条件の また,m+n>m-n≧1であるから,①より m+n=40 m+n=20 m+n=10 m+n=8 m-n=5 したがって、求めるnの値は m-n=1' 41 39 解は順に(m,n)=(1/2 (2. 32), (11, 9), (7. 3). (13. 3) 2 <n=√n² <√n²+40=m ①m²-n²=40 このことを利用すると、上の解答の れる。 00000 <n> 0から m+n>m-n <m+n=a,m-n=b とす ると a+b n= 2' a-b 2 mn が分数の組は不適。 m= n=9,3 FARO FRA 検討 積がある整数になる2整数の組の求め方 上の解答の① のように,(積) = (整数)の形を導く 1つである。(積)=(整数)の形ができれば,指針の 答えにたどりつくことができる。 また、上の解答では, 積が 40 となるような2つ この自然数の組を調べる必要があるが, そのような組 は、右の で示された, 2数を選ぶと決まる。 例えば、 140 に対して (1,40) と (40, 1) の2組 が決まるから, 条件を満たす組は全部で4×2=8 (組) ある。 ちなみに, 「(積が40となる) 2つの整数の組」 という条件の場合は、負の場合も考える必要がある ため、組の数は倍 (16組) になる。 しかし、上の解答では, る。 なお, 整数 α bに対し (a+b)(a-b) = 26 (偶数) であるから, a+b と α-bの偶奇は 一致 ことは,整数の問題における有効な方法の を利用することで,値の候補を絞り込み, 40 の正の約数 40=2.5 から (3+1)(1+1)=8(個) 5 ↓ 1, 2, 4, 5, 8, 10, 20, 40 を利用することで, (m+n, m-n) の組を4つに絞る工夫をしてい の組は省くことができて, 2組に絞られるか HAR U M-801- て求め上 473 4章 JmH 17 約数と倍数、最大公約数と最小公倍数