二元一次不定方程式と鳩ノ巣原理

はじめに

てきとーに書いてみました

鳩ノ巣原理とは

$n<m\ \ (n,m\in\mathbb{N})$とするとき,$n$個の巣に$m$羽の鳩が入る時，必ず2匹以上入っている巣が存在する.
という主張である.
考えてみれば当たり前のことですが，とても面白いものです.

二元一次不定方程式について

ax+by=cが整数解を持つ条件

$x,y$に関する二元一次不定方程式 $ax+by=c$ が整数解を持つ$\iff c$ は $\mathrm{gcd}(a,b)$ の倍数

これを示す.補題として
$ax+by=1$が整数解を持つ$\iff a $と $b$ は互いに素
これをまず示す.

(証明)
($\implies$)対偶をとると，$(a と b は互いに素)\lnot \implies(ax+by=1が整数解を持つ)\lnot$
ここで$a,b$の公約数を$d\geq2$とするとき$ax+by$は$d\cdot k(x,y)$となるので，$k(x,y)=\frac{1}{d}$となり整数解を持たない.
($\impliedby$)$ax+by=1\iff ax=b(-y)+1$ここで「巣」を$ax$を$b$で割った余りとし，「鳩」を$a\cdot1,a\cdot2,\cdots a\cdot n$とするとき，「巣」と「鳩」の数が等しいので鳩ノ巣原理の主張が使えないと思うが，同じ「巣」に鳩が入らない事を示せば今回の主張が得られる.
同じ「巣」に「鳩」が入ると仮定すると
$i<j$としたとき，$a\cdot i\equiv a\cdot j\ (\mathrm{mod}\ b)\iff i\equiv j\ (\mathrm{mod}\ b)$となり
$i=j$である.よって同じ「巣」に「鳩」が入ることはないので主張が得られた.
$\therefore\ $$ax+by=1$が整数解を持つ$\iff a $と $b$ は互いに素

ここから，
$x,y$に関する二元一次不定方程式 $ax+by=c$ が整数解を持つ$\iff c$ は $\mathrm{gcd}(a,b)$ の倍数
を示す.

(証明)
$(\implies)$$a,b$は$\mathrm{gcd}(a,b)$の倍数なので整数解$m,n$に対して，$am+bn$も$\mathrm{gcd}(a,b)$の倍数である.
即ち，$\mathrm{gcd}(a,b)k(x,y)=c$であるので，$c$は$\mathrm{gcd}(a,b)$の倍数である.
$(\impliedby)$$a=p\cdot \mathrm{gcd}(a,b),b=q\cdot \mathrm{gcd}(a,b)$とする.$\ (\mathrm{gcd}(p,q)=1)$
先ほどの補題から$pm+qn=1$は整数解を持つ.両辺に$\mathrm{gcd}(a,b)$をかけると
$am+bn=\mathrm{gcd}(a,b)$となる.
よって，$cが\mathrm{gcd}(a,b)$の倍数のとき$k$倍$(c=\mathrm{gcd}(a,b)\cdot k)$すれば右辺が$c$になる.
$\therefore\ $$x,y$に関する二元一次不定方程式 $ax+by=c$ が整数解を持つ$\iff c$ は $\mathrm{gcd}(a,b)$

二元一次不定方程式の解き方

ユークリッドの互除法を使う解き方と合同式を使う解き方で解いてみます.

問題

二元一次不定方程式$\ 47x+43y=1$を解け.

ユークリッドの互除法

$47=43\cdot 1+4$
$43=4\cdot 10+3$
$\ 4\ =3\cdot 1+1$
より
$1=4-3\cdot 1$
$1=4-(43-4\cdot10)\cdot1$
$1=(47-43\cdot1)-(43-(47-43\cdot1)\cdot10)$
$1=47\cdot11-43\cdot12$
これを与式から引いて
$47(x-11)+43(y+12)=0$
$-47(x-11)=43(y+12)$
$\mathrm{gcd}(47,43)=1$より$x-11=43k,y+12=-47k$である.
$\therefore\ x=43k+11,y=-47k-12\ (k\in\mathbb{Z})$

合同式

$43$を法とすると
$47x+43y\equiv1$
であり，また
$47\equiv4$
$47x\equiv 4x$
よって，$4x\equiv1\iff x\equiv\frac{1}{4}\iff x\equiv\frac{44}{4}\ (\because\ \mathrm{gcd}(4,1)=1)$
$\therefore\ x\equiv11$
このことから，$x=43k+11$
与式に代入して$43y=1-47(43k+11)\iff y=-47k-12$
$\therefore\ x=43k+11,y=-47k-12\ (k\in\mathbb{Z})$

参考文献

・高校数学の美しい物語
・AKITOの特異点-鳩を探せ

最後に

ここまで，読んでくださってありがとうございます.この記事から得られるものがあれば嬉しく思います.誤植や不明な点がございましたらTwitter Rime_mathまで連絡ください.