累乗の割り算の余り - 知識メモ - atwiki（アットウィキ）

$a^n \mod p = (...(((a \mod p)a \mod p)a \mod p) ... )$
である、すなわち
$b_k = a^k \mod p$
に対し
$b_k = b_{k-1} a \mod p$
が成立する。

（証明）
$a^n = p q' + r' \Leftrightarrow r' = a^n - p q'$
なる商 q' , 余り r' が存在する（ 0 ≦ r' ＜ p ）。
これと同様にすれば、右辺の操作は
$a = p q_1 + r_1$
$a r_1 = p q_2 + r_2$
$a r_2 = p q_3 + r_3$
$...$
$a r_{n-1} = p q_n + r_n$
から
$r_1 = a - p q_1$
$r_2 = a r_1 - p q_2 = a (a - p q_1) - p q_2 = a^2 - p(a q_1 + q_2) = a^2 - p A_2$
$r_3 = a r_2 - p q_3 = a (a^2 - p A_2) - p q_3 = a^3 - p(a A_2 + q_3) = a^3 - p A_3$
$...$
$r_n = a r_{n-1} - p q_n = a (a^{n-1} - p A_{n-1}) - p q_n = a^n - p(a A_{n-1} + q_n)$
$= a^n - p A_n$
となる。このとき A_i は全て非負整数である。
よって、右辺の操作で得られる余り r_n は a^n を p で割った余りに等しくなる。

タグ：

代数学初等数学（高校数学）

「累乗の割り算の余り」をウィキ内検索

最終更新：2012年08月30日 17:54

知識メモ累乗の割り算の余り

メニュー

更新履歴

タグ別

知識メモ 累乗の割り算の余り

メニュー

更新履歴

タグ別

知識メモ累乗の割り算の余り