合同式の種々の公式

\(a\equiv b\pmod p,~c\equiv d\pmod p\)のとき,\[a\pm c \equiv b \pm d\pmod p,~ac \equiv bd\pmod p,~a^n \equiv b^n\pmod p\]が成り立つことは教科書や問題集等でよく証明されているので,ここではあまり紹介されないもののよく使う次の式を証明してみます。前半は片方のみに法の整数倍を加えるという\(=\)の世界では決して許されなかった計算が許されるという性質,後半は逆に\(\equiv\)の世界では禁じ手であった「両辺を割る」という操作ががある仮定のもとに限り許されるという面白い性質です。

\(a \equiv b\pmod p\)のとき,\[a\equiv b+pk \pmod p~(k\in \mathbb{Z})\]

証明

仮定により\(a-b=pk\)であるから
\begin{align*}
a-(b+kp)&=pk+b-(b+kp)\\
&=pk+kp=p(k+1)
\end{align*}よって\[a\equiv b+pk \pmod p~(k\in \mathbb{Z})\]

証明終

\(\gcd(c,p)=1\)(\(c\)と\(p\)が互いに素)のとき,
\[ac \equiv bc \pmod p\Longrightarrow a \equiv b \pmod p\]

証明

仮定により\[ac-bc=pk \Longleftrightarrow (a-b)c=pk\]右辺が\(p\)の倍数であるから左辺も\(p\)の倍数.ここで,\(c\)が\(p\)の倍数(\(c=pk^{\prime}\))であると仮定すると,\(c(=pk^{\prime})\)と\(p\)が互いに素であることに反する(合同式の定義により\(p\)は\(2\)以上のの整数であることに注意).したがって\(a-b\)が\(p\)の倍数,すなわち\[a\equiv b \pmod p\]
証明終

© 2022 佐々木数学塾, All rights reserved.