数学A 不定方程式 問題 11 解説

方針・初手

整数係数の不定方程式 $ax+by=c$ が整数解をもつためには、$\gcd(a,b)$ が $c$ を割り切ることが必要である。

まず $756$ と $232$ の最大公約数をユークリッドの互除法で求め、その最大公約数が右辺 $1$ を割り切るかを調べる。

解法1

ユークリッドの互除法により、$756$ と $232$ の最大公約数を求める。

$$ 756=232\cdot 3+60 $$

$$ 232=60\cdot 3+52 $$

$$ 60=52\cdot 1+8 $$

$$ 52=8\cdot 6+4 $$

$$ 8=4\cdot 2+0 $$

したがって、

$$ \gcd(756,232)=4 $$

である。

次に、不定方程式

$$ 756x+232y=1 $$

について考える。

左辺の $756x$ と $232y$ は、$756$ も $232$ も $4$ の倍数であるから、任意の整数 $x,y$ に対してどちらも $4$ の倍数である。

したがって、左辺 $756x+232y$ も必ず $4$ の倍数である。

しかし右辺は $1$ であり、$1$ は $4$ の倍数ではない。

よって、整数 $x,y$ に対して

$$ 756x+232y=1 $$

が成り立つことはない。

したがって、この不定方程式は整数解をもたない。

解説

この問題の核心は、不定方程式 $ax+by=c$ の整数解の存在条件である。

$ax+by$ の形で表される整数は、必ず $\gcd(a,b)$ の倍数になる。したがって、右辺 $c$ が $\gcd(a,b)$ の倍数でなければ、整数解は存在しない。

本問では $\gcd(756,232)=4$ であり、右辺 $1$ は $4$ で割り切れない。そのため、実際に $x,y$ を探す必要はなく、最大公約数だけで整数解が存在しないことを示せる。

答え

(1)

$$ \gcd(756,232)=4 $$

(2)

$756x+232y$ は任意の整数 $x,y$ に対して $4$ の倍数であるが、右辺 $1$ は $4$ の倍数ではない。よって、

$$ 756x+232y=1 $$

は整数解をもたない。