2016年03月31日
巨大な数によるべき乗計算
3 月も今日で終わりです。桜は明日あたりが満開になるかな。しかし、雨の予報が。。。
3 月に間に合わせる形で「アルゴリズムのコーナー」を更新しました。過去に公開した「ウェーブレット変換」の内容を見直しています。過去に作ったドキュメントをみると変な箇所や説明不足の部分もいろいろとあったのでかなり手直ししています。メインは多重解像度解析なのに、連続ウェーブレット変換の方が見直しに時間がかかりました。
そして、過去に拾ったまま放置していた問題を気合入れて解きました。ようやく暗算で計算できる方法を思いついたので紹介しておきます。
-----
1) 201123 の下 4 桁を求めよ。
2) 201123! の下 4 桁を求めよ ( cruz__F 様 )
以下、合同式を多用するので、先に定義といくつかの定理だけ示しておきます。
整数 m, k, q, r に対して m = qk + r となるとき、「m は k を法として r と合同である」といい、m ≡ r ( mod k ) と表します。これを「合同式」または「モジュラー演算」といいます。「時計算」と呼ばれることもあります。合同式では、m ≡ r ( mod k ) かつ n ≡ s ( mod k ) であるとき、
m ± n ≡ r ± s ( mod k )
m・n ≡ r・s ( mod k )
mn ≡ rn ( mod k )
が成り立ちます。
1) 二項定理より
201123
= ( 2000 + 11 )23
= 200023 + 23C1・200022・11 + ... + 23C22・2000・1122 + 1123
≡ 23・2000・1122 + 1123 ( mod 10000 )
となります。なぜなら、任意のゼロでない自然数 N と 1 より大きい自然数 a に対し、2000a・N ≡ 0 ( mod 10000 ) となるため、そのような項は無視できるからです。
23・2000・1122 + 1123 = 1122( 23・2000 + 11 )
より、1122 と 23・2000 + 11 が 10000 を法いくつになるかがわかれば、求めたい数を見つけることができます。もう一度、二項定理を使って
1122
= ( 10 + 1 )22
= 1022 + 22C1・1021 + ... + 22C19・103 + 22C20・102 + 22C21・10 + 1
≡ 22C3・1000 + 22C2・100 + 22C1・10 + 1 ( mod 10000 )
= ( 22・21・20 / 3・2 )・1000 + ( 22・21 / 2 )・100 + 220 + 1
= 1540000 + 23100 + 2201 + 1
≡ 3321 ( mod 10000 )
となり、
23・2000 + 11 = 46011 ≡ 6011 ( mod 10000 )
なので、
3321・6011 = 19962531 ≡ 2531 ( mod 10000 )
となって、求める数は 2531 となります。
2) オイラーの定理より、自然数 n と互いに素な数の個数を φ( n ) としたとき、整数 a と n が互いに素であれば、
aφ(n) ≡ 1 ( mod n )
が成り立ちます。n が素数の場合、φ(n) = n - 1 なので、これはフェルマーの小定理の一般化になります。φ(n) には以下の定理が成り立ちます。
素数 p に対し、
φ(p) = p - 1
φ(pm) = pm - pm-1
m, n が互いに素であれば
φ(mn) = φ(m)・φ(n)
以下の説明ではこれらを利用します。
10000 = 24・54 より
φ(10000)
= φ(24・54)
= φ(24)・φ(54)
= ( 24 - 23 )( 54 - 53 )
= ( 16 - 8 )( 625 - 125 ) = 8・500 = 4000 = 20・10・5・4
2011 と 10000 は互いに素なので、オイラーの定理から
201120・10・5・2 ≡ 1 ( mod 10000 )
となります。23! は 23 以下の全ての自然数の積なので、この結果から 201123! ≡ 1 ( mod 10000 ) となります。
-----
オイラーの定理は、フェルマーの小定理の場合とほぼ同じ方法で証明ができます。
まず、自然数 n と互いに素な自然数を bj ( j = 1, 2, ... φ(n) ) とします。bj の全てに、n と互いに素なある自然数 a を掛けた数 abj は、a, bj のどちらも n と互いに素であることから abj も n と互いに素であり、ある k ( k = 1, 2, ... φ(n) ) に対して
abj ≡ bk ( mod n )
が成り立ちます。なぜなら、n と互いに素で n 以下の数は φ(n) の bk の中にしか存在しないからです。二数 bj と bk について
abj ≡ abk ( mod n )
が成り立つと仮定した時、
a( bj - bk ) ≡ 0 ( mod n )
より a( bj - bk ) は n で割り切れます。しかし、a は n と互いに素なので、bj - bk が n で割り切れなければなりません。また、1 ≤ bj < n より | bj - bk | < n なので、条件を満たす数はゼロのみとなります。つまり、a を掛けたときに合同になる数が等しくなる bj は存在せず重複しないことから
abj ≡ bk ( mod n )
を満たす 1 から φ(n) までの全ての bk が存在することになります。すなわち
Πj{1→φ(n)}( abj ) ≡ Πk{1→φ(n)}( bk ) ( mod n )
であり、左辺は
Πj{1→φ(n)}( abj ) = aφ(n)Πj{1→φ(n)}( bj )
なので、両辺を Πj{1→φ(n)}( bj ) で割れば
aφ(n) ≡ 1 ( mod n )
となります。
-----
最後のところでさりげなく両辺を Πj{1→φ(n)}( bj ) で割りましたが、mc ≡ nc ( mod k ) のときに
m ≡ n ( mod k )
は必ずしも成り立つとは限りません。例えば、
30 ≡ 6 ( mod 8 )
は成り立ちますが、両辺を 2 で割った
15 ≡ 3 ( mod 8 )
は成り立ちません。しかし、c が k と互いに素であれば成り立ちます。bj は全て n と互いに素なので問題はないというわけです。
3 月に間に合わせる形で「アルゴリズムのコーナー」を更新しました。過去に公開した「ウェーブレット変換」の内容を見直しています。過去に作ったドキュメントをみると変な箇所や説明不足の部分もいろいろとあったのでかなり手直ししています。メインは多重解像度解析なのに、連続ウェーブレット変換の方が見直しに時間がかかりました。
そして、過去に拾ったまま放置していた問題を気合入れて解きました。ようやく暗算で計算できる方法を思いついたので紹介しておきます。
-----
1) 201123 の下 4 桁を求めよ。
2) 201123! の下 4 桁を求めよ ( cruz__F 様 )
以下、合同式を多用するので、先に定義といくつかの定理だけ示しておきます。
整数 m, k, q, r に対して m = qk + r となるとき、「m は k を法として r と合同である」といい、m ≡ r ( mod k ) と表します。これを「合同式」または「モジュラー演算」といいます。「時計算」と呼ばれることもあります。合同式では、m ≡ r ( mod k ) かつ n ≡ s ( mod k ) であるとき、
m ± n ≡ r ± s ( mod k )
m・n ≡ r・s ( mod k )
mn ≡ rn ( mod k )
が成り立ちます。
1) 二項定理より
201123
= ( 2000 + 11 )23
= 200023 + 23C1・200022・11 + ... + 23C22・2000・1122 + 1123
≡ 23・2000・1122 + 1123 ( mod 10000 )
となります。なぜなら、任意のゼロでない自然数 N と 1 より大きい自然数 a に対し、2000a・N ≡ 0 ( mod 10000 ) となるため、そのような項は無視できるからです。
23・2000・1122 + 1123 = 1122( 23・2000 + 11 )
より、1122 と 23・2000 + 11 が 10000 を法いくつになるかがわかれば、求めたい数を見つけることができます。もう一度、二項定理を使って
1122
= ( 10 + 1 )22
= 1022 + 22C1・1021 + ... + 22C19・103 + 22C20・102 + 22C21・10 + 1
≡ 22C3・1000 + 22C2・100 + 22C1・10 + 1 ( mod 10000 )
= ( 22・21・20 / 3・2 )・1000 + ( 22・21 / 2 )・100 + 220 + 1
= 1540000 + 23100 + 2201 + 1
≡ 3321 ( mod 10000 )
となり、
23・2000 + 11 = 46011 ≡ 6011 ( mod 10000 )
なので、
3321・6011 = 19962531 ≡ 2531 ( mod 10000 )
となって、求める数は 2531 となります。
2) オイラーの定理より、自然数 n と互いに素な数の個数を φ( n ) としたとき、整数 a と n が互いに素であれば、
aφ(n) ≡ 1 ( mod n )
が成り立ちます。n が素数の場合、φ(n) = n - 1 なので、これはフェルマーの小定理の一般化になります。φ(n) には以下の定理が成り立ちます。
素数 p に対し、
φ(p) = p - 1
φ(pm) = pm - pm-1
m, n が互いに素であれば
φ(mn) = φ(m)・φ(n)
以下の説明ではこれらを利用します。
10000 = 24・54 より
φ(10000)
= φ(24・54)
= φ(24)・φ(54)
= ( 24 - 23 )( 54 - 53 )
= ( 16 - 8 )( 625 - 125 ) = 8・500 = 4000 = 20・10・5・4
2011 と 10000 は互いに素なので、オイラーの定理から
201120・10・5・2 ≡ 1 ( mod 10000 )
となります。23! は 23 以下の全ての自然数の積なので、この結果から 201123! ≡ 1 ( mod 10000 ) となります。
-----
オイラーの定理は、フェルマーの小定理の場合とほぼ同じ方法で証明ができます。
まず、自然数 n と互いに素な自然数を bj ( j = 1, 2, ... φ(n) ) とします。bj の全てに、n と互いに素なある自然数 a を掛けた数 abj は、a, bj のどちらも n と互いに素であることから abj も n と互いに素であり、ある k ( k = 1, 2, ... φ(n) ) に対して
abj ≡ bk ( mod n )
が成り立ちます。なぜなら、n と互いに素で n 以下の数は φ(n) の bk の中にしか存在しないからです。二数 bj と bk について
abj ≡ abk ( mod n )
が成り立つと仮定した時、
a( bj - bk ) ≡ 0 ( mod n )
より a( bj - bk ) は n で割り切れます。しかし、a は n と互いに素なので、bj - bk が n で割り切れなければなりません。また、1 ≤ bj < n より | bj - bk | < n なので、条件を満たす数はゼロのみとなります。つまり、a を掛けたときに合同になる数が等しくなる bj は存在せず重複しないことから
abj ≡ bk ( mod n )
を満たす 1 から φ(n) までの全ての bk が存在することになります。すなわち
Πj{1→φ(n)}( abj ) ≡ Πk{1→φ(n)}( bk ) ( mod n )
であり、左辺は
Πj{1→φ(n)}( abj ) = aφ(n)Πj{1→φ(n)}( bj )
なので、両辺を Πj{1→φ(n)}( bj ) で割れば
aφ(n) ≡ 1 ( mod n )
となります。
-----
最後のところでさりげなく両辺を Πj{1→φ(n)}( bj ) で割りましたが、mc ≡ nc ( mod k ) のときに
m ≡ n ( mod k )
は必ずしも成り立つとは限りません。例えば、
30 ≡ 6 ( mod 8 )
は成り立ちますが、両辺を 2 で割った
15 ≡ 3 ( mod 8 )
は成り立ちません。しかし、c が k と互いに素であれば成り立ちます。bj は全て n と互いに素なので問題はないというわけです。
