競技数学解説

OMC対策（N分野：合同式）

OMC,競技数学,合同式

本記事の前提知識

　前提知識は特になし．
　今回の記事は，非常に基本的なところからスタートするので，練習問題も多めとなっている．不安がある人は確認しながら進めてほしい．

合同式の定義と性質

　合同の定義とは，次のようなものである．

整数の合同

　 $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$
（乗法） $a c \equiv b d \mod n$ 　とくに　 $a^{k} \equiv b^{k} \mod n$

　証明略．気になる人はこちらをどうぞ．

　加減乗の $3$ つの演算については，公式1のようによい性質を持っているが，除法については少し面倒である．

合同式と除法

　 $a k \equiv b k \mod n$ であり， $n$ と $k$ が互いに素であるとき， $a \equiv b \mod n$ が成り立つ．

（問題）「 $n$ と $k$ が互いに素」という条件を取り除いて， $a ≢ b \mod n$ となる例を考えよ．

問題の答え

　単純な例としては，

2 \equiv 4 \mod 2

と

1 ≢ 2 \mod 2

が考えられる．（この例を一般化すると，

a k \equiv b k \mod k

と

a ≢ b \mod k

とも言える．）

　次の問いに答えよ．
(1)　 $10 a + b \equiv - a + b \mod 11$ を示せ．
(2)　(1)を用いて， $10000 a + 1000 b + 100 c + 10 d + 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)の解答

10 a + b \equiv (10 a + b) - 11 a = - a + b

である．

(2)の解答

N = 10000 a + 1000 b + 100 c + 10 d + e = 10 (1000 a + 100 b + 10 c + d) + e

に対して(1)を用いると

N \equiv - (1000 a + 100 b + 10 c + d) + e

である．さらに変形して，

10 (- 100 a - 10 b - c) - d + e

に対して(1)を用いると

N \equiv (100 a + 10 b + c) - d + e

である．あと何回か同じことをすればよい．
　なお，この証明は

11

の倍数判定法の証明にも適用できる．

(3)の解答

2^{34} = 4^{17} \equiv (- 1)^{17} = - 1 \equiv 4

と計算するか，

2^{34} = 2^{32} \times 4 = 16^{8} \times 4 \equiv 1^{8} \times 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 b k \mod n$ が成り立つ自然数 $b$ が存在する．このような $b$ は $0$ 以上 $n - 1$ 以下の中にただ一つである（これを「 $n$ を法としてただ一つ」ともいう）．
　従って $\frac{a}{k} \equiv b \mod n$ と書くことが可能であり，実際にこのように書く場合がある．

　なお，このような記法をする場合，最初の定義のままでは危うい．最初の定義は，整数に対してのみ定義されていたからである．そこで一応，分数にまで拡張した合同式の定義を記しておく．ただし，この定義をきちんと把握しておくことが役立つかと言うと，そうでもないだろう．

分数の合同式

　 $2$ つの分数 $\frac{a}{b}, \frac{c}{d}$ が法 $n$ ( $≧ 2$ )に関して合同とは，

$b, d$ が $n$ と互いに素である
$a d - b c$ が $n$ の倍数である

　以上の両方が成り立つことを意味する．これを $\frac{a}{b} \equiv \frac{c}{d} \mod n$ と記述する．

　 $a d - b c$ がどこから来たのか？という疑問があるかもしれないが，それは $\frac{a}{b} - \frac{c}{d}$ を計算してみればわかる．

問題２(5)の補足

　問題2(5)は「 $101$ を法として $\frac{1}{2}$ と合同な整数は何か」という問いだと考えられる．これは，以下のように計算できる．
　 $\frac{1}{2} \equiv \frac{1 + 101}{2} = 51$

（問題）同様にして，問題2(6)を分数の合同式を使って表せ．

問題の答え

\frac{1}{4} \equiv \frac{1 + 101}{4} = \frac{51}{2} \equiv \frac{51 + 101}{2} = 76

もしくは　

\frac{1}{4} \equiv \frac{1 - 101}{4} = - 25 \equiv - 25 + 101 = 76

　など

　

\frac{1}{8} \equiv \frac{1 + 101}{8} = \frac{51}{4} \equiv \frac{51 + 101}{4} = 38

もしくは　

\frac{1}{8} \equiv \frac{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 > 10

に注意して，

n + 10 = 20, 25, 50, 100

であり，

n = 10, 15, 40, 90

．

　 $_{p - 1} C_{2 k} \equiv 1 \mod p$ を示せ．ただし $2 k < p - 1$ である．

解答

p = 2

のときはすぐに確かめられる．以下，

p ≧ 3

とする．
　

_{p - 1} C_{2 k} = \frac{(p - 1)!}{(2 k)! (p - 2 k - 1)!}

である．ここで
　

\begin{aligned} (2 k)! & = 1 \cdot 2 \dots (2 k - 1) \cdot 2 k \\ = (- 1) (- 2) \dots (- 2 k + 1) (- 2 k) \\ \equiv (p - 1) (p - 2) \dots (p - 2 k + 1) (p - 2 k) \end{aligned}

より，

_{p - 1} C_{2 k} = \frac{(p - 1)!}{(2 k)! (p - 2 k - 1)!} \equiv \frac{(p - 1)!}{(p - 1)!} = 1

OMCの例題

OMC177(B)
OMC025(A)
OMC145(C)
OMC203(G) ←かなり難しめ

投稿日：3月22日

更新日：3月22日

この記事を高評価した人

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

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

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

て

841

他の人のコメント

コメントはありません。

読み込み中

て

OMC対策（N分野：合同式）

本記事の前提知識
合同式の定義と性質
分数の合同式
練習問題