合同式のすべて

はじめに

　競技数学や受験数学ではあたりまえのように合同式が用いられます。ここで、この記事にたどり着いたみなさんに合同式の基礎から競技数学で用いるテクニックまで幅広く伝えたいです。
　まず、合同式とは、極論「場合分けのテクニック」です。場合分けの記法と議論を簡略化するものだと思ってもらえると概ね合っています。この理解のもとでこの記事を始めます。

目次

• 1　定義と基礎計算
• 2　除算
• 3　フェルマーの小定理 / ウィルソンの定理
• 4　中国剰余定理
• 5　その他の定理

1. 定義と基礎計算

合同式の定義と意味

合同式まわりの用語と記法について、整理する。

　つまり、$a\equiv b\ (\text{mod}\ n)$とは、$a$と$b$を$n$で割った余りが等しいことを意味する。このことを念頭にもっと例を挙げていく。

　ここで、たとえば場合分けのときにこのように記述をサボれる。

合同式での計算方法

　以下、合同式を用いた計算について考えていく。そのために以下の性質を示す。

(証明)
$a\equiv b\ (\text{mod}\ n)$とは、$n\vert (a-b)$を表していたため、
$a\equiv b\ (\text{mod}\ n)\Rightarrow n\vert (a-b)\Rightarrow n\vert\lbrace(a+c)-(b+c)\rbrace\Rightarrow a+c\equiv b+c\ (\text{mod}\ n)$
$a\equiv b\ (\text{mod}\ n)\Rightarrow n\vert (a-b)\Rightarrow n\vert\lbrace(a-c)-(b-c)\rbrace\Rightarrow a-c\equiv b-c\ (\text{mod}\ n)$
$a\equiv b\ (\text{mod}\ n)\Rightarrow n\vert (a-b)\Rightarrow n\vert(a-b)c\Rightarrow n\vert(ac-bc)\Rightarrow ac\equiv bc\ (\text{mod}\ n)$

　故に、次のような計算が許される。

　さらには、以下の公式を得る。

(証明)
$a^c=a\cdot a\cdots a\equiv b\cdot b\cdots b\equiv b^c\ (\text{mod}\ n)$

　以上のことから、「指数じゃないやつは全部先に余りに変換していい」ということがわかる。

　ちなみに、多くの読者は気にしていないかもしれないが「辺々足し算、辺々掛け算」のようなことも許される。もちろん代入も許される。基本的には「普通の足し算・引き算・掛け算ができる世界で許されていることはなんでもできる」と思ってもらって構わない。

　計算ができるようになったとして、記述をガチサボりしてみる。

　ここまでで受験数学は概ね終了です。あとは計算練習と実践をしてください。京都大学の整数問題をたくさん解けばいいと思います。だいたい$3$を法にするとうまくいきます。京大以外だとちゃんと法を考えないといけません。頑張って整数の過去問を解きまくってください。

　では、ここから下は完全に「マニア向け」「整数ファン向け」「競技数学選手向け」のお話になります。

2. 除算

計算のしくみと練習

　先ほど書いた通り、合同式において基本的に除算はできません。その理由を調べるためにまず「除算とはなにか」について考えていきます。

　小学生に戻ってください。「$6\divsymbol3$」をどのように求めましたか？　おそらく、$3x=6$という方程式の解を「$6\divsymbol3$」と記述したのだと思います。つまり、除算とは、方程式を解いていることにほかならないのです。

　では、合同式の世界での「$6\divsymbol3$」、つまり、「$6\divsymbol3\ (\text{mod}\ 7)$」のようなものを考えていきましょう。

　つまり、私たちのモチベーションは「$3x\equiv6\ (\text{mod}\ 7)$」という方程式を解くところにあります。では、解いてみましょう。全探索すればいいですね。

• $x\equiv 0\ (\text{mod}\ 7)$のとき、$0\equiv6\ (\text{mod}\ 7)$となり不適
• $x\equiv 1\ (\text{mod}\ 7)$のとき、$3\equiv6\ (\text{mod}\ 7)$となり不適
• $x\equiv 2\ (\text{mod}\ 7)$のとき、$6\equiv6\ (\text{mod}\ 7)$となり適する
• $x\equiv 3\ (\text{mod}\ 7)$のとき、$2\equiv6\ (\text{mod}\ 7)$となり不適
• $x\equiv 4\ (\text{mod}\ 7)$のとき、$5\equiv6\ (\text{mod}\ 7)$となり不適
• $x\equiv 5\ (\text{mod}\ 7)$のとき、$1\equiv6\ (\text{mod}\ 7)$となり不適
• $x\equiv 6\ (\text{mod}\ 7)$のとき、$4\equiv6\ (\text{mod}\ 7)$となり不適

