Fussy's Diary

3 月も今日で終わりです。桜は明日あたりが満開になるかな。しかし、雨の予報が。。。

3 月に間に合わせる形で「アルゴリズムのコーナー」を更新しました。過去に公開した「ウェーブレット変換」の内容を見直しています。過去に作ったドキュメントをみると変な箇所や説明不足の部分もいろいろとあったのでかなり手直ししています。メインは多重解像度解析なのに、連続ウェーブレット変換の方が見直しに時間がかかりました。

そして、過去に拾ったまま放置していた問題を気合入れて解きました。ようやく暗算で計算できる方法を思いついたので紹介しておきます。

-----

1) 2011²³ の下 4 桁を求めよ。
2) 2011^23! の下 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 )
mⁿ ≡ rⁿ ( mod k )

が成り立ちます。

1) 二項定理より

2011²³
= ( 2000 + 11 )²³
= 2000²³ + ₂₃C₁・2000²²・11 + ... + ₂₃C₂₂・2000・11²² + 11²³
≡ 23・2000・11²² + 11²³ ( mod 10000 )

となります。なぜなら、任意のゼロでない自然数 N と 1 より大きい自然数 a に対し、2000^a・N ≡ 0 ( mod 10000 ) となるため、そのような項は無視できるからです。

23・2000・11²² + 11²³ = 11²²( 23・2000 + 11 )

より、11²² と 23・2000 + 11 が 10000 を法いくつになるかがわかれば、求めたい数を見つけることができます。もう一度、二項定理を使って

11²²
= ( 10 + 1 )²²
= 10²² + ₂₂C₁・10²¹ + ... + ₂₂C₁₉・10³ + ₂₂C₂₀・10² + ₂₂C₂₁・10 + 1
≡ ₂₂C₃・1000 + ₂₂C₂・100 + ₂₂C₁・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
φ(p^m) = p^m - p^m-1

m, n が互いに素であれば

φ(mn) = φ(m)・φ(n)

以下の説明ではこれらを利用します。

10000 = 2⁴・5⁴ より

φ(10000)
= φ(2⁴・5⁴)
= φ(2⁴)・φ(5⁴)
= ( 2⁴ - 2³ )( 5⁴ - 5³ )
= ( 16 - 8 )( 625 - 125 ) = 8・500 = 4000 = 20・10・5・4

2011 と 10000 は互いに素なので、オイラーの定理から

2011^{20・10・5・2} ≡ 1 ( mod 10000 )

となります。23! は 23 以下の全ての自然数の積なので、この結果から 2011^23! ≡ 1 ( mod 10000 ) となります。

-----

オイラーの定理は、フェルマーの小定理の場合とほぼ同じ方法で証明ができます。

まず、自然数 n と互いに素な自然数を b_j ( j = 1, 2, ... φ(n) ) とします。b_j の全てに、n と互いに素なある自然数 a を掛けた数 ab_j は、a, b_j のどちらも n と互いに素であることから ab_j も n と互いに素であり、ある k ( k = 1, 2, ... φ(n) ) に対して

ab_j ≡ b_k ( mod n )

が成り立ちます。なぜなら、n と互いに素で n 以下の数は φ(n) の b_k の中にしか存在しないからです。二数 b_j と b_k について

ab_j ≡ ab_k ( mod n )

が成り立つと仮定した時、

a( b_j - b_k ) ≡ 0 ( mod n )

より a( b_j - b_k ) は n で割り切れます。しかし、a は n と互いに素なので、b_j - b_k が n で割り切れなければなりません。また、1 ≤ b_j < n より | b_j - b_k | < n なので、条件を満たす数はゼロのみとなります。つまり、a を掛けたときに合同になる数が等しくなる b_j は存在せず重複しないことから

ab_j ≡ b_k ( mod n )

を満たす 1 から φ(n) までの全ての b_k が存在することになります。すなわち

Π_j{1→φ(n)}( ab_j ) ≡ Π_k{1→φ(n)}( b_k ) ( mod n )

であり、左辺は

Π_j{1→φ(n)}( ab_j ) = a^φ(n)Π_j{1→φ(n)}( b_j )

なので、両辺を Π_j{1→φ(n)}( b_j ) で割れば

a^φ(n) ≡ 1 ( mod n )

となります。

-----

最後のところでさりげなく両辺を Π_j{1→φ(n)}( b_j ) で割りましたが、mc ≡ nc ( mod k ) のときに

m ≡ n ( mod k )

は必ずしも成り立つとは限りません。例えば、

30 ≡ 6 ( mod 8 )

は成り立ちますが、両辺を 2 で割った

15 ≡ 3 ( mod 8 )

は成り立ちません。しかし、c が k と互いに素であれば成り立ちます。b_j は全て n と互いに素なので問題はないというわけです。