(高校生むけ)合同式の基本
合同式の基本
(※今回の記事は生徒に解説するために作ったので,100％高校範囲です.)
断りがなければ,$a,b,c$を整数,$k,n,m$を0以上の整数とします.
1.合同式とは
合同式とは,整数の剰余(あまりのことね.)に着目した式のことです.
例えば,$a$と$bをm$で割った剰余が等しいことを
$a\equiv b\m n)$
と書きます.
これを$a,b$は$n$を法として合同($a$ and $b$ are congruent modulo $n$)と言います.
(modulo【前】:〜を法として)
例えば,
$$
57\equiv 7 \m 5), \ 57\equiv 2 \m 5), \ 57\equiv -3 \m 5)
$$
です.
これは適切な整数$K$を用いて$57$を,
$57=5K+7, \ 57=5K+2, \ 57=5K-3$
と表せることに対応していますね.
2.合同式の性質1
$(\mathrm {i})a\equiv a\m n)$(反射律)
$(\mathrm {ii})a\equiv b\m n)\implies b\equiv a\m n)$(対称律)
$(\mathrm {iii})a\equiv b\m n)\mathrm{かつ}b\equiv c\m n)\implies a\equiv c\m n)$(推移律)
任意の整数$a,b,c,d$に対し,$a\equiv b\m n),c\equiv d\m n)のとき,$
$(\mathrm {I})a+c\equiv b+d\m n)$(加法)
$(\mathrm {II})a-c\equiv b-d\m n)$(減法)
$(\mathrm {III})ac\equiv bd\m n)$(乗法)
$(\mathrm {I})$
条件より,
$a+c\equiv b+c\m n),b+c\equiv b+d\m n)$
推移律$(\mathrm {iii})$より,
$\therefore a+c\equiv b+c\equiv b+d\m n).$
$(\mathrm {II})$
条件より,$c,d$は任意なので$c\to -c,d\to -d$と置き換えて,$(\mathrm {I})$より,
$\therefore a-c\equiv b-d\m n).$
$(\mathrm {III})$
条件と$(\mathrm {I})$より,
$ac\equiv bc\m n),bc\equiv bd\m n)$
推移律$(\mathrm {iii})$より,
$\therefore ac\equiv bc\equiv bd\m n).$
これで合同式においても等式と同様に加減乗が保障されました.
難しかったら最悪$a=b+nk,c=d+nl$と置けば証明できます.
$(\mathrm {IV})$任意の整数$a,b$に対し,$ac\equiv bc\m n)$で$c$と$n$が互いに素のとき,$a\equiv b\m n)$(除法)
$(\mathrm {IV})$
$ac\equiv bc\m n)$即ち$(a-b)c\equiv 0\m n)$より,$(a-b)c$は$n$の倍数.
$c$と$n$が互いに素ゆえ,$(a-b)$は$n$の倍数となるから
$\therefore a\equiv b\m n)$.
条件付きで加減乗(除)が保障されました.
$(\mathrm {V})$$a\equiv b\m n)\implies a^m\equiv b^m\m n)$
$(\mathrm {V})$
数学的帰納法を用いる.
$(\mathrm {i})m=1$のときは自明.
$(\mathrm {ii})m=k$のとき$a^k\equiv b^k\m n)$と仮定すると,$m=k+1$のとき$a^{k+1}\equiv b^{k+1}\m n)$を示す.
仮定と条件より,
$a^{k}\cdot a\equiv b^{k}\cdot a\m n), \ a\cdot b^{k}\equiv b\cdot b^{k}\m n)$だから,
$\therefore a^{k+1}\equiv a\cdot b^{k}\equiv b^{k+1}\m n) \ \ldots m=k+1$でも成立.
以上により,題意は示された.
$(\mathrm {III})$を使ってもよいならもっと簡単に示せますね.
$(\mathrm {VI})$$p$を素数とすると,
$a^p\equiv a\m p)$
$(\mathrm {VII})$$p$が素数,$a,p$が互いに素のとき,
$a^{p-1}\equiv 1\m p)$
$(\mathrm {VI})$
$k=1,...,p-1$のとき,
$k_p\C_k=p_{p-1}\C_{k-1}$ , $p,k$は互いに素より,
${}_p\C_k$は$p$の倍数だから,二項定理より,
$a^p=[(a-1)+1]^p=(a-1)^p+{}_p\C_1(a-1)^{p-1}+...+{}_p\C_{p-1}(a-1)+1\equiv (a-1)^p+1\m p)$
よって,これを繰り返すと,
$a^p\equiv (a-1)^p+1\equiv(a-2)^p+2\equiv...\equiv1^p+a-1\equiv a\m p)$
を得る.
$(\mathrm {VII})$
条件より$(\mathrm {IV})$が使えるので,$(\mathrm {VI})$の両辺を$a$で割ると,
$\therefore a^{p-1}\equiv 1\m p).$
3.使用例1:ユークリッドの互除法
合同式を使うと,次のようになります.
$0< r_k<...< r_1< b$
$a\equiv r_1 \m b), \ b\equiv r_2 \m r_1), ...,r_{k-1}\equiv0\m r_k)\implies\gcd(a,b)=r_k$
$\dfrac{10033}{12877}$を約分せよ.(数検1級 2010/4)
$12877\equiv 2844\m 10033)$
$10033\equiv 1501\m 1244)$
$2844\equiv 1343\m 1501)$
$1501\equiv 158\m 1343)$
$1343\equiv 79\m 158)$
$158\equiv 0\m 79)$
より,$\gcd(10033,12877)=79$だから,
$$\therefore \frac{10033}{12877}=\frac{10033/79}{12877/79}=\frac{127}{163}.$$
4.使用例2:一次不定方程式
次の方程式の整数解をすべて求めよ.
$72x+32y=3$
$71x+32y \equiv 71x \equiv 7x\equiv 3 \m 32)...(1)$
$3\equiv 35\m 32)$($(1)$より,右辺が$7$の倍数になるようにする)より,
$7x\equiv 35\m 32)$
$7$と$32$は互いに素だから,
$x\equiv 5\m 32)$
よって,$x=32k+5(k\in \mathbb Z)$と表せるから,
$32y=-71x+3=-71(32k+5)+3=-71\cdot32k-352$
故に,
$\therefore x=32k+5,y=-71k-11 (k\in \mathbb Z).$
特殊解を求めなくても一次不定方程式を解くことができました.
4.演習問題
$(1)2^{50}$を7で割った余りを求めよ.(易)
$(2)17^{50}$を9で割った余りを求めよ.(易)
$(3)23^{100}$を19で割った余りを求めよ.(易)
$(4)n^5-n$が$30$の倍数になることを示せ.(普)
$(5)n$が自然数のとき,$2^{6n-5}+3^{2n}$が$11$の倍数となることを示せ.(普)
$(6)n$が自然数のとき,$5^{2n-1}+7^{2n-1}+23^{2n-1}$が$35$の倍数となることを示せ.(普)
$(7)$$\sum_{k=1}^nk!$が平方数となるような$n$を全て求めよ.(難)
(ヒント:$0$から$9$までの平方の$1$の位に注目せよ.)
$(8)$整式$x^{2023}-1$を整式$x^4+x^3+x^2+x+1$で割ったときの余りを求めよ.(難)
(ヒント:$x^4+x^3+x^2+x+1\equiv 0\m x^4+x^3+x^2+x+1)$より,$x^5-1\equiv 0\m x^4+x^3+x^2+x+1)$)
$(9)$自然数$n$に対し,$n^2+2,n^4+2,n^6+2$の最大公約数を求めよ.(難)
(ヒント:$n^4+2,n^6+2$と$n^2+2$でそれぞれ互除法.)