OMC対策（N分野：合同式）
本記事の前提知識
前提知識は特になし．
今回の記事は，非常に基本的なところからスタートするので，練習問題も多めとなっている．不安がある人は確認しながら進めてほしい．
合同式の定義と性質
合同の定義とは，次のようなものである．
$2$つの整数$a,b$が法$n$($≧2$)に関して合同とは，$a-b$が$n$の倍数であることを意味する．
これを$a \equiv b \mod n$と記述する．
「$2$つの整数$a,b$を$n$で割った余りが等しいとき」という表現の定義もある．この表現は，負の整数の割り算を理解していなければならないので，個人的にはあまり好みではない．
次のうち正しいものを全て選べ．
(1) $13 \equiv 1 \mod 6$
(2) $42 \equiv 7 \mod 12$
(3) $-10 \equiv 8 \mod 9$
(4) $3^4 \equiv 1 \mod 20$
(5) $n^2 \equiv -1 \mod n+1 $（$n ≧ 1$）
解答
(1)(3)(4)は正しい．
(5)は$n=1$のとき正しく，それ以外のときは正しくない．その証明を考えてみてほしい（答えは次の折り畳み）．
(5)について
$n^2-(-1)=n^2+1$が$n+1$の倍数であるかどうかを考えたい．
$n^2+1=(n+1)(n-1)+2$と変形すると，$2$が$n+1$の倍数のとき，(5)は正しい式であるとわかる．
つまり$n=1$のときに限って(5)は正しい．
$a \equiv b \mod n$，$c \equiv d \mod n$であるとき，以下が成り立つ．
（加法）$a+c \equiv b+d \mod n$
（減法）$a-c \equiv b-d \mod n$ とくに $a-b \equiv 0 \mod n$
（乗法）$ac \equiv bd \mod n$ とくに $a^k \equiv b^k \mod n$
証明略．気になる人は こちら をどうぞ．
加減乗の$3$つの演算については，公式1のようによい性質を持っているが，除法については少し面倒である．
$ak \equiv bk \mod n$であり，$n$と$k$が互いに素であるとき，$a \equiv b \mod n$が成り立つ．
（問題）「$n$と$k$が互いに素」という条件を取り除いて，$a \not\equiv b \mod n$となる例を考えよ．
問題の答え
単純な例としては，$2 \equiv 4 \mod 2$と$1 \not\equiv 2 \mod 2$が考えられる．（この例を一般化すると，$ak \equiv bk \mod k$と$a \not\equiv b \mod k$とも言える．）
次の問いに答えよ．
(1) $10a+b \equiv -a+b \mod 11$を示せ．
(2) (1)を用いて，$10000a+1000b+100c+10d+e \equiv a-b+c-d+e \mod 11$を示せ．
(3) $2^{34}$を$5$で割った余りを求めよ．
(4) $12^{34}$を$5$で割った余りを求めよ．
(5) $2^{100}$を$101$で割った余りは$1$である．これを用いて，$2^{99}$を$101$で割った余りを求めよ（わからなければ解答を見てから(6)に取り組むのがよい）．
(6) (5)と同様にして，$2^{98},2^{97}$を$101$で割った余りを求めよ．
(1)の解答
$10a+b \equiv (10a+b)-11a=-a+b$である．
(2)の解答
$N=10000a+1000b+100c+10d+e=10(1000a+100b+10c+d)+e$に対して(1)を用いると$N\equiv -(1000a+100b+10c+d)+e$である．さらに変形して，$10(-100a-10b-c)-d+e$に対して(1)を用いると$N\equiv (100a+10b+c)-d+e$である．あと何回か同じことをすればよい．
なお，この証明は$11$の倍数判定法の証明にも適用できる．
(3)の解答
$2^{34}=4^{17} \equiv (-1)^{17}=-1 \equiv 4$と計算するか，$2^{34}=2^{32}×4=16^8×4 \equiv 1^8×4=4$と計算するかだろう．
(4)の解答
$12^{34}\equiv 2^{34}$より，(3)と同じ$4$である．
(5)の解答
$2^{100} \equiv 1 \mod 101$より$2^{100} \equiv 102 \mod 101$である．両辺$2$で割れば$2^{99} \equiv 51 \mod 101$
(6)の解答
$2^{99} \equiv 51 \mod 101$から$2^{99} \equiv 152$とすれば，$2,4$で割ることができる．それぞれ$76,38$である．
なお，$2^{100}$からスタートする場合，$2^{100} \equiv 1 \equiv -100$としてから$4$で割る発想も自然である．
この(5)(6)の考え方を発展させると，分数の合同式を考えることができる．
分数の合同式
$n$と$k$が互いに素であるとき，任意の整数$a$に対して$a \equiv bk \mod n$が成り立つ自然数$b$が存在する．このような$b$は$0$以上$n-1$以下の中にただ一つである（これを「$n$を法としてただ一つ」ともいう）．
従って$\dfrac{a}{k} \equiv b \mod n$と書くことが可能であり，実際にこのように書く場合がある．
なお，このような記法をする場合，最初の定義のままでは危うい．最初の定義は，整数に対してのみ定義されていたからである．そこで一応，分数にまで拡張した合同式の定義を記しておく．ただし，この定義をきちんと把握しておくことが役立つかと言うと，そうでもないだろう．
$2$つの分数$\dfrac{a}{b},\dfrac{c}{d}$が法$n$($≧2$)に関して合同とは，
- $b,d$が$n$と互いに素である
- $ad-bc$が$n$の倍数である
以上の両方が成り立つことを意味する．これを$\dfrac{a}{b} \equiv \dfrac{c}{d} \mod n$と記述する．
$ad-bc$がどこから来たのか？という疑問があるかもしれないが，それは$\dfrac{a}{b}-\dfrac{c}{d}$を計算してみればわかる．
問題2(5)は「$101$を法として$\dfrac{1}{2}$と合同な整数は何か」という問いだと考えられる．これは，以下のように計算できる．
$\dfrac{1}{2} \equiv \dfrac{1+101}{2}=51$
（問題）同様にして，問題2(6)を分数の合同式を使って表せ．
問題の答え
$\dfrac{1}{4} \equiv \dfrac{1+101}{4}=\dfrac{51}{2} \equiv \dfrac{51+101}{2}=76$
もしくは $\dfrac{1}{4} \equiv \dfrac{1-101}{4}=-25 \equiv -25+101=76$ など
$\dfrac{1}{8} \equiv \dfrac{1+101}{8}=\dfrac{51}{4} \equiv \dfrac{51+101}{4}=38$
もしくは $\dfrac{1}{8} \equiv \dfrac{1+303}{8}=38$ など
練習問題
最後に，練習問題を用意した．
$n^2$が$n+10$で割り切れるような正整数$n$を全て求めよ．
解答
$n^2 \equiv n^2-(n+10)(n-10)=100 \mod n+10$
よって$n+10$が$100$の約数であればよい．$n+10 \gt 10$に注意して，$n+10=20,25,50,100$であり，$n=10,15,40,90$．
${}_{p-1}\mathrm{C}_{2k} \equiv 1 \mod p$を示せ．ただし$2k < p-1$である．
解答
$p=2$のときはすぐに確かめられる．以下，$p≧3$とする．
${}_{p-1}\mathrm{C}_{2k}=\dfrac{(p-1)!}{(2k)! (p-2k-1)!}$である．ここで
$\begin{aligned} (2k)!&=1 \cdot 2 \cdots (2k-1)\cdot 2k\\ &=(-1)(-2)\cdots(-2k+1)(-2k) \\ &\equiv(p-1)(p-2) \cdots (p-2k+1)(p-2k) \end{aligned}$
より，${}_{p-1}\mathrm{C}_{2k}=\dfrac{(p-1)!}{(2k)! (p-2k-1)!}\equiv \dfrac{(p-1)!}{(p-1)! }=1$
この記事を高評価した人
投稿者
