Question

やさいのようせい

a、bが互いに素である⇒ax+by=1が整数解をもつ
の証明がよくわかりません。

下の画像の
a、2a、3a…(b-1)aをbで割った余りとありますが、なぜ(b-1)aまでなんですか？

あと、割った余りがすべて異なるので余りが1となるようなものが存在する
と書いてありますが、割った余りがすべて異なると必ず余りが1であるものが存在すると言い切れるのは何故ですか？？

回答よろしくお願いします！

1 = の証明

CC とらちが互いに素なとき

g, 2o, 3o,・・, (5 一 1)g をで割った余
りは全て異なる (※) ので, 余りが1となる
ようなものが存在する。

それ 7726 とおき, 6 で割った商を 7。 とお

に

7 三672十1

つまり, g77 一 6 三 1 となり(7z, 一)

は整数解になっている。

※の証明(育理法)

2 と 7 (? > 7) を0 で割った余りが同じだ
と仮定すると, (? 一 7)cg は0の倍数となる

はずだが, 1 <く?一7このかつoと6は互
いに素なのでこれは矛盾。

Answer 1

✨ ベストアンサー ✨

鈴木鈴

そもそも
ｂでわった余りは
0.1.2.3…b−1　のｂ通り。
今回はa,bが互いにそで余りが0にはならないので
余りが0以外のb−1通りのいずれか。

座席が1番からb−1番まであってb−1人が1人ずつ座ると　誰かが1番に座る

というような感じです。

やさいのようせい

bで割った余りの種類は
0、1、2、…、b-1なんですね！
確かにそれ以上いっても、同じ余りが繰り返されるだけですね！
ありがとうございます！

Answer 2

ゆう

もしbaまでいくとbaは因数bを持ち互いに素でなくなるため。