一次不定方程式

9.一次不定方程式の解の存在

不定方程式

未知数が方程式より多く解が一つに定まらない方程式

\(ax+by=1\)(命題1)

\(a,b\)が\(0\)でない整数とする
\(ax+by=1 \)が整数解を持つ\( \Leftrightarrow\)\(a\)と\(b\)が互いに素

\((\Rightarrow)\)証明1

(対偶法)

\(a\)と\(b\)が素でないとき1より大きい公約数をもち、それを\(m\)とすると\(ax+by\)は\(m\)の倍数であるが右辺が\(1\)なので整数解を持たない

\((\Leftarrow)\)証明2


\(a\)と\(b\)が互いに素なとき\(a,2a,⋯,(b−1)a\)を\(b\)で割った余りは全て異なる。(補題)

よって余りが\(1\)となるようなものが存在する。
それを\(ma\)とおき,\(b\)で割った商を\(n\)とおくと、
\(ma=bn+1\),   \(am−bn=1\)となる。
\((m,−n)\) が整数解である

補題

(背理法)

\(ia\)と\(ja(i>j)\)を\(b\)で割った余りが同じだと仮定
\((i−j)a\)は\(b\)の倍数となるが\(1≤i−j<b\) かつ\(a\)と\(b\)は互いに素なので矛盾

\(ax+by=c\)(命題2)

\(a,b\)が\(0\)でない整数とする
\(ax+by=c\)が整数解を持つ\(\Leftrightarrow\)\(c\)が\(gcd(a,b)\)の倍数

\((\Rightarrow)\)証明3

\(gcd(a,b)=k\)とする

整数解\(m.n\)に対し\(am+bn=k(a'm+b'n)=c\)
よって \(c\)は\(k\) の倍数。

\((\Leftarrow)\)証明4

\(c=kt\)とする

\(ax+by=c \\ \Leftrightarrow k(a'x+b'y)=c \\ \Leftrightarrow a'x+b'y=t \\ \Leftrightarrow a'\frac{x}{t}+b'\frac{y}{t}=1\)

\(a',b'\)は互いに素なので\(\frac{x}{t}=m ,\,\frac{y}{t}=n\)を満たす整数\(m,n\)が存在し(命題2)、\((x,y)=(tm,tn)\)も整数となるので存在が示せた

10.一次不定方程式の一般解

\(ax+by=c\)の一般解の求め方

\(1.\)両辺を\(gcd(a,b)\)で割って係数を互いに素にする
\( \,\,\,\,\, (gcd(a,b)|c\)でないなら解はない(命題2))

\(2.\,\)解を一つ見つけ、\(x_0,y_0\)とする

\(3.a(x-x_0)=-b(y-y_0)\)と変形

\(4.\)任意整数で\(\begin{cases} x=bm+x_0 \\ y=an+y_0 \end{cases}\)と一般解を得る

問題点

\(1.\)係数\(a,b\)が大きすぎて解が見つけられない
    →ユークリッドの互除法の応用

\(2.\,\)定数項\(c\)が大きすぎて解がみつけられない
    →\(mod\)の応用

1.ユークリッドの互除法の応用

\(ax+by=1\)かつ\(a,b\)が互いに素のとき
右辺の1を互除法の逆操作で\(am+bn\)にする


\(163x+78y=1 \)の整数解を1組求めよ

解説

\(163=78 \times 2+ \bf 7 \rm \\ 78=7 \times 11+ \bf 1\)

\(\bf 1 \rm =78- \bf 7 \rm \times 2 \\=78-(163-78 \times 2) \times 11\\=163 \cdot(-11)+78\cdot 23 \)


整数解の一つは\(\bf (-11,23)\)


2.合同式の応用

両辺の剰余が等しくなることを利用して候補を絞る


例、\(25x+17n=1623\)の整数解を1組求めよ

解説

\(25x+17y=1623 \\ \Leftrightarrow 17(x+y)+8x=17\cdot 95+8 \)

\(8x\equiv 8\,(mod\,17)\)
\(x=1\)のときにこれを満たす


整数解の一つは\(\bf (1,94)\)