【余りの世界】合同式の基礎②
この記事は、「合同式基礎」の続きです。①を読んでいない方、合同式が何かわからない方は先に①をご覧ください。
①はこちら↓
①では合同式の定義を説明しました。今回は、合同式同士のたしざん、ひきざん、かけざんについて書いていきます。
それではどうぞ！
合同式の定義ふりかえり
合同の定義をもう一度書いておきます。詳しい説明は省きます。
a, bを整数、nを2以上の自然数とする。
a−bがnの倍数になるとき、
aとbはnを法として合同といい、
a≡b (mod n)
と表す。
また、以下のようにも表現できました。
a, bを整数、nを2以上の自然数とする。
「aをnで割った余り」と「bをnで割った余り」
が等しくなるとき、
aとbはnを法として合同といい、
a≡b (mod n)
と表す。
合わせて覚えておきましょう。
さあ、ここから新しい内容です。
合同式のたしざん・ひきざん
a, b, c, dを整数、nを2以上の自然数とする。
a≡b (mod n), c≡d (mod n)
のとき、以下が成り立つ。
a+c≡b+d (mod n)
a−c≡b−d (mod n)
2つの合同式があったときに、左辺同士、右辺同士足したり引いたりしても合同式が成立するということです。
具体例
たとえば、5を法としたとき
17≡2 (mod 5)と11≡1 (mod 5)が成り立ちますよね。
よって、左辺と右辺同士それぞれたしざんをした、
17+11≡2+1 (mod 5)
すなわち
28≡3 (mod 5)
も成り立ちます。
実際、28−3=25が5の倍数になっているため、確かに成り立っていることが確認できます。
また、左辺と右辺同士をひきざんした、
17−11≡2−1 (mod 5)
すなわち
6≡1 (mod 5)
も成立します。これは6−1=5なので明らかですね。
厳密な証明は記事の最後に書きます。
合同式のかけざん
a, b, c, dを整数、nを2以上の自然数とする。
a≡b (mod n), c≡d (mod n)
のとき、以下が成り立つ。
a×c≡b×d (mod n)
2つの合同式があったときに、左辺同士、右辺同士かけざんしても合同式が成立するということですね。
具体例
たとえば、5を法としたとき
17≡2 (mod 5)と11≡1 (mod 5)が成り立ちますよね。
このとき、左辺と右辺同士をかけざんした、
17×11≡2×1 (mod 5)
すなわち
187≡2 (mod 5)
が成り立ちます。
実際、187−2=185が5の倍数になっているため、確かに成り立っていることが確認できます
応用例
このかけざんですが、辺のどちらかが1や−1だと便利なことがあります。
例えば、
12を何乗しても、11で割った余りは必ず1になります。
これを示す方法として、12のn乗を二項展開するというやり方がありますが、ちょっと面倒。しかし、合同式を使うとシンプルに示せます。
12≡1 (mod 11)
が成り立つので、かけざんした以下の合同式がすべて成り立ちます。
12 × 12 ≡ 1 × 1 (mod 11)
12 × 12 × 12 ≡ 1 × 1 × 1 (mod 11)
12 × 12 × 12 × 12 ≡ 1 × 1 × 1 × 1(mod 11)
︙
12 × 12 × 12 × ... × 12 ≡ 1 × 1 × 1 × ... × 1 (mod 11)
すなわち、
12^2 ≡ 1 (mod 11)
12^3 ≡ 1 (mod 11)
12^4 ≡ 1 (mod 11)
︙
12^n ≡ 1 (mod 11)
が成り立つのです。
(「^n」は「n乗」を表します)
他にも、合同式を使うとシンプルに示せる内容があるので、このnoteでも少しずつ紹介していければ良いなと思っています。
まとめ
いかがでしたか？
今回紹介した合同式の性質をまとめておきます。
a, b, c, dを整数、nを自然数とする。
a≡b (mod n), c≡d (mod n)
のとき、以下が成り立つ。
a+c≡b+d (mod n)
a−c≡b−d (mod n)
a×c≡b×d (mod n)
例題を交えて説明していきましたが、何となくわかっていただけたでしょうか？
尚、合同式のわりざんもあるのですが、ちょっと複雑なので省きました。
これは、最大公約数について紹介した後に記事にしようと思うので、公開されたらぜひご覧ください！
①はこちら↓
素数はいつも、あなたのそばに。
Let's enjoy SOSU !
最後まで読んでいただき、ありがとうございました。
★補足★
合同式のたしざん、ひきざん、かけざんが成り立つことの証明
a, b, c, dを整数、nを自然数とする。
a≡b (mod n), c≡d (mod n)
のとき、以下が成り立つ。
①a+c≡b+d (mod n)
②a−c≡b−d (mod n)
③a×c≡b×d (mod n)
★証明★
a≡b (mod n), c≡d (mod n)より、
ある整数j, kが存在して、以下のように表せます。
a−b=jn
c−d=kn
(念の為言っておきますが、右辺は「×」を省略していますよ！)
これらの式を使って、①②③を証明していきます。
①の証明
a+c≡b+d (mod n)
を示すためには、(a+c)−(b+d)がnの倍数であることを示せば良いです。
a−b=jn, c−d=knを使うと、
(a+c)−(b+d) = (a−b)+(c−d) = jn+kn=(j+k)n
j, kが整数より、j+kも当然整数です。
よって、 (a+c)−(b+d)はnの倍数となるので
a+c≡b+d (mod n)
が成り立ちます。
②の証明
①と大体同じです。
a−c≡b−d (mod n)
を示すためには、(a−c)−(b−d)がnの倍数であることを示せば良いです。
a−b=jn, c−d=knを使うと、
(a−c)−(b−d) = (a−b)−(c−d) = jn−kn=(j−k)n
j, kが整数より、j−kも当然整数です。
よって、 (a−c)−(b−d)はnの倍数となるので
a−c≡b−d (mod n)
が成り立ちます。
③の証明
a×c≡b×d (mod n)
を示すためには、a×c−b×dがnの倍数であることを示せば良いです。ここでは「×」を省略して、ac−bdと表記します。
a−b=jn, c−d=knを使うと、
ac−bd = ac−bc+bc−bd = c(a−b)+b(c−d) = cjn+bkn = (aj+bk)n
a, j, b, kは整数なので、aj+bkも整数です。
よって、ac−bdはnの倍数となるので、
a×c≡b×d (mod n)
が成り立ちます。
以上が証明でした👏
最後まで読んでいただき、ありがとうございました。