よって$\text{mod}\ 7$で$6\divsymbol3$は$2$になる。

　うまくいきましたね。なんだよ、うまくいくじゃないか、とは思わないでください。うまくいかない例を挙げてみましょう。では、「$18\divsymbol6\ (\text{mod}\ 9)$」のようなものを考えてみましょう。

• $x\equiv0\ (\text{mod}\ 9)$のとき、$0\equiv18\ (\text{mod}9)$となり適する
• $x\equiv1\ (\text{mod}\ 9)$のとき、$6\equiv18\ (\text{mod}9)$となり不適
• $x\equiv2\ (\text{mod}\ 9)$のとき、$12\equiv18\ (\text{mod}9)$となり不適
• $x\equiv3\ (\text{mod}\ 9)$のとき、$0\equiv18\ (\text{mod}9)$となり適する
• $x\equiv4\ (\text{mod}\ 9)$のとき、$6\equiv18\ (\text{mod}9)$となり不適
• $x\equiv5\ (\text{mod}\ 9)$のとき、$12\equiv18\ (\text{mod}9)$となり不適
• $x\equiv6\ (\text{mod}\ 9)$のとき、$0\equiv18\ (\text{mod}9)$となり適する
• $x\equiv7\ (\text{mod}\ 9)$のとき、$6\equiv18\ (\text{mod}9)$となり不適
• $x\equiv8\ (\text{mod}\ 9)$のとき、$12\equiv18\ (\text{mod}9)$となり不適

解が一意に定まらなかったため「$18\divsymbol6\ (\text{mod}\ 9)$」は定義されない。

なかには、方程式の解が一つも存在しないものもあったり、上記のように解が複数個存在したりするものがあります。それらは除算の結果(商)を定義できません。では、どのようなときに定義できるでしょうか。...

　それは、「割る数と法が互いに素」であるときです。

この公式(定理)の証明は後回しにして計算練習をします。

　ここで、私たちは一次方程式を解くことができるようになりました。(未知数の係数と法が互いに素であるときのみ解くことができる。)よって、次のような問題を解くことができる。

(解答)
求まるものを$x$と置くと、$x\equiv 1111^{2018}\ (\text{mod}\ 11111)$
両辺を$10^{2018}$倍することで、$10^{2018}x\equiv 11110^{2018}\equiv(-1)^{2018}\equiv1\ (\text{mod}\ 11111)$
ところで、$10^5$を$11111$で割った余りは計算すると$1$になるため$10^5\equiv1\ (\text{mod}\ 11111)$で
$10^{2018}\equiv(10^5)^{403}\cdot10^3\equiv1^{403}\cdot10^3\equiv10^3\ (\text{mod}\ 11111)$
よって元の方程式は$10^3x\equiv10^5\ (\text{mod}\ 11111)$となり、$11111$と$10^3$は互いに素であるため両辺$10^3$で割り、求まるものは$100$である。

