- ベストアンサー
一次合同式の解き方
３ｘ≡６（mod９）のｘを求めよという問題でgcd（3，9）= 3より6は3の倍数であるので解を持つことは分かるのですが，ｘを具体的に求めることができません．参考にしたサイトは ttp://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/ExEuclid.html「ここの拡張ユークリッド互除法の応用例２」の部分です． 拡張ユークリッドの互除法を用いても 3*1+9*0=3より3*1=3 mod 9 と当然の結果しか得られず進むことができません． ｘをどのようにすれば求めることができますか？手計算で表を書けば出来るという話ではなく参考サイトのように数学らしい（？）の解き方でお願いします．
- garusu
- お礼率18% (50/276)
- 数学・算数
- 回答数2
- ありがとう数3
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
そこまで出来ているなら 3*1 ≡ 3 (mod 9) の両辺に2を掛けて 3*2 ≡ 6 (mod 9) より、x=2が解の一つ。 でもx=5もx=8も解だからこれでは不十分な事が分かる。 自分なら次のように解くかな。 3x ≡ 3*2 (mod 9) より、両辺を3で割りたいところだが、その前にgcd(3,9)=3であることに注意して x ≡ 2 (mod 3) これが答え。 一般に a*c ≡ b*c (mod m) のとき gcd(c,m)=1ならば a ≡ b (mod m) gcd(c,m)=d≠1ならば a ≡ b (mod m') (ただしm'はm=d*m'であるような整数)
その他の回答 (1)
- mister_moonlight
- ベストアンサー率41% (502/1210)
応用例の1を使えばいいんじゃないの。不定方程式を解くだけ。 xとyを整数とすると、題意から 3x＝9y＋6 → x＝3y＋2 ‥‥(1) (1)のxとyの特別解を各々、α、βとすると α＝3β＋2 ‥‥(2) (1)-(2)より （x-α）＝3*（y-β）であるから、1と3は互いに素からmを整数として、x-α＝3m、y-β＝m ‥‥(3) (2)を満たす具体値の一つは （α、β）＝（5、1）。 従って、(3)より x＝3m＋5、y＝m＋1. これを(1)に代入すると、x-3y-2＝0.
関連するQ&A
- 拡張ユークリッドの互除法のaとbは1組のみ？
例えば、下記URLを見ると、 http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/ExEuclid.html -- x, yを0でない自然数とし，c=GCD(x,y)とする。このとき， ax+by=c となる整数a,bが存在する。そして，この a,b は実際に計算することが出来る。 -- のように拡張ユークリッドの互除法が解説されていますが、この時、a,bの組は1組なのでしょうか？それとも複数ある（可能性がある）うちの1組を特定できる、ということなのでしょうか？
- ベストアンサー
- 数学・算数
- ユークリッドの互除法についての問題です。
ユークリッドの互除法についての問題です。 a,bが任意の整数のとき、次の式を満たす整数xは必ずあるか。 (1)aが5の倍数でないとき ax≡b (mod5) (2)aが4の倍数でないとき ax≡b (mod4) 誰か教えてください。
- ベストアンサー
- 数学・算数
- 連立合同式の商の定理について
連立合同式の商の定理について教えてください。 x,yを整数 m,aを自然数とするとき ax≡ay (mod m) ⇔ x≡y ( mod m/GCD(m,a) ) (おかしな表記ですみません。( mod -)は分数式です) が「商の定理」と習いましたが、これは連立合同式 x≡a (mod K) x≡b (mod L) x≡c (mod M) のK L M が「互いに素」ではないときに適用できる定理だと思うのですが、うまく理解できません。 解らない点:(1) 連立合同式 x≡a (mod K) x≡b (mod L) の時、K L のGCDが「1」で「互いに素」と覚えていますが x≡a (mod K) x≡b (mod L) x≡c (mod M) の時も K L MのGCDが「1」で「互いに素」、それ以上ならば「互いに素」ではないと理解してよいのでしょうか？ 解らない点:(2) x≡a (mod K) x≡b (mod L) x≡c (mod M) で K L M が「互いに素」ではない場合、商の定理を適用した解法でx≡y ( mod m/GCD(m,a) )を求める方法。 K L M が「互いに素」ではない時、K L Mの最小公倍数を使えばよいのは解るのですが、GCD(m,a)の「a」が理解できません。「m」はK L Mの最小公倍数だと思うのですが、「a」は何になるのでしょう？ x≡2 (mod 4) x≡4 (mod 12) x≡3 (mod 9) の場合を例として、具体的に解法を教えてください。 よろしくお願いします。もしも上式が連立合同式として成立しないのであれば、その理由も教えてください。 中国式余剰定理では、( mod ○ )が「互いに素」ではない場合にも解を求める事ができると、参考書にはあるのですが、最小公倍数を使う事しか理解できません。 具体的な解法で、よろしくお願いします。
- ベストアンサー
- 数学・算数
- 大学数学で、合同方程式の問題なんですが、
大学数学で、合同方程式の問題なんですが、 ｘ＾９７≡２２ ｍｏｄ ２２５ の解の求め方がわかりません。 どなたかおしえていただけないでしょうか それとｘ＾ｔ≡ａ ｍｏｄ ｎ の解を求める際に ｇｃｄ（ａ，ｍ）＝１ ｇｃｄ（ｋ、φ（ｍ））＝１を使うらしいのですが意味がわかりません。 このときのａ，ｍ，ｋは一般自然数です ｘ＾９７は指数でｘの９７乗のことです よろしくお願いいたします。
- ベストアンサー
- 数学・算数
- 最大公約数 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) を導けばよいのでしょうか？ お願いします。
- 締切済み
- 数学・算数
- ユークリッドの互除法
ユークリッドの互除法の処方でつまづいています。 どなたか教えて頂けませんか。 aとbは正の整数でb≦aの関係にある。 aとbの最大公約数gcd(a,b)。 この時gcd(a,b)=ax+byの解となる(x,y)のペアはいくついるのでしょうか? 直感ですと(x,y)は一つしか存在しないように感じるのですが、どうやって記述すればいいのでしょうか？ よろしくお願いします。
- ベストアンサー
- 数学・算数
- ユークリッドの互除法
二つの整数a,bの最大公約数dを、ユークリッドの互除法で求める方法は分かります。 そうして求めたdは、適当な数x,yを使い、d=ax+byで表せることも何とか分かります。 しかし、d=ax+byが与えられたとき、ユークリッドの互除法を使って、特殊解xとyをどうやって求めたらよいのかが分かりません。 これまでの書き込みを見ても理解ができませんでした。 どなたか分かりやすくお教えください。
- ベストアンサー
- 数学・算数
- 数学のユークリッド互除法についてです。
数学のユークリッド互除法についてです。 [４２０１ｘ－３８５９ｙ=１の１組の非負整数解を求めよ]の解答と解法を教えて下さい。 何度計算しても負の値になってしまいます。 よろしくお願いします。
- 締切済み
- 大学・短大
お礼
>gcd(c,m)=d≠1ならば > a ≡ b (mod m') >(ただしm'はm=d*m'であるような整数) これは知らなかったです＞＜ 助かりました