Appendix 3 1次不定方程式と合同式
f-denshi.com  最終更新日: ***

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 個である。

この問題は,次の1次合同式の問題と同値です。

1次合同式,

  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:整数

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

1次不定方程式
ax−ny = c      ・・・・・・・・・・・・・・・・・・・・(1)

を満たす整数 x,y をすべて求めることです。

まず,(1)が解をもつための必要十分条件が,

a,n の最大公約数 d がc の約数になっている 

ことを証明しましょう。


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

 a = a’d, n=n’d, (a’,n’ は整数で互いに素)

として,これらを(1)に代入すると,

 ax−ny = a’dx−n’dy = (a’x−n’y)d = c

となります。この式から,整数解 x,y  が存在するためには,c がd の倍数であることが必要です。

逆に十分条件であることは,まず,

[1] a,n の最大公約数がd であるならば,

  X’a+Y’n = d

なる整数,X’,Y’が必ず存在する[#](定理)ことを思い出します。次に,

[2] cがdの約数になっている,つまり,c=ud ; (u は整数)ならば,

c = ud = u(X’a+Y’n)
  = a(uX’)−n(-uY’)

と書けます。これはdがcの約数ならば,整数解 x=uX’,y=-uY’ が存在することを示してます。(終)


では,実際の(1)を解いてみましょう。(1)の解をx=X,y=Yとすると,

    aX−nY = c   ・・・・・・・・・・・・・・・・・(2)

を満たします。今,何らかの方法で一組の解x0,y0が得られたとします。これも(1)の解ですから,

    ax0−ny0 = c  ・・・・・・・・・・・・・・・・・(3)

(3)−(2)より

   a(X−x0)−n(Y−y0) = 0

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

   a’(X−x0)−n’(Y−y0) = 0    ・・・・・・(4)

ここで,a’とn’は互いに素なので,(X−x0)はn’の倍数,(Y−y0)はa’の倍数となります。
したがって,整数 t を用いて,

   (X−x0) = n’t  →  X = x0+n’t

これを(4)に代入して,    Y = y0+a’t

十分性は,この解を(1)に代入すれば,確かに解になっていることは容易に確かめられます。(終)

 したがって,最初の方程式の解は,上の手順で求めた,X のうちで 0 ≦ X < n (=n’d) の範囲にn’の間隔で並んでいるものを拾いだせばよいことが分かった。

 

 [目次へ]