(解答)
「いずれも割り切る$2$以上の整数」を$g$とする。このとき、
$$ \begin{eqnarray} \left\{ \begin{array}{l} xy+4\equiv0\ (\text{mod}\ g) \\ yz+5\equiv0\ (\text{mod}\ g) \\ zx+6\equiv0\ (\text{mod}\ g) \\ xyz+7\equiv0\ (\text{mod}\ g) \end{array} \right. \end{eqnarray} $$
つまり、
$$ \begin{eqnarray} \left\{ \begin{array}{l} xy\equiv-4\ (\text{mod}\ g) \\ yz\equiv-5\ (\text{mod}\ g) \\ zx\equiv-6\ (\text{mod}\ g) \\ xyz\equiv-7\ (\text{mod}\ g) \end{array} \right. \end{eqnarray} $$
となる。上の3つの式を辺々掛け合わせることで$(xyz)^2\equiv-120\ (\text{mod}\ g)$を得て、
一番下の式を二乗することで$(xyz)^2\equiv49\ (\text{mod}\ g)$を得る。
つまり$-120\equiv49\ (\text{mod}\ g)$つまり$169\equiv0\ (\text{mod}\ g)$であるから、$g$は$169$の約数であり$2$以上のものである。よって$g$は$13$か$169$。

　(1)$g=13$のとき
$$ \begin{eqnarray} \left\{ \begin{array}{l} xy\equiv-4\ (\text{mod}\ 13) \\ yz\equiv-5\ (\text{mod}\ 13) \\ zx\equiv-6\ (\text{mod}\ 13) \\ xyz\equiv-7\ (\text{mod}\ 13) \end{array} \right. \end{eqnarray} $$
上の式3つをそれぞれ一番下の式に代入することで
$$ \begin{eqnarray} \left\{ \begin{array}{l} -5x\equiv-7\ (\text{mod}\ 13) \\ -6y\equiv-7\ (\text{mod}\ 13) \\ -4z\equiv-7\ (\text{mod}\ 13) \end{array} \right. \end{eqnarray} $$

それぞれ解いて、$x\equiv4,\ y\equiv12,\ z\equiv5\ (\text{mod}\ 13)$を得る。($x$は「右辺に$-13$」、$y$は「右辺に$+13$」、$z$は「右辺に$-13$」するとちょうど割ることができる。)
題意をみたす$(x,\ y,\ z)$の組は、$(4,\ 12,\ 5),\ (17,\ 12,\ 5)$の二つ。
　(2)$g=169$のとき
(1)と同様にして$-6y\equiv-7\ (\text{mod}\ 169)$を得るが、これを解くと$y\equiv142\ (\text{mod}\ 169)$となり、これと$1\leq y\leq17$を同時にみたす整数は存在しないため不適。($y$を解くとき、「右辺に$+169$」するとちょうど割ることができる。)

以上より、求まるものは$(4,\ 12,\ 5),\ (17,\ 12,\ 5)$である。

　一次方程式を解くときは、右辺に法となる数の倍数を足してうまいこと割れるようにすることが必要である。一次方程式なんて自力で無限に作れるのでたくさん計算練習してほしい。
　数学オリンピックの問題のみならず、数学は「言い換えの学問」であるため、状況を合同式に落とし込んで計算してあげるとうまくいく場合がよくある。また、未知数を積極的に文字で置いて条件を調べることは有用なテクニックである。これは化学などにも通じ、とにかく直接答えを求めようとするのではなく文字で置いて方程式で解いたほうが頭の中が整理されてゴールが見えやすくなる。
　すこし脱線するが、頭を使うときは極力頭の中を整理したほうがいい。とくに数学はひらめきが要求される場面が多くあり、脳のリソースを「現状の理解」に多く割いていると閃くことが難しくなる。できるだけは字きれいに平行に書いて、計算用紙でも間違えたところは消しゴムで消し、図もためらわずに描いたほうがよい。頭の中を整理する場所が計算用紙だから、計算用紙は整理しながら使うとより問題が解きやすくなる。天才少女になった気分で計算用紙を使うときれいに使えるためオススメ(筆者は「数学ガール」シリーズのミルカさんを頭の中に降ろしているが、賢い少女ならなんでもいい)。

除算可能であることの証明

　では、先程後回しにした「どうして互いに素のときは除算ができるのか」をきちんと証明する。

「$\text{mod}\ n$で$b\divsymbol a$ができる」ということは「$ax\equiv b\ (\text{mod}\ n)$をみたす$x\ (\text{mod}\ n)$がただ一つ存在する」ことであった。先程行ったように、$x$を全探索する。

$0,\ a,\ 2a,\ 3a,\ \cdots\ (n-2)a,\ (n-1)a$という数の集まりの中に、$n$で割った余りが$b$と等しいものがちょうど1つだけ存在すればいい。ここで、これらの数の中に「$n$で割った余りが等しい2数」があったとする。つまり、「$0\leq i< j\leq n-1$をみたす整数$i,\ j$が存在して$ai\equiv aj\ (\text{mod}\ n)$をみたしている」とする。このとき、$aj-ai=a(j-i)$は$n$の倍数となるが、$a\bot n$であるから$j-i$が$n$の倍数となる。ところが$0\leq i< j\leq n-1$であるから$j-i$は$n$の倍数になり得ない。背理法により$0,\ a,\ 2a,\ 3a,\ \cdots\ (n-2)a,\ (n-1)a$という数の集まりの中に$n$で割った余りが等しい2数は存在しない―つまりこれらはすべて余りが異なることがわかった。

　ここに書いてあるのは$n$個の数であり、$n$で割った余りはどれだけ多くても$n$通りしかありえないため、$0,\ a,\ 2a,\ 3a,\ \cdots\ (n-2)a,\ (n-1)a$の中には$n$で割った余りとしてあり得るもの(つまり0~n-1のn通り)がちょうど1回ずつすべて現れる。よってこの中には$b$と余りが等しいものがただ一つだけ存在する。(証明終わり)

　ちなみに、$a$と$n$が互いに素でないときは、$aj-ai=a(j-i)$が$n$の倍数であるというところで、$j-i$が$\frac{n}{\text{gcd}(a,\ n)}$の倍数となって、いま$\text{gcd}(a,\ n)\geq 2$より$0\leq i< j\leq n-1$を満たしかつ$aj-ai=a(j-i)$が$n$の倍数となる$i,\ j$が存在する。つまり、ある$x$が$ax\equiv b\ (\text{mod}\ n)$の解であったとき、$x+\frac{n}{\text{gcd}(a,\ n)}\cdot k$($k$は任意の整数)も解となる。これは「割り算の答えが一意に定まらない」ことを意味する。たとえば、「$6x\equiv0\ (\text{mod}\ 9)$」の解の一つに$x\equiv 3$があるが、$\frac{n}{\text{gcd}(a,\ n)}=3$の倍数を足し引きしたものも解になるため、$x\equiv0,\ 3,\ 6$のときは方程式をみたすこととなる。なお、$a\bot n$のときも同様の議論ができるが、$x+\frac{n}{\text{gcd}(a,\ n)}\cdot k=x+nk$は$n$で割った余りがすべて$x$であるため割り算の答えは一意に定まっている。
　もちろん、$0,\ a,\ 2a,\ 3a,\ \cdots\ (n-2)a,\ (n-1)a$の中に余りの同じ2数があるなら、その分余りとして出てこない数が存在し、$b$がそれになったときは「割り算の答えが存在しない」ことを意味する。
　つまり、「割り算ができることと$a\bot n$は必要十分条件である」。

　刺さる人には刺さる証明だと思うが、何を話しているのかさっぱりな人にはさっぱり訳のわからない証明だったと思う。これとまったく同じことをする証明がこの記事にもう一回だけ出てくるため、今理解しなくてもそのときにまた理解しようとすればよい。

　計算練習用の記事を作っておいたためぜひやってみてほしい。
この記事です

3. フェルマーの小定理 / ウィルソンの定理

フェルマーの小定理

　いよいよ合同式の中ボス。ここまで読んで疲れた人は、ぜひワクワクしながら読んでほしいため一旦休んでからこの先を読み進めてほしい。それくらいドキドキする定理が、フェルマーの小定理だ。

　もったいぶらないで紹介する。

なお、当たり前だがフェルマーの小定理は次のようにもかけ、もちろんこれらは同値である。

　定理1と定理2が同値であることを証明する。

　(定理1→定理2)
　　(i)$a$が$p$の倍数でないとき　定理1より$a^{p-1}\equiv1\ (\text{mod}\ p)$であり、両辺$a$倍して$a^p\equiv a\ (\text{mod}\ p)$。
　　(ii)$a$が$p$の倍数であるとき　$a^p\equiv a\equiv0\ (\text{mod}\ p)$。
　よって定理2が成立。

　(定理2→定理1)
　定理2より$a^p\equiv a\ (\text{mod}\ p)$であり、$a$が$p$の倍数でないとき$p$は素数だから$a\bot p$であり両辺$p$で割ることで$a^{p-1}\equiv1\ (\text{mod\ p})$つまり定理1を得る。

　では、フェルマーの小定理を証明する前に様々な例を見てみよう。

　フェルマーの小定理の偉いところは、「今までどうにもすることができなかった指数を簡単に計算することができるようになった」ということである。$\text{mod}\ 7$で$18^{20}\equiv4^{20}$とすることはできたが、指数を$20$は簡単にすることができなかったのだ。もちろん、$20\equiv6$だからといって$4^{20}\equiv4^{6}$のように変形するのは誤りである。指数は掛け合わせる「個数」だったから簡単にすることはできなかった。しかし、フェルマーの小定理では指数でさえも簡単にすることができる。$\text{mod}\ 7$であれば指数は$6$で割った余りに、$\text{mod}\ 29$であれば指数は$28$で割った余りに変えることができるのだ。これがとんでもなく革命的なことであるということにぜひ感動してほしい。

　ちなみに、フェルマーの小定理はOMC等競技数学の舞台では呼吸レベルで用いられるため、これを身に付けないと何もできないと思ってほしい。

　以下、証明

証明方法1　THE 整数

　定理1($a\bot p$のとき$a^{p-1}\equiv1\ (\text{mod}\ p)$)を示す。

　「除算可能であることの証明」とほぼ同じことをもう一度する。

　$a\bot p$であるとき、$a,\ 2a,\cdots,\ (p-1)a$は$p$を法としてすべて異なることを示す。ある整数$i,\ j$が, $1\leq i< j\leq(p-1)$をみたし, かつ$ia\equiv ja\ (\text{mod}\ p)$であるとする。このとき$ja-ia=(j-i)a$は$p$の倍数であるが, $a\bot p$より$j-i$が$p$の倍数となる。そのような$i,\ j$は$1\leq i< j\leq(p-1)$を満たさないため矛盾。よって$a,\ 2a,\cdots,\ (p-1)a$は$p$を法としてすべて異なる。

　$p$で割った余りは$1,\ 2,\cdots,\ p-1$の$p-1$通りであるため, 「$a,\ 2a,\cdots,\ (p-1)a$を$p$で割ったときの、すべて異なる$p-1$通りの余り」の中には$1,\ 2,\cdots,\ p-1$がちょうど一回ずつ出てくる。

　つまり、$a\cdot(2a)\cdot(3a)\cdots\lbrace (p-1)a\rbrace$を計算することは実質的には順番を変えて$1\cdot2\cdot3\cdots(p-1)$を計算することとしていることは同じであり。このことから$a\cdot(2a)\cdot(3a)\cdots\lbrace (p-1)a\rbrace\equiv 1\cdot2\cdot3\cdots(p-1)\ (\text{mod}\ p)$である。

　左辺と右辺を$(p-1)!$を用いて表すと、$(p-1)!\cdot a^{p-1}\equiv(p-1)!\ (\text{mod}\ p)$となり、いま、$p$は素数であるから$(p-1)!\bot p$であり、両辺を$(p-1)!$で割ることで目的の式：$a^{p-1}\equiv 1\ (\text{mod}\ p)$を得る。

証明方法2　$a$についての帰納法

　定理2($a^p\equiv a\ (\text{mod}\ p)$)を示す。

(i)$a=1$のとき
　明らかに$1^p\equiv1\ (\text{mod}\ p)$。

(ii)$a=k$で成立すると仮定し、$a=k+1$のとき
　仮定より$k^p\equiv k\ (\text{mod}\ p)$としてよい。
　$(k+1)^p=k^p+ {}_p \mathrm{ C }_1 \cdot k^{p-1}+{}_p \mathrm{C}_2\cdot k^{p-2}+\cdots+1$であるが、二項係数${}_p\mathrm{C}_k\ (1\leq k\leq p-1)$は、分母に$p$を含まず分子には必ず$p$が含まれる数であるため(実際に書き出してみよ)、これらは$p$の倍数である。よって、
　$(k+1)^p$
$=k^p+ {}_p \mathrm{ C }_1 \cdot k^{p-1}+{}_p \mathrm{C}_2\cdot k^{p-2}+\cdots+1$
$\equiv k^p+0\cdot k^{p-1}+0\cdot k^{p-2}+\cdots+1$
$\equiv k^p+1\ (\text{mod\ p})$
ここで仮定より$k^p+1\equiv k+1\ (\text{mod\ p})$であるから$(k+1)^p\equiv k+1\ (\text{mod\ p})$。

　よって、任意の$a$に対して$a^p\equiv a\ (\text{mod}\ p)$が成立する。

では、フェルマーの小定理を用いて次の問題を解いてみよう(自力では不可能)。

(解答)
$p\geq5$を素数とし、$a_{p-2}$が$p$の倍数であることを示す。
$6a_{p-2}=6(2^{p-2}+3^{p-2}+6^{p-2}-1)=3\cdot2^{p-1}+2\cdot3^{p-1}+6^{p-1}-6$
フェルマーの小定理より、
$3\cdot2^{p-1}+2\cdot3^{p-1}+6^{p-1}-6\equiv3+2+1-6\equiv0\ (\text{mod}\ p)$
以上より$6a_{p-2}$は$p$の倍数であるが、$6\bot p$より$a_{p-2}$が$p$の倍数となる。

よって、$5$以上の素因数をもつ正整数は不適。

$a_1$は偶数であるため$2$を素因数に持つ正整数は不適。
$a_2$は$3$の倍数であるため$3$を素因数に持つ正整数も不適。

以上より、もとまる正整数は$1$のみ。

(解答)
$p=3$のとき、$2^{p-3}+3^{p-3}+6^{p-3}=3$これは適する。
$p\geq5$のとき、$p$は整数$k$を用いて$p=6k\pm1$と書ける($6k+0,\ 2,\ 3,\ 4$は素数にならないから$p$を$6$で割った余りは$\pm1$のどちらか)。

$p=6k-1$のとき、$2^{p-3}+3^{p-3}+6^{p-3}=2^{6(k-1)+2}+3^{6(k-1)+2}+6^{6(k-1)+2}$
これを$7$で割った余りはフェルマーの小定理より$4+9+36=49$つまり$0$になる。もちろん$7$にはならないので不適。

$p=6k+1$のとき、$2^{p-3}+3^{p-3}+6^{p-3}=2^{6(k-1)+4}+3^{6(k-1)+4}+6^{6(k-1)+4}$
これを$7$で割った余りはフェルマーの小定理より$16+81+1296=1393$つまり$0$になる。もちろん$7$にはならないので不適。

よって求まるものは$2^0+3^0+6^0=3$のみ。

(もっと実用的な問題を出せなくてすみません)

ウィルソンの定理

逆元

数学には「逆元」という用語があるが、これは「逆数」のことだと思ってもらっていい。たとえば、$\frac{3}{2}$の逆元は$\frac{2}{3}$である。いちおう、定義と性質について軽く触れておく。

定義からすぐに従う性質として下のようなものがある。

(証明)
$a$が$b$の逆元であるとき、$ab=1$。ここで、$b$の逆元は「$b$にそれをかけて$1$にすることのできる数」であるため$a$である。

というわけで、ウィルソンの定理を証明する準備はできた。まずは主張を見てみよう。

では、証明してみよう。

(証明)
$p=2$のときは明らか。以降、$p\geq3$とする。
$\lbrace2,\ 3,\ \cdots,\ p-2\rbrace$の要素数は$p-3$であり、必ず偶数である。また、以下、これらは「ぴったり$\frac{p-3}{2}$個の互いに逆元となるペアに分割できる」ことを示す。

$\text{mod}\ p$において、「自分自身が逆元となるような数」は、$x^2\equiv1\ (\text{mod}\ p)$となる$x$のみであり、整理すると$(x-1)(x+1)\equiv0\ (\text{mod}\ p)$となる。
つまり$(x-1)(x+1)$は$p$の倍数であり、「$p$は素数だから」$x-1$か$x+1$のどちらかが$p$の倍数となる。つまり$x+1\equiv0$または$x-1\equiv0$。
このことから、「自分自身が逆元となるような数」は$1$と$p-1$のみであり、したがって「$\lbrace2,\ 3,\ \cdots,\ p-2\rbrace$の各数には、逆元となる相方がいる。」

つまり、$\lbrace2,\ 3,\ \cdots,\ p-2\rbrace$の要素をすべてかけ合わせると逆元のペアどうしで$1$になってくれてちょうど$1$になる。

だから、$(p-1)!\equiv1\cdot 1\cdot(p-1)\equiv-1\ (\text{mod}\ p)$である。

ウィルソンの定理を知っているだけでこんな問題に対して解法の道筋が見えてくることがある。

(解答)
$n+2$は$3$以上の整数である。
$n+2$が素数であるときに$R=1$であることを示す。ウィルソンの定理の証明を思い出すと、$2\cdot3\cdots n$という積は$1$に等しくなる(互いに逆元となるペアを$\frac{n-1}{2}$個作れるため)。よって$n!$を$n+2$で割った余りは$1\cdot (2\cdot3\cdots n)=1$となる。
$n+2=4$のとき、$R=2$。
$n+2$が$6$以上で、かつ合成数となるときに$R=0$であることを示す。$n+2$が$3$以上の素数$p$の二乗であるとき、$p$と$2p$は$n!$に含まれるため$n+2=p^2$は$n!$の約数。よって$R=0$。もちろん、$n+2$が素数の二乗でないときは$n+2$のてきとーな素因数$q$をもってきて、$q\neq\frac{n+2}{q}$かつ$q,\ \frac{n+2}{q}< n+2$であることから$n!$の中に$q$と$\frac{n+2}{q}$が含まれていて$R=0$である。
以上の議論から、求まるものは、

• $n+2=4$のときの$R=2$
• $n+2$が$3$から$103$のときの$R=1$(これは素数の個数を数えればいい)

を足し合わせたものであり、$27$となる。

あとは、ウィルソンの定理は「平方剰余の相互法則」の話でも出てくるから意外と覚えておいて損はない。

4. 中国剰余定理

主張自体はとても簡単。ただ、定理をちゃんとした形で書くとちょっと分かりにくいから、いくつかの例を通して主張を掴む。

(略解)
不定方程式$3k-2=5l-3$から両辺$7$を引いて$3(k-3)=5(l-2)$。$3\bot5$だから$k-3=5t$とでき、このとき$l-2=3t$。$k$と$l$について解くと$k=5t+3,\ l=3t+2$となり、故に$a_{5t+3}=b_{3t+2}=15t+7$が共通項全体となる。(ただし、$t$は$0$以上。)
$n=t+1$とすると$t=n-1$なので共通項は$15n-8$となり、$n$は$1$以上の整数である。このことから、$c_n=15n-8$を得る。

この問題を言い換えると、「$3$で割って$1$余り, かつ$5$で割って$2$余る数はどのような数か」というものであって、その答えが「$15$で割って$7$余る数」となった。
余りについての複数の条件を、一つの条件式にまとめることができたのだ。

様々な等差数列の共通項の問題を見て、さらに考察を進める。

ということで、主張を述べようと思う。

証明の前にもう少し遊ぶ。遊んでいるうちにアイデアが降ってくるからだ。

一旦、中国剰余定理を認めて、さきほどの数列の問題を解いてみよう。

中国剰余定理より、「$15$で割って$r$余る数」という答えになるはずだから、この$r$を求める。
$5$で割って$2$余る、とは、「$15$で割って$2$or$7$or$12$余る」と言い換えられ、$r$の候補は$2$or$7$or$12$と絞られる。このなかで$3$で割って$1$余るものは$7$であるため、$r=7$となる。

こうやって問題が解ける。もちろん、実際に$15t+7=3(5t+2)+1=5(3t+1)+2$だから、これは確かに「$3$で割って$1$余り, かつ$5$で割って$2$余る数」になっている。

この解き方をそのまま中国剰余定理の証明に応用できないだろうか。１つ目の条件から$r$の候補を絞り、さらにそこから2つ目の条件で$r$を一択に絞るのではないか。では、証明を書いていく。

(証明)
条件式が$2$個のときを示せば、帰納的に一般的な主張も示せる。よって、条件式が$2$個のときを考察する。

とある数$X$が「$p_1$で割って$r_1$余り、$p_2$で割って$r_2$余る」を満たしているとき、$X\pm p_1p_2$も条件をみたす。よって$X$は「$p_1p_2$で割った余りが$R_1$or$R_2$or$\cdots$」という条件で記述できる(少なくとも$p_1p_2$周期で考えることができるから)。そして、なんと考えるべき条件が、「$p_1p_2$で割って$r$余る」という簡単な形で記述できることを、以下で証明する。

$p_1$で割って$r_1$余るから、$p_1p_2$で割った余りとして考えられるものは
「$r_1,\ r_1+p_1,\ r_1+2p_1,\ \cdots\ ,\ r_1+(p_2-1)p_1$」
の$p_2$通りである。ところで、$r_1$を無視した
「$0,\ p_1,\ 2p_1,\ \cdots\ ,\ (p_2-1)p_1$」
という$p_2$個の数は$p_1\bot p_2$より、$p_2$で割った余りがすべて異なる(除算のときや、フェル小のときに証明したやつ。忘れた人はちょっと下の方にもう一度書くからこのまま読み進めて)。

よってもともとの「$r_1,\ r_1+p_1,\ r_1+2p_1,\ \cdots\ ,\ r_1+(p_2-1)p_1$」も、$p_2$で割った余りがすべて異なる(異なるやつに同じのを足したらダイヤルが平行移動してるだけ)。

$p_2$で割った余りは高々$p_2$通りしか考えることができないため、鳩ノ巣原理より、
「$r_1,\ r_1+p_1,\ r_1+2p_1,\ \cdots\ ,\ r_1+(p_2-1)p_1$」
のなかには「$p_2$で割って$r_2$余る」ものがただ一つ存在する。それを$r$とすると、題意は示された。

中国剰余定理について知見を深めていきたい。

まず、最小、という条件を抜きにして、「$97\cdot100\cdot103=999100$を法として$r$余る数」が「$97,\ 100,\ 103$で割った余りがそれぞれ$32,\ 33,\ 34$である」整数だとわかる。ここではその$r$を頑張って求めよう、という話。

機械的に愚直にやればすぐ終わる。
<1. $103$で割って$34$余り、$100$で割って$33$余る数の条件を考える>

$10300$で割って$34+103k$余る数のうち、$100$で割って$33$余るものは、
$34+103k\equiv33\ (\text{mod}\ 100)$
$3k\equiv-1\ (\text{mod}\ 100)$
$3k\equiv99\ (\text{mod}\ 100)$
よって$k=33$としてよく、求まる条件は「$10300$で割って$34+103\cdot33$余る数」である。

<2. $10300$で割って$34+103\cdot33$余り、$97$で割って$32$余る数の条件を考える>

$999100$で割って$(34+103\cdot33)+10300k$余る数のうち、$97$で割って$32$余るものは、
$34+103\cdot33+10300k\equiv32\ (\text{mod}\ 97)$
$6\cdot33+18k\equiv-2\ (\text{mod}\ 97)$
$4+18k\equiv-2\ (\text{mod}\ 97)$
$18k\equiv-6\ (\text{mod}\ 97)$
$3k\equiv-1\ (\text{mod}\ 97)$
$3k\equiv96\ (\text{mod}\ 97)$
$k\equiv32\ (\text{mod}\ 97)$
よって、$k=32$としてよく、「$(34+103\cdot33)+10300\cdot32$」を計算すれば良い。

計算すると$333033$となり、これは答えに一致する。

もっと賢い解き方

求まるものを$X$とする。このとき、
「$X=97l+32$」「$X=100m+33$」「$X=103n+34$」
となり、それぞれ$3$倍して$1$足すと、
「$3X+1=97(3l+1)=100(3m+1)=103(3n+1)$」
となり、$3X+1$は$97$で割れ、$100$で割れ、$103$で割れ、ほかに何かで割れるとしても絶対に$3$で割って$1$余るものらしい。よって$3X+1=999100(3k+1)$。$X=999100k+333033$より、$X=333033$。

20分かけてこれを思いつくより、10分かけて筆算するほうが速いから最初の解き方でいい。この手の問題は検算が楽だから間違っていたらすぐ軌道修正できるし。10分で筆算できなかったらそれは計算力が足りなかったり合同式の割り算に慣れていない証拠だからもっとトレーニングを積んでほしい。

(解答)
いったん$A$を固定すると、$B$は「$9$で割って$A$余り、$11$で割って$-A$余る」とすることができる。中国剰余定理より、どんな$A$を取ってきても「$999,\ 998,\ \cdots\ ,\ 901$」の中に題意を満たす$B$がただ一つ存在し、同様に
「$900,\ 899,\ \cdots\ ,\ 802$」の中にちょうど一つ
「$801,\ 800,\ \cdots\ ,\ 703$」の中にちょうど一つ
...
「$207,\ 206,\ \cdots\ ,\ 109$」の中にちょうど一つ
題意を満たす$B$が存在するため、一つの$A$に対して、「$109$以上$999$以下」の範囲で$B$は$9$個存在する。$A$は$900$通り考えられるため合計で$8100$個の組が見つかる。
$B$が「$100$以上$108$以下」のとき、今度は$B$を固定すると、一つの$B$に対して「$109$以上$999$以下の範囲で」$A$は$9$個存在する。$B$は$9$通り考えられるため合計で$81$個の組が見つかる。
議論すべき残りの組み合わせは「$A$も$B$もどちらも$100$以上$108$以下」のときだが、$9$で割った余りが等しくなるためには$A=B$である必要があり、このとき$A+B=2A$が$11$の倍数になる$A$を探せば良く、そんなものは存在しない。
よって求まるものは$8100+81=8181$個である。

中国剰余定理は「複数の条件→一つの条件」という、条件をまとめる使い方のみならず、「一つの条件→複数の条件」という方向にも使える。

(解答)
$p$は$3$や$5$とは互いに素。フェルマーの小定理より
$p^4\equiv (p^2)^2\equiv 1\ (\text{mod}\ 3)$
$p^4\equiv 1\ (\text{mod}\ 5)$
中国剰余定理より、$3$で割って$1$余り$5$で割って$1$余る数は$15$で割って$1$余る数であるから題意は示された。
(方針として、$15$で割って$1$余る、を素数の条件に言い換えたい。)

もちろん、$18$で割って$13$余る、みたいなものを$2$で割った余りと$9$で割った余りに分解したいなら、$18k+13=9(2k+1)+4$であることから、$13$を$9$で割った余りと$13$を$2$で割った余りを考えてあげればいいことがすぐに分かる。条件をまとめるときより、バラバラに分けるときのほうが簡単にできる。

5. その他の定理

オイラーの定理

フェルマーの小定理を一般化する。$a^{p-1}\equiv1\ (\text{mod}\ p)$だが、指数の$p-1$を、「$1$以上$p$未満の整数で、$p$と互いに素であるものの個数」と見てあげる。

いっぱんに、$\varphi(n)$を、「$1$以上$n$未満の整数で、$n$と互いに素であるものの個数」とすると、以下が成立：

しかも、$\varphi(n)$は「オイラーのトーシェント関数」といい、次のように表される。

便利ですね。でも、正直あまり使わないです。

平方剰余の相互法則　第一(第二)補充法則

正直「これを知らないと解けない問題」になるから出てこない
この記事が長くなりすぎてしまったので興味がある人は この記事 に飛んでください。

さいごに

予選通過レベルだと、「割り算とフェル小ができれば大丈夫」です。
別記事の「 割り算の練習 」は、一周やる価値はあると思います。

ではまた。