最大公約数 gcd(a,b,c) と一次合同式の解の存在

質問

初等整数の証明で困ってます。

(1)gcd(a,b,c)はgcd(a,b)の約数であることを証明せよ。

(2)gcd(gcd(a,b),c)はgcd(a,b,c)の倍数であることを証明せよ。

また合同式の定理の証明について

gcd(a,b)=1ならばax≡c(mod b)は解をもつ。
さらにこの合同方程式の一つの解をpとすると、すべての整数kについてp+kb も解である。逆にこの合同方程式の任意の解はp+kb　と表わされる。

ax≡c(mod b)　は b | (ax-b) を導けばよいのでしょうか？
お願いします。

回答No.2

Tacosan

重要なのは「a と b の公約数は gcd(a, b) の約数である」ということですが... これを使っていいのかなぁ? 最悪証明すればいいんだけど.
(1) gcd(a, b, c) は a, b, c の公約数ですから当然 a と b の公約数でもあります.
(2) (1) から gcd(a, b, c) は gcd(a, b) の約数であり, かつ c の約数でもあります. 従って gcd(a, b) と c の公約数ですね.

お礼

なんとかできました。ありがとうございました。

回答No.1

Tacosan

上は (1), (2) のどちらも gcd の性質を考えるだけだと思います. 悩みだすと (1) の方が悩むかな.
下は gcd(a, b) = 1 から ax + by = 1 となる整数 x, y が存在することと「gcd(a, b) = 1 かつ b | ac なら b|c」を使う.

お礼

下のほうはできました。

補足

回答ありがとうございます。
gcdの性質をうまく扱えなくて困ってます。
ちなみに b | (ax-c)でした。すいません。