合同式

質問

学校で扱わなかったのですが　合同式とは、どんなのもなのか？
基礎をおしえてください。
お願いします。

回答No.1

WiredLogic · ベストアンサー

整数a と b を p で割った時の余りが同じになるとき、
数式では、a ≡ b (mod p) と表し、
日本語では、aとbは、pを法として、合同である、というふうに言います。
特に、0≦b＜p であれば、b は、a を p で割った余りになります。

たとえば、mod 3 であれば、13≡10≡7≡4≡1≡-2≡-5≡-8 のような具合になります。
負の数のときの余りは、-5 ÷ 3 = -2 … 1 のように、余りが負にならないように、
(勿論、割る数以上にならないように)、たてる商を工夫します。

合同式が便利なのは、高校数学で余りで分類して(代表例は奇数・偶数に分ける)、
問題を解くようなときの表現がお手軽にできること(大学入試などでも、上の定義や、
必要なら、性質の証明を簡単に書けば、使っても大丈夫です)と、
等式ほど自由自在ではありませんが、合同式どうしの、足し算・引き算・掛け算・累乗を
やってもかまわないこと(さすがに、割り算は不可です^^)

すべて、mod p とすると、a≡b, c≡d なら、
a±b≡c±d、a×b≡c×d、a^n≡b^n (nは負でない整数) などが、成り立ちます。

とりあえず、足し算が成り立つことを示しておきますから、ほかは自分でやってみてください。
a≡b, c≡d (mod p) であれば、a = p*m + b, c = p*n + d となるような、整数m,nが存在するから、
a+c = (p*m + b) + (p*n + d) = p*(m+n) + (b+d) = p*(整数) + (b+d) ≡ b+d (mod p)
引き算はまったく同じ、掛け算や累乗もちょいと面倒になりますが、同じ要領で示せます。

お礼

予想外に詳しく説明いただき、ありがとうございました！