Question

とりっぴー

青で示したところがさっぱり分かりません。
(1)はユークリッドの互除法がどう活用されてるのかさえ分からないです😫解説よろしくお願いします！

q
下の図は1から始めて分数の左下に分数 右下に分数
p+q
を配置する
p+q'
q
という規則でできた樹形図の一部である。このとき以下の問いに答えよ。
(1)この樹形図に現れる分数はすべて既約分数であることを示せ。 ただし整数は
既約分数とみなす。
(2) すべての正の有理数がこの樹形図に現れることを示せ。
(3)この樹形図に現れる有理数はすべて異なることを示せ。
19
(4)
はこの樹形図の上から何段目の左から何番目に配置されるか答えよ。 たとえ
44
ばは上から3段目の左から4番目である。
3
1
1
1
2
3-2
2
1
2人 3
3
1

解法 1
(1)2つの自然数p, gの最大公約数を(p, g) と表すことにする。
(i) 1段目に現れる分数 1 は既約分数である。
Þ
q
段目 (k=1, 2, ...) に現れる分数が既約分数, すなわち (p, g) =1である
Þ
p+q
と仮定する。このとき, (k+1) 段目に現れる有理数は
と
であるが, ユ
p+g g
ークリッドの互除法より
(p, p+q) = (p, q)=1, (q, p+q) = (q, p) = 1
が成り立つから,ppg および gp+q はいずれも互いに素であるので,
Þ
p+q
p+g
と はいずれも既約分数である。
9

(2) 樹形図でを
p+gに対応させる写像をそれぞれL, Rと表し,この逆
q p+q' q
の対応を表す写像をそれぞれL''R' と表すことにする。 また, 樹形図をT とす
る。
pg のとき
q-p
では次のように対応する。
<1>のとき,L>①であるから,T
q
pg のとき
p>g のとき
品
p-q
q
p+q
p+g
q
なお,p=gのものはP=1
のみであり, L''' R-''は存在しない。
g1
さて、正の有理数を既約分数で表したとき、分母と分子の和をs (b) (=p+α)と
q
表そう。このとき, Tに現れない正の有理数が存在すると仮定し, そのような有理
数(既約分数)で分母と分子の和が最小のものをとすると
go
(po\
S =po+go ただし,
Þo
#
go
go
1)
①より, po<go のとき
Do
go-po'
po> go のとき
po-90
は Tに現れないことになり,い
go
ずれも
Po
(po\
S
=go<s
S
(2000)=pos
po
go-por
go
が成り立つが、これはTに現れない色について sbo)が最小であることに反する。
go
よって, すべての正の有理数がTに現れる。
s
(証明終)
が2段目以降の段に現れることはない L.Rによって得られる有理数は、

Answer 1

✨ ベストアンサー ✨

和

青線は、活用というより、ユークリッドの互除法:
　pをqで割った余りをrとするとき、
　pとqの最大公約数はqとrの最大公約数に等しい
そのままです
模範解答の記号で表すとすると
　(p,q) = (q,r)
です

ただし、ここでいう余りは、特に0≦余り<割る数
に限定しなくても成り立ちます
たとえば(32,12)=(12,8)ですが、
(32,12)=(20,12)などとすることもできます

たとえば(p, p+q)
p+qをpで割った余りはq（p+q = p×1 +q）なので
(p, p+q) = (p,q)であり、これは1です
ここでは(p,q)=19と仮定しているためです

とりっぴー

ありがとうございます！分かりました！！