一次不定方程式

SNS Accounts

SHARE

Side Menu

高校数学編

論理・集合

数・式

変化

空間

確率

論理・集合

数・式

群環体論

線形代数学

整数論

表現論

実解析学

複素解析学

関数解析学

位相幾何学

微分幾何学

代数幾何学

Side Menu

数・式

有理式

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

不定方程式

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

補題

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

\((\Rightarrow)\)

(背理法)

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

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

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

\((\Rightarrow)\)

(対偶法)

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

POINT

他の倍数の判定法も同じように示せる

\((\Leftarrow)\)


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

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

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

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

\((\Rightarrow)\)

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

\((\Leftarrow)\)

\(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)\)

←ユークリッドの互除法


Menu