余りの数学について

余りの計算に関する定理などをまとめていきたいと思います。

・逆元

aをbで割った答えをpで割った余りを求めたいとします。
このときb^(-1)=1(mod p)であるようなb^(-1)の値が整数であると便利です。
この値をbの逆元と言います。
逆元がわかると「aにbの逆元を乗じてpで割った余り」を求めることと、
「aをbで割った答えをpで割った余り」と同等にすることが可能です。

逆元はフェルマーの小定理もしくは拡張ユークリッドの互除法で求まります。
pが素数であればフェルマーの小定理で足りますが、
pが素数でない場合拡張ユークリッドの互除法が必要になります。

・フェルマー小定理

pが素数のときx^p=x(mod p)が成り立ちます。

例えば、p=5のとき

1^5=1(mod 5)
2^5=2(mod 5)
3^5=3(mod 5)
4^5=4(mod 5)
5^5=0(mod 5)
6^5=1(mod 5)
7^5=2(mod 5)
8^5=3(mod 5)

以上のようになります。
1,2,3,4,0,1,2,3,...と周期と法則性を持つことがわかります。
詳しい証明は省きますがこの法則をフェルマーの小定理と呼び、
全ての素数pについて成り立ちます。

1^6=1(mod 6)
2^6=4(mod 6)
3^6=3(mod 6)
4^6=4(mod 6)
5^6=1(mod 6)
6^6=0(mod 6)
7^6=1(mod 6)
8^6=4(mod 6)

pが素数でないと周期性はあっても1,2,3,4,...のように増えません。

また、式を変換します。

1^4*1=1(mod 5)
2^4*2=2(mod 5)
3^4*3=3(mod 5)
4^4*4=4(mod 5)
5^4*5=0(mod 5)
6^4*6=1(mod 5)
7^4*7=2(mod 5)
8^4*8=3(mod 5)

以上のことからxがpで割り切れないとき、x^(p-1)=1(mod p)が成り立ちます。
xがpで割り切れるときはもちろんx^(p-1)=0(mod p)です。

また、xがpで割り切れないとき、x*x^(p-2)=1(mod p)とできます。
このとき、x^(p-2)はx^(-1)に置き換えても同等の結果となります。

すなわち、逆元x^(-1)=x^(p-2)(mod p)と言えます。

・拡張ユークリッドの互除法

1次方程式a*x+b*y=c(a,b,cは整数)があるときにx,yの整数解の組みを拡張ユークリッドの互除法で求めることができます。
1次方程式はxy座標上の直線であるから、予想として整数解を持たないかある周期で無数に解を持つかのどちらかであろう。
まず解を持つ条件はcがaとbの最大公約数gcd(a,b)で割り切れることで判定できます。

ここでa*x+b*y=c*gcd(a,b)と置くとこの方程式は必ずx,yの整数解を持つと言えます。
拡張ユークリッドの互除法でa*x+b*y=gcd(a,b)を解くと解はcx,cyとなります。
その他の解はxがbだけ増えればyがaだけ減ることを考えれば無数に求まります。

さて、ここでa*x=1(mod p)となるような逆元xを拡張ユークリッドの互除法で求めてみる。
a*x=1(mod p)はa*x-p*y=1のxを求めるのと同じです。
よってgcd(a,p)=1であれば拡張ユークリッドの互除法で逆元を求めることができます。
つまりpは必ずしも素数である必要はありません。例えば、a=3,p=4のときaの逆元を求めることは可能です。

また、拡張ユークリッドの互除法では次の連立方程式を解くことが可能です。

a=b1(mod m1)
a=b2(mod m2)

これはb1*x+m1=b2*y+m2と置き換えることができ、
b1*x-b2*y=m2-m1とするとこれは拡張ユークリッドの互除法で解ける形になりました。

・オイラーの定理

オイラー関数phi(p)はp以下の整数でpと素であるものの数です。
例えばp=6のとき6以下で6と素になるのは4,5の2つです。よってphi(6)=2となります。

2^1=2(mod 6)
2^2=4(mod 6)
2^3=2(mod 6)
2^4=4(mod 6)
2^5=2(mod 6)

このとき周期が2になるのがわかります。

このときx^(phi(p))=1(mod p)が成り立ちます。
使い方としては
x^a(mod p)を求めたい場合、x^a(mod p)をx^(a%phi(p))*x^(phi(p))(mod p)に変換できます。
x^(phi(p))(mod p)は1(mod p)なのでx^a(mod p)をx^(a%phi(p))*xとして求めることが可能です。
この方法を使うことで例えばa^(100000!)(mod p)なども求めることが可能です。
特にpが素数の場合は、phi(p)=p-1なので簡単です。
x^a(mod p)の周期はp-1です。

・中国剰余定理

m1とm2が互いに素な正の整数であるとき。
x=b1(mod m1)かつx=b2(mod m2)であれば、必ず解xは存在する。
特に、x=b3(mod m1*m2)であるようなxは0以上m1*m2未満に必ずただ1つと言えます。

m1とm2が互いに素でない正の整数であるとき。
x=b1(mod m1)かつx=b2(mod m2)であるとき、解xが存在しないことがある。
解が存在する条件はb1(mod gcd(m1,m2))=b2(mod gcd(m1,m2))のときである。
また、x=b3(mod lcm(m1,m2))であるようなxは0以上lcm(m1,m2)未満に必ずただ1つと言えます。

また、m1とm2が互いに素でない正の整数であるとき、うまく素になるように変換することもできます。
例えば、x=b1(mod 2*2*2*3)とx=b2(mod 2*2*5)があったとき、2*2*2>=2*2であるため2*2を消して考えることができます。
すなわち、x=b1(mod 2*2*2*3)とx=b2(mod 5)と変換することが可能です。

中国余剰定理を使った例題（その１）

x^2=76901607(mod 100761443)のxを求めよ。

この問題は100761443回の試行で解くことができる。
しかし、100761443=10037*10039であるため高速化できる。

x^2=8150(mod 10037)
x^2=2867(mod 10039)

このようにすることでそれぞれ10037回、10039回の試行で足りる。

x=168(mod 10037)
x=2292(mod 10039)
x=7747(mod 10039)

拡張ユークリッドの互除法で解くことができます。

x=12345678(mod 100761443)
x=90102317(mod 100761443)

・その他の役に立ちそうな法則

x^2+1を素因数分解すると2と4*n+1の素数のみで4*n+3の素数はあらわれない。
素数pが2と4*n+1の場合は2つの整数の2乗の和p=x^2+y^2であらわせる。逆にいうと4*n+3はできない。
pを素数とするとき(p-1)!+1はpで割り切れる。
2よりも大きい偶数は2つの素数の和で求められる。(ただし、4*10^18までしか証明されていない。)
5よりも大きい奇数は3つの素数の和で求められる。
素数を小さいものからp(1),p(2),...とすると、n>=4のときp(1)*p(2)*p(3)*..*p(n)>p(n+1)^2と言える。