🔙

合同式について

合同という概念を数学に導入する。

(参考)幾何学の合同よりもこちらの整数の合同のほうが歴史的には古いものである

定義

$n\in N,n\geq 2$に対して整数$a,b$が合同とは下の同値な条件2つのどちらか(すなわち両方)を満たすことである

$\exists k\in Z;a-b=kn \iff \exists p,q,r \in Z ;a=pn+r\land b=qn+r \land r<n$ 日本語で書けば、「a-bがnの倍数、すなわちaをnで割ったあまりとbをnで割ったあまりが等しい」ということである。

性質

重要な性質が成り立つ。(以下、nは2以上の自然数とし、 $$a \equiv b $$はnに対し $$a $$と $$b $$が合同であることを表す。)

$$a,b,c,d\in Z $$で $$a\equiv b\land c\equiv d $$ならば

  • $$a\pm b\equiv c\pm d $$

  • $$ab\equiv cd $$

さらに、 $$a\perp n $$、すなわちaとnが互いに素なとき、

  • $$ab \equiv ac \to b \equiv c $$

が成立する。

最初の2つに関しては証明が非常にやさしいので略。

3つ目の証明を以下に示す
合同の定義より $$ac-ad = a(c-d) $$はnの倍数。
aがnと互いに素であることからc-dがnの倍数。
よって定義より $$c\equiv d $$ 証明終

応用

ここでは、初等整数論における定理であるフェルマーの定理とオイラーの定理の証明を述べる。

フェルマーの小定理

$$a\in Z,p;prime\wedge a\perp p\to a^{p-1} \equiv1,(mod,p) $$
ただし、 $$a \equiv b , (mod,p) $$はpに対してaとbが合同ということを表す。
日本語で主張を書けば「整数aと素数p(ただしa,p互いに素)に対してaのp-1乗はpで割って1余る」ということである。

証明
$$A={1,2,…,p-1} $$と $$B={a,2a,…,(p-1)a} $$を考える。
AとBが集合として合同、すなわちAの元とBの元で合同な組が一つ存在しかぶりが無いような状況を考える。
これにはBにpに対して合同な元の組が無いことを示せば十分であるから、それを背理法で示す。
$$1\leq i,j\leq p-1,i\neq j $$で $$ia\equiv ja $$となる場合を考えよう。 このときaとpは互いに素であるから、先程示した性質から $$i\equiv j $$が直ちに従う。さて $$1\leq i,j\leq p-1 $$の条件下でpで割った余りが等しいことから、明らかに $$i= j $$であるがこれは明らかに矛盾。よってBの中にpに対し合同な元の組は存在しない。
よってAとBには一対一の合同な組が存在するので、集合全体の積は(積が入れ替え可能であることを考えると)明らかに合同である。すなわち
$$(p-1)! \equiv a^{p-1}(p-1)! $$であり、pが素数であるからpと(p-1)!は互いに素なので、性質から
$$a^{p-1} \equiv 1 $$が示された。証明終

オイラーの定理

$$a,n\in N\wedge a\perp n\to a^{\phi(n)} \equiv1,(mod,n) $$ ただしΦ(n)はn以下のnと互いに素な自然数の個数。

証明は先の証明においてAをn以下のnと互いに素な自然数の集合とすればよい。

 

これによって実戦で必要な合同式の道具はすべて揃ったと言っても過言ではない。

例

合同式によって考えやすくなる問題の例をあげる。

$$2^{2021} $$を $$3 $$, $$127 $$で割った余りをそれぞれ答えよ

解答例

  1. 3で割った余り 以下 $$mod,3 $$で考える。
    $$2\equiv -1 $$より、 $$2^{2021}\equiv (-1)^{2021} \equiv 2 $$ よって余り2

  2. 127で割ったあまり
    以下 $$mod,127 $$で考える。
    ① $$127=2^7-1 $$より $$2^7 $$をうまく利用する方法
    $$2^{2021}=2^{7\cdot 288}\cdot 2^5 \equiv 32 $$
    ②フェルマーの小定理より $$2^{126} \equiv 1 $$を利用する方法
    $$2^{2021}=2^{126\cdot 16}\cdot 2^5 \equiv 32 $$

$$p $$が素数のとき $$p^{4}+14 $$が素数ではないことを示せ。(2021 京都大学文系数学)

解答例

まず $$p \neq 3 $$なる場合について考えると、 $$p\equiv \pm 1,(mod,3) $$
故に $$p^4 \equiv 1 $$であるから、 $$p^4 +14 \equiv 0 $$よって $$p^4+14 $$は3の倍数より素数ではない
次に $$p=3 $$のときだが、 $$p^4+14=95 $$より明らかに素数ではない。

故に題意は示された。