|
Appendix ３ １次不定方程式と合同式 | |
| f-denshi.com 最終更新日： 21/08/02 | ||
| ［目次へ］ | ||
１．1次不定方程式 aX＝c の解法
［１］
| 命題 環 Zn上の方程式 aX−c ＝ 0 が，Znにおいて根をもつための必要十分条件は，a と n の最大公約数 d （a，n）＝d が c の約数であることである。そのとき，最小の根をα，また，n ＝ n’d とすると，方程式の解は， X ＝ α，α＋n’，α＋2n’，・・・，α＋（d-1)n’ の d 個である。 |
この問題は，次の１次合同式の問題と同値です。
| １次合同式，
ax ≡ c （mod n） が根をもつための必要十分条件は，a と n の最大公約数 （a，n） ＝ d が c の約数であることである。そのとき，最小の根をα，また，n ＝ n’d とすると，方程式の解は n を法として x ＝ α，α＋n’，α＋2n’，・・・，α＋（d-1)n’ の d 個である。 |
に置き換えることができます。
［２］ さらに，
ax ≡ c （mod n ） ⇔ ax−c ＝ yn y：整数
なので，次の方程式を解くことになります。
１次不定方程式
ax−ny ＝ c ・・・・・・・・・・・・・・・・ [*] を満たす整数 x，y をすべて求めることです。 |
まず，[*]が解をもつための必要十分条件が，
a，n の最大公約数 d がc の約数になっている |
ことを証明しましょう。
［３］
(1) まず必要性は，最大公約数が d＝ （a，n） ならば，
a ＝ a’d， n＝n’d， （ a’，n’ は整数で互いに素 ）
として，これらを [*] に代入すると，
ax−ny ＝ a’dx−n’dy ＝ （a’x−n’y）d ＝ c
となります。この式から，整数解 x，y が存在するためには，c が d の倍数であることが必要です。
(2) 逆に十分条件であることは，a，n の最大公約数が d であるならば，
X’a＋Y’n ＝ d
なる整数 X’，Y’が必ず存在する[#]（定理）ことを思い出します。
(3) 次に，c が d の約数になっている，つまり，ｃ＝ud ； （u は整数） ならば，
c ＝ ud ＝ u（X’a＋Y’n）
＝ a（uX’)−n（-uY’）
と書けます。これは d が c の約数ならば，整数解 x＝uX’，y＝-uY’ が存在することを示してます。（終）
［４］
では，実際に（１）を解いてみましょう。（１）の解を x＝X，y＝Y とすると，
aX−nY ＝ c ・・・・・・・・・・・・・・・・・(1)
を満たします。今，何らかの方法で一組の解 x0，y0 が得られたとします。これも [*] の解ですから，
ax0−ny0 ＝ c ・・・・・・・・・・・・・・・・・(2)
(2)−(1)より
a（X−x0）−n（Y−y0） ＝ 0
a，n の最大公約数を d とすると，a＝a’d，n＝n’d，（ a’，n’は整数で互いに素 ) と表すことができ，これを上の式に代入して d で割ると，
a’（X−x0）−n’（Y−y0） ＝ 0 ・・・・・・(3)
ここで，a’とn’は互いに素なので，（X−x0） は n’の倍数，（Y−y0） は a’の倍数となります。
したがって，整数 t を用いて，
（X−x0） ＝ n’t → X ＝ x0＋n’t
これを(3)に代入して， Y ＝ y0＋a’t
十分性は，この解を [*] に代入すれば，確かに解になっていることは容易に確かめられます。（終）
［５］
したがって，最初の方程式の解は，上の手順で求めた，X のうちで 0 ≦ X ＜ n (=n’d) の範囲に n’の間隔で並んでいるものを拾いだせばよいことが分かります。
それは，最小の根をα （0≦α＜n’） とすれば，
X ＝ α，α＋n’，α＋2n’，・・・，α＋（d-1)n’
と表されます。 (完）