互いに素とは？

大学の授業で「二つの整数a,bが互いに素であることと、ある整数p,qが存在してpa+qb=1が成り立つこととは同値であるか証明しなさい。」という問題があったのですが、ニュアンス的にはわかりますが、これらを式でどのように証明したらいいのかが、さっぱりわからなくて困っています。
回答のほどよろしくお願いします。

No.2 ベストアンサー 回答者： yoikagari 回答日時： 2005/04/24 21:34

二つの整数a,bが互いに素であることとは、aとbの最大公約数が1であることです。

ある整数p,qが存在してpa+qb=1が成り立つこと⇒二つの整数a,bが互いに素であること

aとbの最大公約数をdとおく
d*{p(a/d)+q(b/d)}=pa+qb=1
となって、dは1の約数ゆえに、d=1
したがってaとbが互いに素であることが示された。

二つの整数a,bが互いに素であること
⇒ある整数p,qが存在してpa+qb=1が成り立つこと

整数の集合SをS={kは自然数|k=ma+nb、mとnは整数}とおく。
Sの正の要素のうち最小のものをeとおく
e=sa+tb
ここで、Sの任意の要素kがeで割り切れることを証明する。・・・※

k=eq+r(ただし0≦r＜e)と書ける。
0＜r＜eと仮定する・・・○
r=k-eq=(m-sq)a+(n-tq)b
ですから、○よりrは正のSの要素となるはずであるが、やはり○よりrはeより小さいので、これはSの正の最小の要素がeであることに反する。

したがってr=0となって、※が示された。

a=1*a+0*b、b=0*a+1*bだから、aとbもSの要素である。

※よりaとbもeで割り切れるはずであるが、
e≧2と仮定すると、eがaとbの2以上の公約数となってしまい、aとbが互いに素であることに反する。

したがってe=1
1=sa+tbとなるような整数sとtが存在することが言えました。

この回答へのお礼

すごく丁寧な解説をしていただきまして、ありがとうございました。これだけ詳しく解説をしてくださるとすごく理解しやすかったです。
ありがとうございました。

お礼日時：2005/04/25 03:09

No.3 回答者： noname#14584 回答日時： 2005/04/24 21:37

方法は色々ありますが，一例を．

左⇒右：
∃m∈Ｚ，ma≡1 (mod b)を示せばよい．
条件を満たすmが存在しないと仮定して，矛盾を導く．

右⇒左：
d=(a,b)とする．
d≠1と仮定して，整数環の可逆元が1,-1だけであることを用いて矛盾を導く．

この回答へのお礼

やはり矛盾を導きだすのですね。
ありがとうございました。

お礼日時：2005/04/25 03:02

No.1 回答者： eatern27 回答日時： 2005/04/24 21:27

二つの整数a,bが互いに素である、ならば、ある整数p,qが存在してpa+qb=1が成り立つ

の証明。

方針はいくつかあるので、その１つを。

p,qが整数全体を動くときに、
pa+qb
の形で表される自然数(1以上の整数)の集合Ａの最小元をＮとおく。
この後、Ｎ＝{a,bの最大公約数}(=1)である事を証明すればよい。


ある整数p,qが存在してpa+qb=1が成り立つ、ならば、二つの整数a,bが互いに素である
の証明は、背理法を使えば容易。

この回答へのお礼

ありがとうございました。

お礼日時：2005/04/25 03:11