• 締切済み

最大公約数 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) を導けばよいのでしょうか？ お願いします。

みんなの回答

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.2

重要なのは「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 の公約数ですね.

southern38
質問者

お礼

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

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.1

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

southern38
質問者

お礼

下のほうはできました。

southern38
質問者

補足

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

  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • 連立１次合同方程式

    連立１次合同方程式 x≡b_1(mod m) x≡b_2(mod n) の一般解をxとするとき、gcd(m,b_1)=1かつgcd(n,b_2)=1であるならば、かつその時に限り、gcd(mn,x)=1 これをどのように示したらよいか分かりません。 １次合同方程式を解くことはできるのですが、証明となるとどうしていいか分からなくなってしまいました。 分かる方、助けてください。

  • 最大公約数を求めたい！

    二つの数字の最大公約数を求めたいのですがどうしたらいいのかわからず困っています…。プログラムに関しては初心者なのでどなたか分かりやすく教えてもらえませんか？？ ＜さらにもし出来る方がおられたら…＞------------------------------------ 実は最終的にはある数（a（素数））があって、そのaと”たがいに素”である数（ｂ）をプログラムで求めたいんです…。 ある本によると適当な二つの素数ｐ、ｑがあるとしてこのふたつの積（つまりｐ＊ｑ）をｍとします。また、(p-1)(q-1)＝aとすると ”gcd(b,a)≡1(mod m)” という式を満たすんだそうです…。 ※この中にでてくる値で実際に分からないのは"b"のみです。 ※ここで書いているgcd(b,a)というのはaとｂの最大公約数のことです。 --------------------------------------------------------------------- かなり難しいのでこの質問の回答をいただくと本当に助かります。 よろしくお願いしますm(_ _)m

  • a,bの最大公約数を求める関数をつくってみたのですが、aまたはbが零の

    a,bの最大公約数を求める関数をつくってみたのですが、aまたはbが零の時の処理としては、どのようにするのが適当かがわかりません。ある数と零の最大公約数ってどうなるんでしょうか？ #include <iostream> using namespace std; // 整数 a, b の最大公約数を求める int gcd(int a, int b) { if(b == 0) return -1; // この戻り値は適当なのか？ int r = a % b; // aをbで割った余り if ( r == 0 ) return b; // 余りが0ならbが最大公約数である else return gcd(b,r); // 余りが0でなければbとrの最大公約数を返す } int main() { cout << "gcd(1000,100) = " << gcd(1000, 100) << endl; return 0; }

  • 最大公約数の証明

    gcd(n,a)=1かつgcd(n,b)=1ならばgcd(n,ab)=1をベズーの等式を用いて証明するっていう問題なのですが、 nx+ay=1 nu+bw=1 と書いて、最初の式にｂを掛けたりしたんですが、どうやって証明すればいいのか全くわかりません。 わかる方、どうかお願いします。

  • 最大公約数を再帰で求める（pascal)

    入力した整数値の最大公約数を出力するプログラムを再帰呼び出しの形式で作れ、という課題が出ました。 再帰でない形式は下のように作れたのですが、再帰形式がどうしてもできません。どなたかご教授ください。 function gcd(a,b:integer):integer;　｛関数部｝ var tmp:integer; begin if a<b then begin tmp:=b; b:=a; a:=tmp end; repeat tmp:=b; b:=a mod b; a:=tmp until b=0; gcd:=a end; repeat　｛計算部、i=n=入力した個数、max=入力できる最大数｝ i:=i+1; n:=n+1; data[i]:=x; writeln('値:'); readln(x); until (x=0) or (i=max); if i>=2 then begin p:=gcd(data[1],data[2]); if i>=3 then begin for i:= 3 to n do begin p:=gcd(p,data[i]) end; writeln('最大公約数:',p) end else begin writeln('最大公約数:',p) end;

  • 最大公約数について

    「a,b,c,rが正の整数で、a=rb+cであるとき、a,bの最大公約数とb,cの最大公約数は一致することを証明せよ。」 という問題の解答の出だしが、 「aとbの最大公約数をm、bとcの最大公約数をnとおくと a=mA, b=mB（AとBは互いに素な整数） b=nB',c=nC（B'とCは互いに素な整数） と書ける」 となっているのですが、なぜこう書けるのかわかりません。 「a=mA, b=mB」「b=nB',c=nC」とかけるのはわかりますが、なぜAとB,B'とCが互いに素と言えるのかわかりません。 思いつく反例を上げると、a,b,cは異なる数とは問題文に書かれていないので、もしaとbが同じ数だとしたらA=Bとなり互いに素ではありませんよね？

  • 最大公約数の問題

    数学の問題の解説を読んでいる途中で、 ＞ここで２つの正の整数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であることが証明できません。 誰か解決してくれませんか。

  • a、ｂを自然数として…

    a、ｂを自然数として、ｂを素数とする。 x^3+ax^2-５ｘ+b=0が自然数解αをもつとき、 a、ｂの値とこの方程式の解をすべて求めよ。 解と係数の関係ですかね？ やはり分かりません… 教えてください(><)

  • 添削願い

    xについての３次方程式x^3+ax^2+bx+c=0が実数解α、β、γをもつとき、次の問いに答えよ。ただし、a,b,cはすべての実数でc≠0 (1)yについての３次方程式cy^3+10by^2+100ay+1000=0の解は10/α,10/β,10/γであることをしるせ。 回答 cy^3+10by^2+100ay+1000=0は10/α解に持つとき、 c(10/α)^3+10b(10/α)^2+100a(10/α)+1000=0 両辺にα^3/1000をかけて、 α^3+aα^2+bα+c=0 これはx^3+ax^2+bx+c=0がαを解に持つとき成り立つ式である。よって、cy^3+10by^2+100ay+1000=0 は10/αを解にもつ 同様にして、10/β,10/γのときも成り立つ。 (2)上のxについての３次方程式の解とyについての３次方程式の解がすべて整数となるような (a,b,c)の組は全部で何通りあるか。 回答 α、β、γは10の約数であるから、 ±1,2,5,10 のいずれか。 [1]α、β、γがすべて異なる場合 8C3=56通り [2]α、β、γのうち２つが異なる場合 8C2=28通り [3]α、β、γがすべて同じ場合 8通り 以上より 56+28+8=92通り こうなりましたが、これであっていますか？(1)の答えは友達から教えてもらったのですが、こういう証明の仕方はありなのでしょうか？？あと(2)もいまいち自信がありません。

  • 離散数学の証明問題

    離散数学の証明問題 合同でないことを≡×と表します。 Pを素数とし、a≡×0(mod p)とする。また、aの位数をdとする。 このとき、次のことを示せ。 (1)整数nに対して、a^n≡1(mod p)であるならば、かつそのときに限り、d|n (2)dはp-1の約数である。 (3)整数i,jに対してa^i≡a^j　(mod p)であるならば、かつそのときに限り、i≡j(mod p) (1)はFermatの小定理を使うと思うのですが、いまいち解法が浮かびません。 (2)はFermatの小定理から自明に思えますが、厳密に証明しないといけないみたいです。 (3)は証明方法がまったく分かりません。 分かる方、証明お願いします。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する