taiseinimanの日記

国家公務員総合職合格、名工大院生、INTP

整数の合同の定義とその性質とフェルマーの小定理の拡張

[整数の合同の定義]

a,b,pを正の整数とする。

a-bがpで割り切れる時、

aはpを法としてbに合同であるといい、

a ≡ b (mod p)と表す。※以降は括弧を省略

また、aをpで割ったときの余りをa mod pと表す。

[合同式の性質]

a ≡ b (mod p)と下記の命題は同値（必要十分条件の関係）。

(1): a mod p = b mod p

(2): b ≡ a mod p

(3): a + n ≡ b + n mod p (nは正の整数)

a ≡ b (mod p)が成り立つ時、下記の命題が成立（逆が成り立つとは限らない)。

(1): a^n ≡ b^n mod p (nは正の整数)

(2): an ≡ bn mod p (nは正の整数)

その他の性質

c,dを正の整数とする。

(1): a ≡ b mod p かつ c ≡ d mod pが成り立つ時、ac ≡ bd mod p

(2): a ≡ b mod p かつ b ≡ c mod pが成り立つ時、a ≡ c mod p

$強力な合同式: a^n \equiv (a \bmod{p})^{n \bmod{p-1}} \bmod{p}...(1)$

ここで、a,nは正の整数でpは素数かつaとpは互いに素（aはpの倍数でない)。

また、n mod (p-1) = r、a mod p = Rと置くことにする。

[証明]

nをp-1で割ったときの余りをr,商をqとする。

$a^n = a^{q(p-1)}・a^{n - q(p-1)}と変形でき、$

$フェルマーの小定理より, a^{p-1} \equiv 1 \mod pであるから,$

$(a^{p-1})^q = a^{q(p-1)} \equiv 1^q = 1 \mod p...(2)$

$(2)の両辺にa^{n - q(p-1)}を掛けると、$

$a^n \equiv a^{n - q(p-1)} \mod p$

$n - q(p-1)というのはrであるから、$

$a^n \equiv a^{r} \mod pを得る。....(3)$

さらに、 $aをpで割った時の商をQ,余りをRとすると、$

$a = Qp + Rであるからこれを(3)の右辺に代入して二項定理を用いて展開すると、$

$(Qp+R)^r = (Qp)^r + _r \mathrm{C}_{r-1}(Qp)^{r-1}R + .... + R^r より$

$(Qp+R)^rをpで割った時の余りはR^rをpで割った時の余りに等しいから,$

$a^n \equiv R^{r} \mod p$ ...(1) を得る。]

例題： $3333^{3333}を31で割ったときの余りを求めよ。$

上記の公式より、 $3333^{3333}\equiv (3333 \mod 31)^{3333 \mod 30} = 16^3 = 4096 \mod 31$

であるから、余りは4。

$\displaystyle さらなる一般化：a^k \equiv (a \bmod{n})^{k \bmod{φ(n)}} \bmod{n}$

ここで、aは整数でn,kは正の整数かつnとaは互いに素で、

φ(n)はn以下の自然数のうちnと互いに素な"個数"を与える関数でオイラー関数という。

$命題： \displaystyle r \lt mかつmのs番目(に小さい)の素因数の冪をd_sとするとき、$

$\displaystyle a^n\bmod{m} = r⇔全てのsについてr\bmod{d_s} = a^n\bmod{d_s}$

$\displaystyle (証明)$

$\displaystyle r \lt mとする。$

$\displaystyle a^n \bmod{m} = rと仮定する。...(1)$

$\displaystyle このとき、a^n - rをmは割り切る。$

$\displaystyle 当然、a^n - rをd_sは割り切るので、$

$\displaystyle a^n - r = Q_sd_s とおける。Q_sは商$

$\displaystyle 変形して、a^n = Q_sd_s + r =Q_sd_s + r - (r \bmod{d_s}) + (r \bmod{d_s})$

$\displaystyle であるから、すべてのsについてr = \bmod{d_s} = a^n \bmod{d_s}$

$\displaystyle 逆にr \bmod{d_s} = a^n \bmod{d_s}のとき...(2)$

$\displaystyle (2)より、r = q_sd_s + a^n - cd_s = (q_s - c)d_s + a^nであるから、$

$\displaystyle a^n - r = (c - q_s)d_sと変形でき、$

$\displaystyle a^n - rを全てのsについてd_sは割り切るので、$

$\displaystyle a^n ≡ r \bmod{m}であるから、a^nをmで割ったときの余りはr$

$\displaystyle (応用)$

$\displaystyle 例題：3333^{3333}を30で割ったときの余りを求めよ。$

$\displaystyle 上記を用いて,$

$\displaystyle 全てのsについてr \bmod{d_s} = 3333^{3333} \bmod{d_s}となるrを求める。$

$\displaystyle すなわち、r = 2n + (3333^{3333} \bmod{2}) = 3k +(3333^{3333}\bmod{3}) =$

$\displaystyle 5m + (3333^{3333} \bmod{5})...(1)を満たすrを見つけることである。$

$\displaystyle ※30の素因数分解は2*3*5であるので。$

$\displaystyle フェルマーの小定理の拡張により、3333^{3333} \bmod{(2 or 3 or 5)}は簡単に求められ、$

$\displaystyle それぞれを代入すると、(1) : r = 2n + 1 = 3k = 5m + 3かつr \lt 30$

$\displaystyle 5m+3 = (3,8,13,18,23,28)と3kの共通部分は(3,18)で、$

$\displaystyle 2n+1との共通部分は3であるから、余りは３。$