最大公約数の問題

質問

数学の問題の解説を読んでいる途中で、

＞ここで２つの正の整数x,yの最大公約数を[x,y]とあらわすことにすると(3)（ p_n = p_(n-1) + p_(n-2) )により、
＞　[p_(n-1),p_n]=[p_(n-2),p_(n-1)] (n=2,3,...).

という部分が出てきたんですが、理屈がわかりません。

a=b+cとして、
　[b,a]=[c,b]
である。
ということに書き換えられると思い、a=ma',b=mb'=nb'',c=nc'とおいていろいろ考えたのですがどうもうまくm=nであることが証明できません。

誰か解決してくれませんか。

回答No.4

yoikagari · ベストアンサー

#3の証明で間違いがあったので修正しておきます
正しくは
「
mをa,bの最大公約数、nをb,cの最大公約数としますと
a=ms，b=mt=nu，c=nvとなります
(ただし、s,t,u,vは整数です)
c=a-b=m(s-t)，b=mt
だからmはb,cの公約数でもあります。
nはb,cの最大公約数ですから、b,cの公約数の中で最も大きいです。
したがって、※よりm≦nが成り立ちます。・・・★
また
a=b+c=n(u+v)，b=nu
だからnはa,bの公約数でもあります。
mはa,bの最大公約数ですから、a,bの公約数の中で最も大きいです。
したがって、※よりn≦mが成り立ちます。・・・☆
★と☆よりm=nがいえます。
即ちa,bの最大公約数＝b,cの最大公約数であることがいえました。
」
でした。
ご迷惑をかけてすみませんでした。

回答No.5

yaemon_2006

以下、文字は、全て正の整数。

a = b + c (1)
[b, a] == m とする。a == pm、b == qm (pとqは互いに素) (2)
(1)より、c == a - b == (p - q)m
p と p - q が、1 以外の公約数 r を持つとすると、
p == kr、 p - q == lr (3)
q == kr - lr == (k - l)r (4)
(3)(4)より、p、q は 1 以外の公約数 r を持つので互いに素ではない。
これは、(2)と矛盾する。
よって、p、p - q は 1 以外の公約数 r を持たない、つまり互いに素である。
したがって、
[c, b] == m
以上により、
[b, a] == [c, b]

合ってるかな？

回答No.3

yoikagari

あなたの記号をそのまま流用します。
あなたはこの種の議論には慣れてらっしゃらないようですので、詳しく書きます。

この証明の最大のポイントは
「a,bの最大公約数はa,bの公約数のうちで最大であること」です。
つまり、
「a,bの最大公約数をd、a,bの任意の公約数をeとする。
このとき、e≦dが成り立つ」・・・※
ことがポイントです。

mをa,bの最大公約数、nをb,cの最大公約数としますと
a=ms，b=mt=nu，c=nvとなります
(ただし、s,t,u,vは整数です)
c=a-b=m(s-t)，b=mt
だからmはb,cの公約数でもあります。
nはb,cの最大公約数ですから、b,cの公約数の中で最も大きいです。
したがって、※よりm≦nが成り立ちます。・・・★
また
a=b+c=n(u+v)，b=nv
だからnはa,bの公約数でもあります。
mはa,bの最大公約数ですから、a,bの公約数の中で最も大きいです。
したがって、※よりn≦mが成り立ちます。・・・☆
★と☆よりm=nがいえます。
即ちa,bの最大公約数＝b,cの最大公約数であることがいえました。

同様な方法で
ユークリッドの互防法の原理
「a=bq+rが成り立つとき、a,bの最大公約数＝b,rの最大公約数」
が成り立つことが証明できます。

回答No.2

zk43

ユークリッドの互除法と似たようなものです。
[a,b]はbを割り切る。
c=a-bで、[a,b]はaとbを割り切るからa-bも割り切り、cも割り切る。
よって、[a,b]はbとcを割り切り、bとcの公約数だから、bとcの最大
公約数[b,c]より小さい。すなわち、[a,b]≦[b,c]…(1)
また、[b,c]はbを割り切る。
a=b+cで、[b,c]はbとcを割り切るからb+cも割り切り、aも割り切る。
よって、[b,c]はaとbを割り切り、aとbの公約数だから、aとbの最大
公約数[a,b]より小さい。すなわち、[b,c]≦[a,b]…(2)
(1)(2)から、[a,b]=[b,c]

記号としては普通、a,bの最大公約数は(a,b)、最小公倍数は[a,b]と表
します。

回答No.1

koko_u_

最大公約数を [,] で書くのはあんまり見ませんが、

>a=b+cとして、
> 　[b,a]=[c,b]
> である。
その通りです。

d を b, a の公約数だとすると d は c = a - b の約数でもあります。
つまり d は c, b の公約数。

逆に d' を c, b の公約数とすると、やはり d' は b, a の公約数でもありますね。