最大公約数

質問

2つの正の整数をA、Bとし、AをBで割ったときの商をQ、あまりをRとすれば、A、Bの最大公約数はB、Rの最大公約数に一致するのはなぜですか？

回答No.4

tarame · ベストアンサー

ＡとＢの最大公約数をＧとすると
Ａ＝Ｇa，Ｂ＝Ｇb（a,bは互いに素）とおけます。

Ｒ＝Ａ－ＢＱ＝Ｇa－ＧbＱ＝Ｇ(a－bＱ)
よって、ＲとＢはＧを公約数にもちます。

ここで
bとa－bＱが公約数ｇ(≠1)をもつとすると
b＝gb',a－bＱ＝ga'（a',b'は互いに素)とおけます。
a＝ga'＋gb'Ｑ＝g(a'＋b'Ｑ)となり
aとbが互いに素であることに矛盾します。

よって、bとa－bＱは互いに素であることになります。
ゆえに、ＧはＲとＢの最大公約数となります。

回答No.3

quantum2000

厳密にはNo.１さんやNo.２さんの通りで、内容的には同じ様なことですが、数式をあまり用いない形で説明すると、

今、
　　Ａ＝ＢＱ＋Ｒ
となっているので、
　　Ａ と Ｂ の最大公約数を求める
ということは、
　　ＢＱ＋Ｒ と Ｂ との最大公約数を求める
ということになります。

この２つの数 ＢＱ＋Ｒ と Ｂ を見ると、
右のＢの約数は、左の ＢＱ＋Ｒ の中のＢＱの部分の約数に必ずなっています。・・・(i)
ですから、Ｂの約数の中で、Ｒの約数にもなっているものがあれば、（元々(i)より、ＢＱの約数にもなっていますから、）それは ＢＱ＋Ｒ の約数、すなわちＡの約数にもなっています。
つまり、ＢとＲの公約数は、ＢとＡの公約数になっているのです。
だから、ＢとＲの最大公約数も、ＢとＡの公約数になっています。・・・(ii)

逆に、ＢとＡの公約数は、Ｂ と ＢＱ＋Ｒ の公約数ということですから、Ｒの約数にもなっていないといけません。（Ｂの約数は、ＢＱの約数になっていますから。）
つまり、ＢとＡの公約数は、ＢとＲの公約数になっているのです。
だから、ＢとＡの最大公約数も、ＢとＲの公約数になっています。・・・(iii)

ゆえに、(ii)と(iii)より、ＢとＡの最大公約数と、ＢとＲの最大公約数は一致しないといけません。

回答No.2

sakura_214

AとBの最大公約数をg，BとRの最大公約数をg'とします．

まず，AとBはそれぞれgで割り切れるので，ある整数a,bによって
A=BQ+R=ag
B=bg
という形に書くことができます．この時上の式は
R=A-BQ=ag-bgQ=(a-bQ)g
と変形できるので，Rもgで割り切れます．よって，BとRはともにgで割り切れるのでgはBとRの公約数であるとわかります．この時点ではまだgがBとRの「最大」の公約数g'と一致するかどうかはわかりませんが，これより少なくてもg≦g'であるとわかります．

今度はBとRに注目します，上と同様にBとRはそれぞれg'で割り切れるので，ある整数r,b'によって
R=A-BQ=rg
B=b'g'
という形に書くことができます．この時上の式は
A=BQ+R=b'g'Q+rg=(b'Q+r)g
と変形できるので，Aもg'で割り切れます．よって，AとBはともにg'で割り切れるのでg'はAとBの公約数であるとわかります．これだけではg'がAとBの「最大」の公約数gと一致するかどうかはわかりませんが，少なくても今度はg'≦gであるとわかります．ところが，これは先程とは逆の関係であるので，両者がともに正しいためには実はg=g'であったとわかります．

この命題はユークリッドの互除法と呼ばれるもの原理を示した定理です．この定理のおかげで任意の２つ（以上でもいいですが）の数の最大公約数や最小公倍数は簡単に求めることができます．

回答No.1

masa072

AとBの最大公約数をαとすると、A=αm、B=αnとなります。但し、(m,n)=1
AをBで割ったときの商がQ、余りをRとすると、
A=BQ+R
が成り立ちます。今、A=αm、B=αnより、
αm=αnQ+R
もし、R=αpと書けない、つまりRがαを公約数に持たないならAはαを公約数に持たない。よって、Rはαを公約数に持ちます。
あとは、(nQ,p)=1を示せばいいことになります。
αm=αnQ+αpより、
p=m-nQ
(m,n)=1より、(m,nQ)=1。また、(nQ,nQ)=nQ。よって、(nQ,p)=1
よって、AとBの最大公約数はBとRの最大公約数となります。