modの計算について

質問

modの計算式ax≡b (mod c)の時xを求めよのような問題は
解く上で何か良い方法というか手順みたいなものはあるのですか？いつも運で解いています。検算の仕方も知っているのですが、解くときはいつも試行錯誤状態で困ってしまっています。

何か計算する上でこれを頭の片隅においておいたらすらすら解けるみたいな物があればご教授してください。
お願いします。

例えば80x≡339 (mod 583)はx≡201となり何とか
とけました。問題を見た瞬間に解ける方法とかないんですかねぇ。

回答No.5

yaksa

みなさんが説明しておられるユークリッド互除法の利用と別系統（でもないか）の方法としてフェルマーの小定理を使うやり方もありますね。

フェルマーの小定理
「pを素数、aをpの倍数でない整数とすると、a^(p-1)≡1 (mod p)」
ただし、法 583 が素数でないので、80x≡339 (mod 583) には使えません。
法が合同数の場合にはフェルマーの小定理を拡張したオイラーの定理というのがあります。
「aとnを互いに素な整数とすると、a^φ(n) ≡ 1 (mod n) 」
ここで、φ(n)：オイラー関数は、n 未満の n に素な自然数の数を表します。
これを使うと、583=11*53と素因数分解できるので、φ(583)=580 より、
80^580≡1 (mod 583)　両辺339倍して、
339*80^580 ≡ 80*(339*80^579) ≡ 339 (mod 583)
したがって、x≡339*80^579 と解が求まります。
フェルマーの小定理（オイラーの定理）を使うと簡単に解が求まりますが、実際にはとても使い物にならない複雑な解になってしまいます。
とはいっても理論の分野では、どんな場合にも解を陽の形にサッとかけるフェルマーの小定理は非常に有用ですね。

回答No.4

yoikagari

ax+cy=bの一般的な解法は、こちらは参照ください。

参考URL：

http://aozoragakuen.sakura.ne.jp/suuron/node13.html

回答No.3

oberon

No.2 shkwta 氏の解法で正しいです

a, b, c を消去すると　　x = 201 + 583 d

となり、任意の ｄ に対してこの x が最初の合同式の解になっています

なお、最小の正の解は　d=0　のとき　x=201

（80x = 339 + 583a のような方程式を Diophantos 方程式と言います）

回答No.2

shkwta

数学界で正しい習慣なのかどうかわかりませんが、こんなのはどうでしょうか。文字はすべて整数とします。
80x≡339 (mod 583)
80x = 339 + 583a
80b = 19 + 23a　　; b = x - 4 - 7a
11b = 19 + 23c　　; c = a - 3b
11d = 8 + c　　　 ; d = b - 1 - 2c
0 = e　　　　　　 ; e = c + 8 - 11d
ここで、d = 1 から出発して下からc, b, a, x とたどっていくと x = 201を得ます。

回答No.1

nitscape

＞問題を見た瞬間に解ける方法とかないんですかねぇ。
残念ながらないと思います。

ただ、
ax≡b (mod c)
を変形すると
ax-b = cn
になりますよね（nは整数）。

つまり例えば
22x-2=4n　（22x≡2 (mod 4)）
のような形であれば両辺を共通因数の2で割って
11x-1=2n　（11x≡1 (mod 2)）
のように簡単にできるかと思います。このくらいしかないのではないでしょうか？