合同式ごうどうしきcongruenceと余あまりの基本きほん

2.1合同式ごうどうしきcongruence

$m$m を正まさの整数せいすうとする。整数せいすう $a,b$a,b について、

とは、$a-b$a-b が $m$m の倍数ばいすうであること、すなわち

を意味いみする。

これは「$a$a と $b$b を $m$m で割さった余あまりが同おなじである」という意味いみである。たとえば

である。なぜなら $17-2=15$17-2=15 は 5 の倍数ばいすうだからである。

2.2法ほうmodulus

$a\equiv b\text{[PARSE ERROR: Undefined("Command("pmod")")]}m$a\equiv b\pmod m の $m$m を法ほうmodulusという。どの $m$m で余あまりを見みているかによって、同おなじ整数せいすうの見みえ方かたは変かわる。

2.3剰余じょうよremainder

整数せいすう $a$a を正まさの整数せいすう $m$m で割さった余あまりを剰余じょうよremainderという。通常つうじょう、余あまりは

のいずれかに代表だいひょうさせる。

4.1主張しゅちょう

$a\equiv a^{\prime }\text{[PARSE ERROR: Undefined("Command("pmod")")]}m$a\equiv a'\pmod m、$b\equiv b^{\prime }\text{[PARSE ERROR: Undefined("Command("pmod")")]}m$b\equiv b'\pmod m なら、

かつ

である。

4.2証明しょうめい

$a\equiv a^{\prime }\text{[PARSE ERROR: Undefined("Command("pmod")")]}m$a\equiv a'\pmod m より、ある整数せいすう $s$s が存在そんざいして

と書かける。同様どうように、$b\equiv b^{\prime }\text{[PARSE ERROR: Undefined("Command("pmod")")]}m$b\equiv b'\pmod m より、ある整数せいすう $t$t が存在そんざいして

と書かける。

まず和なごについて、

である。したがって $m$m は $(a+b)-(a^{\prime }+b^{\prime })$(a+b)-(a'+b') を割わり切きるので、

である。

次つぎに積つについて、

と変形へんけいする。右辺うへんに上うえの表示ひょうじを代入だいにゅうすると

である。したがって $m$m は $ab-a^{\prime }{b}^{\prime }$ab-a'b' を割わり切きるので、

である。

4.3意味いみ

この命題めいだいにより、整数せいすうを余あまりに置おき換かえてから足たし算ざん・掛かけ算ざんをしても、最後さいごの余あまりは変かわらない。したがって多項式たこうしき型かたの式しきや線型せんけい漸化式ぜんかしきを、余あまりだけで追おうことができる。

5.1主張しゅちょう

$F\left(x\right)$F(x) を整数せいすう係数けいすう多項式たこうしきとする。$a\equiv r\text{[PARSE ERROR: Undefined("Command("pmod")")]}m$a\equiv r\pmod m なら、

である。

5.2証明しょうめい

まず $a\equiv r\text{[PARSE ERROR: Undefined("Command("pmod")")]}m$a\equiv r\pmod m から、すべての自然数しぜんすう $j$j について

を示しめす。$j=0$j=0 では $a^0=r^0=1$a^0=r^0=1 なので成立せいりつする。$j$j で成立せいりつすると仮定かていすると、命題めいだい 1 の乗法じょうほうにより

である。したがって数学的帰納法すうがくてききのうほうにより、すべての $j$j で $a^j\equiv r^j\text{[PARSE ERROR: Undefined("Command("pmod")")]}m$a^j\equiv r^j\pmod m である。

次つぎに、整数せいすう係数けいすう多項式たこうしきを

と書かく。各かく $j$j について $a^j\equiv r^j\text{[PARSE ERROR: Undefined("Command("pmod")")]}m$a^j\equiv r^j\pmod m であり、整数せいすう $c_j$c_j を掛かけても合同性ごうどうせいは保たもたれる。つまり

である。これらを $j=0,\dots ,d$j=0,\ldots,d について足たし合あわせると、命題めいだい 1 の加法かほうにより

である。したがって

が成立せいりつする。