仮面浪人生の日記

DAY 23 合同式

今回は合同式について勉強した。
合同式は学習指導要領の範囲外であるが、知っていると整数問題でかなり有利である。

定義

$a-b$ が $m$ の倍数であるとき、 $a,b$ は $m$ を法(英:modulus)として合同といい、 $a\equiv b(mod\,m)$ とかく。

性質

1. $a\equiv a(mod\,m)$

2. $a\equiv b(mod\,m)$ ならば $b\equiv a(mod\,m)$

3. $a\equiv b, b\equiv c(mod \,m)$ ならば $a\equiv c(mod\,m)$

さらに、 $a\equiv b,c\equiv d (mod\,m)$ のとき

4. $a+c \equiv b+d (mod\,m)$

5. $a-c \equiv b-d (mod\,m)$

6. $ac \equiv bd (mod\,m)$

7. 自然数 $n$ に対し $a^n\equiv b^n (mod\,m)$

証明

1. $a-a=0=0\cdot m$ となるから $a-a$ は $m$ の倍数である。 $\square$

2. 条件より $a-b=km$ となる整数 $k$ が存在するから $K=-k$ ととると $K$ は整数であって

$b-a=-(a-b)=-km=Km$ となるから $b-a$ も $m$ の倍数である。 $\square$

3. 条件より $a-b=km,b-c=lm$ となる整数 $k,m$ が存在するから $b=lm+c$

よって $a-(lm+c)=km$

$a-c=km+lm=(k+l)m$ となるから $a-c$ はmの倍数である。 $\square$

4. 条件より $a-b=km,c-d=lm$ となる整数 $k,l$ が存在する。

これより $(a+c)-(b+d)=km+lm=(k+l)m$ となって $(a+c)-(b+d)$ は $m$ の倍数である。 $\square$

5. 4.と同様.

6. $a=b+km$ より $ac=bc+kcm$ 、また $d=c+lm$ より $bd=bc+lbm$

これより $ac-bd=(kc-lb)m$ であって $ac-bd$ は $m$ の倍数である。 $\square$

7. 6で $a=c,b=d$ の場合を $n$ 回適用すれば公式を得る。 $\square$

これを利用して次の問題は簡単に解ける。

問題

$13^{2018}$ を $8$ で割った余りを求めよ。(チャート式改)

回答

$13^2=169$ を $8$ で割った余りは $1$ であるから

$13^{2018} \equiv {13^{2}}^{1009} \equiv 1^{1009} \equiv 1(mod\,8)$

よって $1$

このように $a^n$ の余りを求める問題でnが非常に大きいとき性質6,7がとくに役に立つ。

1~7の性質は普通の等式とほぼ同じ性質なので、合同式はほとんど等式のように扱うことができる。

ただ一つ普通の等式と違うのは除法が（普通には)できないことである。

性質

8. $a,m$ が互いに素であるなら $ax\equiv ay \Rightarrow x\equiv y(mod\,m)$

証明

条件より $ax-ay=a(x-y)=km$

$a,m$ は互いに素であるが $km$ は $a$ の倍数であるから、 $k$ は $a$ の倍数であって

$k=al$ とかけるからこれを代入して

$a(x-y)=alm$

よって $x-y=lm$ となり $x-y$ はmの倍数である。 $\square$

$a,m$ が互いに素でないと2~3行目が使えないので除法は使えない。

問題

次の合同方程式を解け。なお合同方程式を解くとは $x\equiv a(mod\,m)$ ( $a$ は $m$ より小さい自然数)の形にすることである。

(1) $4x\equiv 3(mod\,5)$

(2) $3x\equiv 6(mod\,9)$

(チャート式改)

(2)について、いかにも割れそうな形をしているが、3と9は互いに素ではないため性質8は使えない。このようなときは、実際に値を代入して条件を満たすものを総当たりで探すこととなる。総当たりとはいってもこの問題では1から8までの8個の自然数しかないため、比較的容易である。もちろん(1)の解法のほうが格段に早いのだが、こういった泥臭い方法も知っておくべきだろう。

回答

(1)

$3\equiv 8(mod\,5)$ より $4x\equiv8 (mod\,5)$

$4$ と $5$ は互いに素であるから

$x\equiv4 (mod\,5)$

(2)

$3\cdot 2 = 6,3\cdot 5 = 15 \equiv 6,3\cdot 8 = 24 \equiv 6 (mod\,9)$ より

条件をみたす $x$ は $x=2,5,8$

よって $x\equiv 2,5,8(mod\,9)$

(2)で、2行目につられて最後の合同記号をイコールにしかけたが、合同式を解くとは $x\equiv a(mod\,m)$ (aはmより小さい自然数)の形にすることなのでしっかり合同記号でかこう。

いや、そもそも高校範囲外なので問われることはないのだが、将来的に入ったときのために一応書いておく。

今日の勉強時間

チャート式基礎からの数学I+A 2時間29分

合計：２時間２９分