0

(高校生むけ)合同式の基本

132
0
$$\newcommand{C}[0]{\mathrm C} \newcommand{m}[0]{ \ (\mathrm{mod} \ } $$

合同式の基本

(※今回の記事は生徒に解説するために作ったので,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

合同式の性質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)$(推移律)

合同式の性質2-1

任意の整数$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)$(乗法)

合同式の性質2-2

$(\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$と置けば証明できます.

合同式の性質2-2

$(\mathrm {IV})$任意の整数$a,b$に対し,$ac\equiv bc\m n)$$c$$n$が互いに素のとき,$a\equiv b\m n)$(除法)

合同式の性質2-2

$(\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$でそれぞれ互除法.)

投稿日:202382
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

東北大学工学研究科出身 できるだけ受け売りはせず,自分で思いついた解法や妄想を備忘録がてら書き綴っていこうと思います.

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中