一次不定方程式 - フィンチの憂鬱

一次不定方程式で、整数論の基礎的な部分を学べるのでまとめてみた。次の（１）～（４）は本質的には同じだ。

（１）次の一次不定方程式の整数解をすべて求めよ。

　　　　　　　　 $\displaystyle 7x + 10y = 1　・・・①$

（２）次の直線の通る格子点をすべて求めよ。

　　　　　　　　 $\displaystyle 7x + 10y = 1$

（３） $x$ の解を求めよ。

　　　　　　　　 $\displaystyle 7x≡1 （mod\ 10）$

（４） $y$ の解を求めよ。

　　　　　　　　 $\displaystyle 10y \equiv 3y \equiv 1 （mod\ 7）$

ｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰｰ

（１）の形式で出題された場合はひとつの解を求めて解くことができる（仮に係数が大きい場合でも互除法で必ず一般解は求まる（当然、解の存在する場合（右辺の値が、係数の最大公約数の倍数となっている場合）））。

適当に見つけた解（ $\displaystyle x=3\ ,y=-2$ ）を入力した $\displaystyle 7(3)+10(-2)=1$ から①を辺々引けば、 $\displaystyle 7(-x+3)=10(y+2)$ となる。7と10は互いに素なので $\displaystyle (-x+3)$ は10の倍数となり、 $\displaystyle (-x+3)=10s$ （ $\displaystyle s$ は整数）とおけるので、 $\displaystyle (y+2)=7s$ となり、結局、（１）（２）の解答は次のとおり。（ $\displaystyle x$ が10減って、 $\displaystyle y$ が7増えても与式の左辺の値は変わらない。）

\[ \left( \begin{array}{c} x \\ y \end{array} \right) = \left( \begin{array}{l} \ \ 3 \\ -2 \end{array} \right) + \left( \begin{array}{l} -10 \\ \ \ 7 \end{array} \right) s \ \ \ （sは整数） \]

（３）は　 $\displaystyle mod\ 10$ なので下一桁を見ればよい。九九表の７の段（カッコ書きは下一桁）を見れば、下一桁の数値がすべて異なっているのが分かる（これは7と10が互いに素だから。１、３、９の段も下一桁はすべて異なっている。なお、１、３、７、９は剰余類Z／10Zの乗算で群をなす。なお、群は閉結単逆を満たせば良い（閉じていて、結合法則が成り立ち、単位元、逆元がある））。ここで　 $\displaystyle 7x≡1 （mod\ 10）$ なので、１桁目が１となっているのは3のときでそれが答（すなわち、 $\displaystyle x≡3（mod\ 10）$ であり、 $\displaystyle x=3+10s（sは整数）$ ）

（九九表）

1	2	3	4	5	6	7	8	9
2	4	6	8	10	12	14	16	18
3	6	9	12	15	18	21	24	27
4	8	12	16	20	24	28	32	36
5	10	15	20	25	30	35	40	45
6	12	18	24	30	36	42	48	54
7 （7）	14 （4）	21 （1）	28 （8）	35 （5）	42 （2）	49 （9）	56 （6）	63 （3）
8	16	24	32	40	48	56	64	72
9	18	27	36	45	54	63	72	81

〇オイラーの定理を使って解く場合、まず、オイラー数 $\displaystyle φ(n)$ とは、「ｎより小さい自然数の中でｎと互いに素なものの個数」であり、上で述べたとおり、 $\displaystyle φ(10)=4$ （１、３、７、９の４つ）である。ここで、オイラーの定理は次のとおり。

$\displaystyle x$ が $\displaystyle n$ と互いに素の場合、 $\displaystyle x^{φ(n)}≡1　(mod \ n)$

7と10は互いに素なので、 $\displaystyle 7^{φ(10)}≡7^4≡7・7^3≡7・3≡1　(mod \ 10)$ となり、 $\displaystyle x≡3　(mod \ 10)$ と求まる。

（４）は　 $\displaystyle mod\ 7$ であるが7は素数なので、原子根が存在する。7の原子根は3であり、1～6はそれぞれ3の累乗で表せる。　 $｛1,2,3,4,5,6｝$ は　 $｛3^6( \equiv 1),3^2( \equiv 2),3^1( \equiv 3),3^4( \equiv 4),3^5( \equiv 5),3^3( \equiv 6)｝$ に対応する。オイラーの定理で解いた場合とおなじであるが、 $\displaystyle 3^6≡3・3^5≡3・5≡1　(mod \ 7)$ となり、 $\displaystyle x≡5　(mod \ 7)$ と求まる。