剰余と合同式

/ tau / コメントする

商と剰余

剰余(余り)について

a \div bの商がq、余りがrのとき、以下のように表される。d:divisor、q:quotient、r:reminderの意味。

(1)   \begin{eqnarray*} &a = dq + r \\ &a \mod d = r \end{eqnarray*}

余りの定義を「割る数未満の自然数あるいは0」とすると、

(2)   \begin{eqnarray*} 8 &=& 3 \times 2 + 2 \\ 7 &=& 3 \times 2 + 1 \\ 6 &=& 3 \times 2 + 0 \\ 5 &=& 2 \times 2 + 2 \\ 4 &=& 2 \times 2 + 1 \\ 3 &=& 2 \times 2 + 0 \end{eqnarray*}

割られる数が負の場合には、

(3)   \begin{eqnarray*} -9 &=& 3 \times (-3) + 0 \\ -8 &=& 3 \times (-3) + 1 \\ -7 &=& 3 \times (-3) + 2 \\ -6 &=& 3 \times (-2) + 0 \\ -5 &=& 3 \times (-2) + 1 \\ -4 &=& 3 \times (-2) + 2 \end{eqnarray*}

割る数が負の場合には、

(4)   \begin{eqnarray*} 9 &=& -3 \times (-3) + 0 \\ 8 &=& -3 \times (-3) + 1 \\ 7 &=& -3 \times (-3) + 2 \\ 6 &=& -3 \times (-2) + 0 \\ 5 &=& -3 \times (-2) + 1 \\ 4 &=& -3 \times (-2) + 2 \\ \end{eqnarray*}

負数の余り

余りとして負の数を認めることもできる。ただしその場合、商と余りの組み合わせが1つとは限らない。

(5)   \begin{eqnarray*} 10 &=& -3 \times (-3) + 1 \\ 10 &=& -3 \times (-4) -2 \end{eqnarray*}

余りの定義(要件)は以下の2通りがあり、いずれを採用するかは任意。

  • 余りを割る数の絶対値より小さい0以上とする(0 \le r < |d|)
  • 余りの絶対値が割る数の絶対値より小さい数とする(0 \le |r| < |d|)

特別な場合の余り

割る数が1あるいは-1のときは、余りは常に0。

(6)   \begin{eqnarray*} a &=& 1 \times a + 0 \\ a &=& -1 \times (-a) + 0 \end{eqnarray*}

割られる数が1のときの余りは1、割られる数が-1なら余りは割る数の絶対値から1を現じた値(余りを正と定義した場合)。

(7)   \begin{eqnarray*} 1 &=& b \times 0 + 1 \\ -1 &=& b \times 1 + b - 1 \quad (b > 0) \\ -1 &=& b \times (-1)1 + (-b - 1) \quad (b < 0) \end{eqnarray*}

合同式

合同式の定義

整数a, bを正の整数dで割った余りが等しいとき、以下のように表記し、「a, bはdを法として合同である」という。

(8)   \begin{eqnarray*} a &\equiv& b \mod{d}\\ a &\equiv& b \pmod d \end{eqnarray*}

これは次のようにも表現できる。

(9)   \begin{equation*} a - pd = b - qd = r \end{equation*}

合同式の例

(10)   \begin{eqnarray*} 7 &\equiv& 4 \bmod 3\\ 6 &\equiv& 4 \bmod 2\\ 6 &\equiv& 0 \bmod 2\\ 5 &\equiv& 1 \bmod 2 \\ 5 &\equiv& (-1) \bmod 3 \end{eqnarray*}

角度の例

以下の例では、330度と−30度が合同となっている。360度回転するたびに元の位置に戻るイメージ。

(11)   \begin{eqnarray*} 1050 &\equiv& 690 \bmod 360 \\ 690 &\equiv& 330 \bmod 360 \\ 330 &\equiv& -30 \bmod 360 \\ -30 &\equiv& -390 \bmod 360 \end{eqnarray*}

合同式の性質

以下、合同式の\mod dを省略する。

合同式の和

(12)   \begin{equation*} a_1 \equiv b_1 , \; a_2\equiv b_2 \; \Rightarrow \; a_1 + a_2 \equiv b_1 + b_2 \end{equation*}

【証明】

\begin{eqnarray} a_1 - p_1 d &=& b_1 - q_1 d \\ a_2 - p_2 d &=& b_2 - q_2 d \\ &\Downarrow& \\ (a_1 + a_2) - (p_1 + p_2)d &=& (b_1 + b_2) - (q_1 + q_2) d

合同式の積

(13)   \begin{equation*} a_1 \equiv b_1 , \; a_2\equiv b_2 \; \Rightarrow \; a_1 a_2 \equiv b_1 b_2 \end{equation*}

【証明】

(14)   \begin{eqnarray*} a_1 - p_1 d &=& b_1 - q_1 d \\ a_2 - p_2 d &=& b_2 - q_2 d \\ &\Downarrow& \\ (a_1 - p_1 d)(a_2 - p_2 d) &=& (b_1 - q_1 d)(b_2 - q_2 d) \\ &\Downarrow& \\ a_1 a_2 - (a_1 p_2 + a_2 p_1 + p_1 p_2 d) d &=& b_1 b_2 - (b_1 q_2 + b_2 q_1 + q_1 q_2 d) d \end{eqnarray*}

合同式の商

a, \; dが互いに素(a \perp d)のとき、以下が成り立つ。

(15)   \begin{equation*} ab \equiv ac \bmod d \; \Rightarrow \; b \equiv c \bmod d \quad ( {\rm where} \; a \perp d ) \end{equation*}

【証明】

(16)   \begin{eqnarray*} ab \equiv ac \bmod d \; &\Rightarrow& \; ab = dp + r , \; ac = dq + r \\ &\Rightarrow& a(b - c) = d(p + q) \\ \end{eqnarray*}

ここでa, \; bは互いに素なので、b-cがdの倍数となる。

(17)   \begin{eqnarray*} b - c = dk &\Rightarrow& \; b = dm + s , \; ac = dn + s \\ &\Rightarrow& b \equiv c \bmod d \\ \end{eqnarray*}

合同式の冪乗

(18)   \begin{equation*} a \equiv b \bmod d \; \Rightarrow \; a^n \equiv b^n \bmod d \end{equation*}

【証明】

(19)   \begin{equation*} a \equiv b \bmod d \quad \Leftrightarrow \quad \left\{ \begin{array}{l} a = pd + r \\ b = qd + r \end{array} \right. \end{equation*}

(20)   \begin{eqnarray*} a^n &=& (pd + r)^n = \sum_{k=0}^n \dbinom{n-k}{k} (pd)^{n-k} r^k \\ &=& pd \sum_{k=0}^{n-1} \dbinom{n-k}{k} (pd)^{n-k-1} r^k + r^n \\ b^n &=& (qd + r)^n = \sum_{k=0}^n \dbinom{n-k}{k} (qd)^{n-k} r^k \\ &=& qd \sum_{k=0}^{n-1} \dbinom{n-k}{k} (qd)^{n-k-1} r^k + r^n \end{array} \end{eqnarray*}

 

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です