読者です 読者をやめる 読者になる 読者になる

一次不定方程式

一次不定方程式で、整数論の基礎的な部分を学べるのでまとめてみた。次の(1)~(4)は本質的には同じだ。

 

(1)次の一次不定方程式の整数解をすべて求めよ。

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

(2)次の直線の通る格子点をすべて求めよ。

        \displaystyle 7x + 10y = 1

(3)xの解を求めよ。

        \displaystyle 7x≡1 (mod\ 10)

(4)yの解を求めよ。

        \displaystyle 10y \equiv 3y \equiv 1 (mod\ 7)

 ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

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

適当に見つけた解(\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となり、結局、(1)(2)の解答は次のとおり。(\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は整数) \]

 

(3)は \displaystyle mod\ 10なので下一桁を見ればよい。九九表の7の段(カッコ書きは下一桁)を見れば、下一桁の数値がすべて異なっているのが分かる(これは7と10が互いに素だから。1、3、9の段も下一桁はすべて異なっている。なお、1、3、7、9は剰余類Z/10Zの乗算で群をなす。なお、群は閉結単逆を満たせば良い(閉じていて、結合法則が成り立ち、単位元、逆元がある))。ここで \displaystyle 7x≡1 (mod\ 10)なので、1桁目が1となっているのは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)とは、「nより小さい自然数の中でnと互いに素なものの個数」であり、上で述べたとおり、\displaystyle φ(10)=4(1、3、7、9の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)と求まる。

 

(4)は \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)と求まる。

 

(参考)(7と10ではなく、) 3と5の場合のイメージ

f:id:beatle_hat:20150222142551j:plain