Appendix ３　１次不定方程式と合同式
f-denshi.com  最終更新日： ***

１．aX＝c

この問題は、次の１次合同式の問題と同値です。

に置き換えることができます。

さらに、

ax ≡ c　（mod　n ）　　⇔　ax−c ＝ yn　　Y：整数

なので、次の方程式を解くことになります。

まず、（１）が解をもつための必要十分条件が、

ことを証明しましょう。

まず必要性は、最大公約数がd ならば、

　a ＝ a’d、　n＝n’d、　（a’、n’　は整数で互いに素）

として、これらを（１）に代入すると、

　ax−ny ＝ a’dx−n’dy ＝ （a’x−n’y）d ＝ c

となります。この式から、整数解 x、y  が存在するためには、c がd の倍数であることが必要です。
　逆に十分条件であることは、まず、
［１］　a、n の最大公約数がｄ であるならば、

　　X’a＋Y’n ＝ d

なるX’、Y’が必ず存在する[#]（定理）ことを思い出します。次に、
［２］　ｃ ＝ ud ； （u は整数）ならば、

c ＝ ud ＝ u（X’a＋Y’n）
　 ＝ （uX’)a−（-uY’）n

と書けます。これはdがcの約数ならば、解　x ＝ uX’、y ＝ -uY’　が存在することを示してます。（終）

では、実際の（１）を解いてみましょう。（１）の解をX＝X、y＝Yとすると、

　　　　aX−nY ＝ c　　　・・・・・・・・・・・・・・・・・（２）

を満たします。今、何らかの方法で一組の解x₀、y₀が得られたとします。これも（１）の解ですから、

　　　　ax₀−ny₀ ＝ c　　・・・・・・・・・・・・・・・・・（３）

（３）−（２）より

　　　a（X−x₀）−n（Y−y₀） ＝ 0

a、n の最大公約数を d とすると、a＝a’d、n＝n’d、（a’、sは整数）とあらわすことができ、これを上の式に代入してdで割ると、

　　　a’（X−x₀）−n’（Y−y₀） ＝ 0　　　　・・・・・・（４）

ここで、a’とn’は互いに素なので、（X−x₀）はn’の倍数、（Y−y₀）はa’の倍数である。
したがって、整数tを用いて、

　　　（X−x₀） ＝ n’t　　→　　X ＝ x₀＋n’t

これを（４）に代入して、　　 　Y ＝ y₀＋a’t

十分性は、この解を（１）に代入すれば、確かに解になっていることは容易に確かめられます。（終）

　したがって最初の方程式の解は、上の手順で求めた、X のうちで　0 ≦ X ＜ n　なるものである。