離散数学講義ノート（初等整数論）

初等整数論のモチベーション 0の発見 { 1, 2, 3, ... 0, 1, 2, 3, ... 負の数の導入 { 0, ±1, ±2, ±3, ... 加算と乗算ができる. 加算と乗算ができる. 減算もできる. } 整数の和・差・積も整数である. 有理数に拡張 x ÷ y = x/y 有理数 整数 整数 そして実数 複素数 四元数 ... 除算は? (商は?) 商と余りを求める x ÷ y = q あまり r 整数 整数 整数 整数 あえて整数に限定してみよう! (ゲームの縛りプレイのようなもの) ・アイテム禁止 ・レベル上げ禁止など

初等整数論のモチベーション 例 x² + y² = z² をみたす正整数 x, y, z を求めよ. x, y, z が実数の範囲なら, 半径 z の円周上の点だが 整数に限定すると, 円周上のどんな点なのか? 例 フェルマーの最終定理 (ワイルズ, ほか証明に貢献した歴代の数学者たち) xⁿ + yⁿ = zⁿ (n≧3) は正整数解を持たない. 例 7145592^865542103 が3の倍数かどうかをどうやって判定するか? ◎ 整数に限定すると意外で面白くて難しい問題が生まれる. ◎ 整数のいろいろな性質に着目したり, 他の様々な数学の分野と結び付けたりして発展する. (偶奇性, 互いに素など) ◎ 巨大な整数の扱い方が暗号通信に有用であることが最近になって見出された. (1970年代~)

整数の整除

除法の定理 division theorem principle 定理(除法の定理または原理) 整数 a, b (b≠0) について, 整数 q, r が唯一一組存在して, a = bq + r, 0≦r < |b|. quotient remainder このとき, 「aをbで割った商はq, 余り(剰余)はrである」などと言う. 例 8 = 3×2 + 2. 3×2 +2 0 8 8を3で割った商 2 余り 2 11 = -4×(-2) + 3. -4×(-2) +3 0 11 11を-4で割った商 -2 余り 3 -15 = 4×(-4) + 1. +1 4×(-4) -15 0 -15を4で割った商 -4 余り 1

整数の整除 b≠0とする流儀もある. その場合は0の倍数は 定義されない. 整数の整除 整数 a, b について, 整数 q が存在して, a = bq のとき, multiple divisor ・a は b の倍数, b は a の約数という. a is divisible by b ・a は b で割り切れるとか整除されるという. b divides a ・b は a を割り切るといい, b|a で表す. 「bはaを割り切る」 から「a/bは整数」 を連想してしまい, b|aと紛らわしい... b divides a 例 18 = 6×3 より, 6|18, 18は6の倍数, 6は18の約数. -18 = 2×(-9) より, 2|-18, -18は2の倍数, 2は-18の約数. 18 = 18×1 より, 18|18, 18は18の倍数, 18は18の約数. 18 = 1×18 より, 1|18, 18は1の倍数, 1は18の約数. 0 = 18×0 より, 18|0, 0は18の倍数, 18は0の約数. 0 = 0×18 より, 0|0, 0は0の倍数, 0は0の約数. 0で割ってはダメでは? → 0=0xの解を定めているわけではないのでセーフ.(商は未定義)

最大公約数 common divisor 2つ以上の整数 a1, a2, ..., an のすべてを割り切る整数を公約数と呼ぶ. 例 12 と 18 の公約数は, ±1, ±2, ±3, ±6 の8個. 12, 15, -18 の公約数は, ±1, ±3 の4個. 0, 4, 6 の公約数は, ±1, ±2 の4個. 0, 0, 0 の公約数は, すべての整数. 2つ以上の整数 a1, a2, ..., an のうち少なくとも1つは0でないとき, greatest common divisor a1, a2, ..., an の公約数のうち最大のものを最大公約数と呼び, gcd(a1, a2, ..., an) で表す. relatively prime gcd(a1, a2) = 1 のとき, a1 と a2 は互いに素であるという. 例 gcd(12, 15, -18) = 3. gcd(4, 7) = 1 より, 4と7は互いに素である. このような定義をするときは, "最大のもの"が存在するか要チェック

最小公倍数 common multiple 2つ以上の整数 a1, a2, ..., an のいずれの倍数でもある整数を公倍数と呼ぶ. 例 2 と 3 の公倍数は, 0, ±6, ±12, ±18, ... 2, 3, 5 の公倍数は, 0, ±30, ±60, ±90, ... -6, 9, 15 の公倍数は, 0, ±90, ±180, ±270, ... 0, 4, 8 の公倍数は, 0 のみ. 2つ以上の整数 a1, a2, ..., an のいずれも0でないとき, least common multiple a1, a2, ..., an の正の公倍数のうち最小のものを最小公倍数と呼び, lcm(a1, a2, ..., an) で表す. 例 lcm(12, 18) = lcm(2×6, 3×6) = 36. 12だけの約数 18だけの約数 2×3×6 最大公約数は重複してるから1回だけ掛ける. 0を許すとつまらない. 正に限ると"最小のもの" が存在しないかも...? ということを気にしながら 定義する 定理. 2つの正整数 a, b について, ab = gcd(a, b) × lcm(a, b). 例 12×18 = (2×6) × (3×6) = 6 × (2×3×6) = gcd(12, 18) × lcm(12, 18).

素数

0と1と素数と合成数 非負整数 { 0 1 ※ 1は素数でも合成数でもない. prime number 素数 2以上の整数で, 1とその数自身の他に 正の約数を持たない数. composite number 合成数 2以上の整数で, 1とその数自身の他にも 正の約数を持つ数. 例 2 1, 2 素数 3 1, 3 素数 4 1, 2, 4 合成数 5 1, 5 素数 6 1, 2, 3, 6 合成数 7 1, 7 素数 8 1, 2, 4, 8 合成数 正の約数の個数 0 無限 1 1個 素数 2個 合成数 3個以上

素因数分解 2200 = 2³ × 5² × 11 のように, 整数を素数の積 p1・p2・...・pk (k≧1) prime factorization で表すことを素因数分解と呼ぶ. 「3」は整数3を1つの素数の積で 表した素因数分解とみなす. 定理 2以上の整数 n は素因数分解できる. 証明) n に関する数学的帰納法で示す. n = 2 のとき, n は「2」と素因数分解できる. k を2以上の整数とする. 2以上 k 以下の整数は素因数分解できると仮定する. (累積帰納法) k + 1 が素数のとき, k + 1 は「k + 1」と素因数分解できる. k + 1 が合成数のとき, k + 1 は 2以上 k 以下の約数 a を持つ. 仮定より, a と (k+1)/a はそれぞれ素因数分解できるから, k + 1 もできる. 以上より定理は成り立つ. 定理 2以上の整数 n の素因数分解は1通りしかない. 12 = 2² × 3 12 = 2 × 6 = 3 × 4 = 1 × 12 = 1 × 1 × 12 素数でなくて良ければ 複数の分解がありうる.

素数の個数 定理. 素数は無限に存在する. 証明) すべての素数について, それよりも大きな素数の存在を示せばよい. p を素数とする. p 以下のすべての素数の積に1を加えた数 n = 2 × 3 × 5 × ... × p + 1 は p 以下の素数では割り切れない. 一方, n は2以上の整数だから素因数分解できる. よって n は p よりも大きい何らかの素数で割り切れる. したがって, p よりも大きい素数が存在する. ※ 2 + 1 = 3 2 × 3 + 1 = 7 2 × 3 × 5 + 1 = 31 2 × 3 × 5 × 7 + 1 = 211 2 × 3 × 5 × 7 × 11 + 1 = 2311 2 × 3 × 5 × 7 × 11 × 13 + 1 = 30031 = 59 × 509

約数の個数 6 = 2 × 3 の正の約数は 1, 2, 3, 6 (1 + 2)(1 + 3) = 1 + 2 + 3 + 6 30 = 2 × 3 × 5 の正の約数は 1, 2, 3, 5, 6, 10, 15, 30 (1 + 2)(1 + 3)(1 + 5) = 1 + 2 + 3 + 6 + 5 + 10 + 15 + 30 12 = 2² × 3 の正の約数は 1, 2, 3, 4, 6, 12 (1 + 2 + 2²)(1 + 3) = 1 + 2 + 4 + 3 + 6 + 12 3項 2項 6項 定理 2以上の整数 n の素因数分解が p1^α1・p2^α2・p3^α3・...・pm^αm と書けるとき, n の正の約数の個数は (1 + α1)(1 + α2)...(1 + αm) 例 180 = 2² × 3² × 5 の正の約数の個数は (1 + 2)(1 + 2)(1 + 1) = 18個. (1 + 2 + 2²)(1 + 3 + 3²)(1 + 5) = (1 + 2 + 4 + 3 + 6 + 12 + 9 + 18 + 36)(1 + 5) = 1 + 2 + 4 + 3 + 6 + 12 + 9 + 18 + 36 + 5 + 10 + 20 + 15 + 30 + 60 + 45 + 90 + 180.

ユークリッドの互除法

最大公約数を求めたい gcd(19654635, 777546) = ? 素因数分解してみる. 19654635 = 3 × 5 × 7 × 11 × 11 × 13 × 17. 777546 = 2 × 3 × 3 × 3 × 7 × 11 × 11 × 17. よって, gcd(19654635, 777546) = 3 × 7 × 11 × 11 × 17 = 43197. 巨大な数の素因数分解を効率良く求める方法は発見されていない. 現時点で最速の方法でもコンピュータで数百億年以上かかることがあるかも... 2020年の記録では250桁の合成数を数台のコンピュータで 数ヶ月かけて2つの素数の積に分解したらしい...

余りに着目してみる d := gcd(19654635, 777546) とおく. 19654635 = 777546 × 25 + 215985 dで割り切れる dで割り切れる よって, 余りもdで割り切れる d は 777546 と 215985 の公約数でもある. よって, d' := gcd(777546, 215985) とおくと d ≦ d'. 19654635 = 777546 × 25 + 215985 よって, d'で割り切れる d'で割り切れる d'で割り切れる d' は 19654635 と 777546 の公約数でもある. よって, d' ≦ d. したがって, d = d'.

余りに着目してみる 19654635 = 777546 × 25 + 215985 だから gcd(19654635, 777546) = gcd(777546, 215985) 777546 = 215985 × 3 + 129591 だから gcd(777546, 215985) = gcd(215985, 129591) 215985 = 129591 × 1 + 86394 だから gcd(215985, 129591) = gcd(129591, 86394) 129591 = 86394 × 1 + 43197 だから gcd(129591, 86394) = gcd(86394, 43197) 86394 = 43197 × 2 + 0 だから gcd(86394, 43197) = gcd(43197, 0) = 43197.

最大公約数と余りの関係性 定理. 整数 a, b について, 整数 q, r が存在して, a = bq + r ← rに何も制限がなくてもOK であるとき, d が a と b の公約数ならば d は b と r の公約数でもあるし, 逆も成り立つ. a b r 44=16×1+28 0=0×q+0 などでも 定理は成り立つ. 証明). d|a かつ d|b ならば, 整数 s, t が存在して a=ds, b=dt. 仮定より ds = dtq + r ∴ r = d(s-tq) ∴ d|r. よって d は b と r の公約数である. d|b かつ d|r ならば, 整数 s, t が存在して b=ds, r=dt. 仮定より a = dsq + dt = d(sq+t) ∴ d|a. よって d は a と b の公約数である. 系. a, b が共に0でなければ gcd(a, b) = gcd(b, r). 便宜的に gcd(0,0)=0 と定めてしまえば a=b=0でも成り立つ

ユークリッドの互除法 除法の定理より, 整数 a, b (b≠0) について, 整数 q, r が唯一一組存在して, a = bq + r, (0≦r < |b|) であることを, くり返し利用して, gcd(a, b) (b≠0) を求めたい. r1 : aをbで割った余り. r2 : bをr1で割った余り. r3 : r1をr2で割った余り. : rk : rk-2をrk-1で割った余り. (r-1:=a, r0:=bとしておく) : (k≧1のとき) とすると, 0≦rk < |rk-1| だから数列|b|, r1, r2, ... は単調減少する. 一方, 0≦rk だから, どこかで0になる. rm+1 = 0 とすれば, gcd(a, b) = gcd(b, r1) = gcd(r1, r2) = ... = gcd(rm, rm+1) = rm. 0 Euclidean algorithm この方法をユークリッドの互除法と呼ぶ. (b=0のときは簡単で, gcd(a,0)=a.)

ユークリッドの互除法 例 gcd(44, 16) = gcd(16, 12) = gcd(12, 4) = gcd(4, 0) = 4. 44 16 16 12 12 4 4 4 4 4

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

砂時計パズル 3分 5分 1分を測ろう ①スタート ②3分経過 ひっくり返す ③5分経過 ④6分経過 1分 3x + 5y = 1 の整数解を求める問題と等価.

バケツパズル 8l 11l 1lを汲もう 1 4 7 0 11 3 11 6 11 2 5 8 -8 -8 -8 8 3 8 6 8 9 3 6 9 3 0 6 0 8 1l 8x + 11y = 1 の整数解を求める問題と等価.

一次不定方程式 整数係数の方程式の整数解を求める問題を考えるとき, Diophantine equation その方程式はディオファントスの方程式と呼ばれる. Diophantus 定理. 整数 a, b について, ax+by = gcd(a, b) は整数解を持つ. (ただし, 便宜上 gcd(0,0)=0 と定めておく.) 証明) a=0 または b=0 のとき, (x,y)=(1,1), (1,-1), (-1,1)のいずれかが解である. a≠0, b≠0 のとき, ユークリッドの互除法で gcd(a, b) を求める. a = bq1 + r1 ∴ a + (-q1)b = r1. x1=1, y1=-q1とおく. b = r1q2 + r2 ∴ b = (a-q1b)q2 + r2. ∴ -q2a + (1+q1q2)b = r2. x2=-q2, y2=1+q1q2とおく. 以下同様に a と b の係数を xi, yi とおきながら計算を続けると, いずれ rm-2 = rm-1 qm + rm = rm-1 qm + gcd(a, b) となる. これを xma + ymb = gcd(a, b) と変形すれば xm, ym が所望の解である.

拡張ユークリッドの互除法 例 8x + 11y = 1 の解を1組求めよ. 8 = 11×0 + 8. ∴ 8 + 0×11 = 8. x1=1, y1=0. ↓代入 11 = 8×1 + 3. ∴ 11 + (-1)×8 = 3. ∴ -8 + 11 = 3. x2=-1, y2=1. ↓代入 8 = 3×2 + 2. ∴ 8 + (-2)×3 = 2. ∴ 8 - 2(-8 + 11) = 2. ∴ 3×8 + (-2)×11 = 2. x3=3, y3=-2. ↓代入 ↓代入 3 = 2×1 + 1. ∴ 3 + (-1)×2 = 1. ∴ -8 + 11 - (3×8 - 2×11) = 1. ∴ (-4)×8 + 3×11 = 1. x4=-4, y4=3. よって, x=-4, y=3 はこの方程式の解のうちの1つである.

一次不定方程式のすべての解 8x + 11y = 1 の整数解の1つは x=-4, y=3 である. このとき, {x = -4 + 11 = 7, y = 3 - 8 = -5} や {x = -4 - 33 = -37, y = 3 + 24 = 27} も解である. (8×7 + 11×(-5) = 56 - 55 = 1. 8×(-37) + 11×27 = -296 + 297 = 1.) 定理. 整数 a, b について, gcd(a, b) = 1 のとき, ax + by = 1 の整数解の1組を x=x0, y=y0 とする. このとき, この方程式の整数解は. {x = x0 + bk, y = y0 - ak} (k∈Z). ax0 → a(x0+bk)に増えたら, 左辺はabk増えてしまうから by0 → by0-abkに減らすと キャンセルできる. 例 8x + 11y = 1 の整数解は {x = -4 + 11k, y = 3 - 8k} (k∈Z).

合同式

曜日と余り(剰余) 8/3が木曜日のとき, 8/21は何曜日? 曜日は, 7日毎に一周する. 8/3 → 8/10 → 8/17 → 8/21 +7 +7 +4 「8/17の4日後」ではなく 「木曜日の4日後」 であることが本質的 木曜日の4日後は月曜日 // 剰余を使って言い換えると... 8/21は8/3の18日後である. 日付と日数の話 18と7について, 18 = 7×2 + 4 (すべての整数) が成り立ち, 0≦4<7であるから 18を7で割った余り(剰余)は4. よって, 8/21は木曜日の4日後である. 曜日と日数の話 即ち, 月曜日 // (0~6) 8月 日 月 火 水 木 金 土 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 ぐるぐる周る話は 余り(剰余)に着目すると 話を簡単にできる.

曜日と余り(剰余) 曜日が知りたいだけなら, 曜日が同じ日を"同じ"日だと思ってOK! 8/3も8/17も 8/21の曜日を知る上では 本質的な違いは無かった. 観察 8/3と8/17は"同じ"日. 8/6と8/20は"同じ"日. 8/a と 8/b の曜日が同じであるとは, a-bが7の倍数であることである. このとき, 8/aと8/bは"同じ"日であると 言ってしまうことにしよう. ← いちいち"曜日が同じ" と言うのはめんどいから. 例 8/6と8/20は 6-20が7の倍数だから"同じ"日. 例 8/25は何曜日? → 25 = 7×3 + 4より, 25-4 = 7×3. ゆえに25-4は7の倍数. よって, 8/25は8/4と"同じ"日だから金曜日 8月 日 月 火 水 木 金 土 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 曜日で同一視 日 月 火 水 木 金 土 27 28 29 30 31 25 26

合同式 「異なる」がないので a=bでもOK 2つの整数 aとbについて, a-bが整数mの倍数であることを, congruent modulo m aとbはmを法として合同である modulus congruence と言い. a ≡ b (mod m) と書き表す. この式を合同式と呼ぶ. congruence expression 例 6 ≡ 8 (mod 2) 3 ≡ 9 (mod 3) 13 ≡ 5 (mod 2) 8 ≡ 8 (mod 3) -1 ≡ 1 (mod 2) -1 ≡ 2 (mod 3) 0 ≡ 2 (mod 2) 0 ≡ 3 (mod 3) m≠0なら, mで割った余り(剰余) が等しいとき a ≡ b (mod m)

「≡」は同値関係 2つの整数の間の(mを法とする)合同関係は同値関係である. 即ち, 以下が成り立つ. ① [反射律] すべての x∈Z について, x ≡ x (mod m). ② [対称律] すべての x, y∈Z について, x ≡ y (mod m) ならば y ≡ x (mod m). ③ [推移律] すべての x, y, z∈Z について, 「x ≡ y (mod m) かつ y ≡ z (mod m)」ならば x ≡ z (mod m). 例 7 ≡ 4 (mod 3), 4 ≡ 1 (mod 3), ゆえに 7 ≡ 1 (mod 3). → これを単純に 7 ≡ 4 ≡ 1 (mod 3) ゆえに 7 ≡ 1 (mod 3) と書いてもよい.

合同式と加法・減法 a ≡ b (mod m), k ≡ l (mod m) (a,b,k,l,mは整数) のとき, a + k ≡ b + l (mod m) a - k ≡ b - l (mod m) 証明 仮定より a-b, k-l はmの倍数. よって (a+k)-(b+l) = (a-b) + (k-l), (a-k)-(b-l) = (a-b) - (k-l) はmの倍数. 例 8 ≡ 2 (mod 3), 13 ≡ -5 (mod 3) のとき, 21 ≡ -3 (mod 3). 辺々を足せる 例 x ≡ y (mod 3) のとき, 両辺からyを引くと, x-y ≡ 0 (mod 3) 移項できる 例 3x ≡ 0 (mod 3) だから, 3x+y ≡ 2 (mod 3) のとき 左辺から3x, 右辺から0を引くと y ≡ 2 (mod 3) 法mの倍数の項を消せる!!

合同式と乗法 a ≡ b (mod m), k ≡ l (mod m) (a,b,k,l,mは整数) のとき, ka ≡ lb (mod m) 証明 仮定より a-b, k-l はmの倍数. よって, ka-lb = k(a-b) + (k-l)b はmの倍数. 例 8 ≡ 2 (mod 3), 13 ≡ -5 (mod 3) のとき, 104 ≡ -10 (mod 3). 辺々を掛けれる 例 11 ≡ 19 (mod 8) のとき, 両辺を2倍すると 22 ≡ 38 (mod 8). 両辺を等倍できる 例 7 ≡ 1 (mod 3) より, 7と1を辺々に掛けると 7² ≡ 1² (mod 3). さらに掛けると 7³ ≡ 1³ (mod 3). さらに掛け続けると 7ⁿ ≡ 1ⁿ (mod 3). 累乗の底を小さくできる!! 一般に, a ≡ b (mod m) のとき aⁿ ≡ bⁿ (mod m) (nは非負整数).

除法は? ka = kb (k≠0) のとき a = b だけど, ka ≡ kb (mod m) (k≠0) のとき a ≡ b ？？？ 例 6 ≡ 9 (mod 3) 2 ≢ 3 (mod 3). 10 ≡ 16 (mod 3) 5 ≢ 8 (mod 3). 18 ≡ 22 (mod 4) 9 ≢ 11 (mod 4). 56 ≡ 32 (mod 6) 7 ≢ 4 (mod 6). 定理. ka ≡ kb (mod m) (a,b,m,kは整数, k≠0) のとき, gcd(k, m) = 1 ならば a ≡ b (mod m). kとmが互いに素 例 28 ≡ 84 (mod 8), gcd(7,8)=1 より 4 ≡ 12 (mod 8). 1, 2, 4, 7, 14, 28で割り切れるけど... 7で割ると安全.

合同式で余りを求める 例 26^100 を3で割った余りを求めよ. 26 ≡ 2 (mod 3) より, 26^100 ≡ 2^100 ≡ 4^50 (mod 3). 4 ≡ 1 (mod 3) より, 4^50 ≡ 1^50 ≡ 1 (mod 3). よって, 26^100 ≡ 1 (mod 3). したがって, 26^100を3で割った余りは 1. 例 2050^89 を11で割った余りを求めよ. 2050^89 ≡ 4^89 ≡ 4^64 × 4^16 × 4^8 × 4^1 (mod 11). 4^8 = 16^4 ≡ 5^4 ≡ 25^2 ≡ 3^2 ≡ 9 (mod 11), 4^16 ≡ (4^8)² ≡ 9^2 ≡ 81 ≡ 4 (mod 11), 4^64 ≡ (4^16)^4 ≡ 4^4 ≡ 16^2 ≡ 5^2 ≡ 25 ≡ 3 (mod 11). よって, 2050^89 ≡ 3 × 4 × 9 × 4 ≡ 12 × 36 ≡ 1 × 3 ≡ 3 (mod 11). したがって, 2050^89を11で割った余りは 3. 89 = 64 + 16 + 8 + 1 = 2^6 + 2^4 + 2^3 + 2^0 2の累乗の和に 分けておく

3と11の倍数判定 正整数nが10進法で "an an-1 ... a2 a1 a0" と表されるとき, (1) n ≡ an + an-1 + ... + a0 (mod 3). (2) n ≡ (-1)^N an + (-1)^(N-1) an-1 + ... + a2 - a1 + a0 (mod 11). 例 6432は, 6+4+3+2 ≡ 0 (mod 3) より, 3の倍数である. 6432は, -6+4-3+2 ≡ -3 ≡ 8 (mod 11) より, 11の倍数ではない.(11で割った余りは8). 証明. (1) a × 10^k ≡ a × 1^k ≡ a (mod 3) より, n = an・10^N + an-1・10^(N-1) + ... + a1・10 + a0 ≡ an + an-1 + ... + a1 + a0 (mod 3). (2) a × 10^k ≡ a × (-1)^k (mod 11) より, (10≡-1 (mod 11).) n = an・10^N + an-1・10^(N-1) + ... + a1・10 + a0 ≡ (-1)^N an + (-1)^(N-1) an-1 + ... + a2 - a1 + a0 (mod 11).

剰余類 2つの整数の間のmを法とする合同関係は同値関係である. residue class a∈Zの同値類を(法mに関するaの)剰余類と呼ぶ. 例 m=2のとき, 剰余類は [0] = {x|xは偶数}, [1] = {x|xは奇数} の2つ. 整数全体の集合は[0]と[1]に分割できる. 例 m=7のとき, 剰余類は[0], [1], ..., [6] の7つ. ([k] = {x|x≡k (mod 7)}) 日, 月, 火, 水, 木, 金, 土 を [0], [1], [2], [3], [4], [5], [6] に対応させる. [x] + [y] := [z] (z≡x+y (mod 7), 0≦z<7) とすると, 8/3(木)の18日後の8/21は, [4] 18∈[4] [4] + [4] = [1] より 月曜日. 偶奇性だけを考えたいときは 0, ±2, ±4...を同一視した[0] ±1, ±3, ±5...を同一視した[1] の2つの剰余類を数のように扱う. 「奇数+奇数=偶数」とは [1]+[1]=[0]のこと. 8月 日 月 火 水 木 金 土 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

一次 合同方程式

一次合同方程式 5x ≡ 1 (mod 6) を解け. 意味: 5倍しても6で割ると余りが1になる整数を求めよ. 5 × 0 ≡ 0 (mod 6). 5 × 1 ≡ 5 (mod 6). 5 × 2 ≡ 10 ≡ 4 (mod 6). 5 × 3 ≡ 15 ≡ 3 (mod 6). 5 × 4 ≡ 20 ≡ 2 (mod 6). 5 × 5 ≡ 25 ≡ 1 (mod 6). よって, x = 5 + 6k (k∈Z) 5(5+6k) = 25+5×6k ≡ 1 (mod 6) 「6を法として唯一の解が存在する」などと言う.

一次合同方程式 例 4x ≡ 2 (mod 6) を解け. 4 × 0 ≡ 0 (mod 6). 4 × 1 ≡ 4 (mod 6). 4 × 2 ≡ 8 ≡ 2 (mod 6). 4 × 3 ≡ 12 ≡ 0 (mod 6). 4 × 4 ≡ 16 ≡ 4 (mod 6). 4 × 5 ≡ 20 ≡ 2 (mod 6). よって, x = 2 + 6k, 5 + 6k (k∈Z). 例 4x ≡ 1 (mod 6) は解を持たない. mを法として解が複数あったり, 解が無いケースは珍しくない.

一次合同方程式の解 定理. 一次合同方程式 ax ≡ 1 (mod m) に整数解が 存在するための必要十分条件は gcd(a, m) = 1. 証明) x0 が ax ≡ 1 (mod m) の整数解であるとき, 整数 q が存在して ax0 - 1 = mq. ∴ ax0 - mq = 1. a と m の公約数は左辺を割り切るから, 右辺の1も割り切る. よって, gcd(a, m) = 1. 次に, 逆を示す. gcd(a, m) = 1 のとき, ax + my = 1 の整数解が存在する. その解の1組を x=x0, y=y0 とすると, ax0 - 1 = m(-y0). ∴ ax0 ≡ 1 (mod m). よって, ax ≡ 1 (mod m) に整数解が存在する.

一次合同方程式の解 例 8x ≡ 1 (mod 11) を解け. 8x + 11y = 1 を拡張ユークリッドの互除法で解くと. {x = -4 + 11k, y = 3 - 8k} (k∈Z). を得る. よって, 8x ≡ 1 (mod 11) の整数解は x = -4 + 11k (k∈Z). 11を法として唯一の解が存在する. k=1のときx=7. 8×7=56≡1 (mod 11). k=2のときx=18 8×18=144≡1 (mod 11). 定理. gcd(a, m) = 1 のとき, ax ≡ 1 (mod m) の解は, mを法として唯一存在する.

一次合同方程式の解 定理. 一次合同方程式 ax ≡ b (mod m) に整数解が 存在するための必要十分条件は gcd(a, m) | b. 証明) x0 が ax ≡ b (mod m) の整数解であるとき, 整数 q が存在して ax0 - b = mq. ∴ ax0 - mq = b. a と m の公約数は左辺を割り切るから, 右辺の b も割り切る. よって, gcd(a, m) | b. 次に, 逆を示す. gcd(a, m) | b のとき, 整数 a', b', m' が存在して, a = a'gcd(a, m), b = b'gcd(a, m), m = m'gcd(a, m). gcd(a', m') = 1 より, 一次合同式 a'x ≡ 1 (mod m') の解が mを法として唯一存在する.

一次合同方程式の解 定理. 一次合同方程式 ax ≡ b (mod m) に整数解が 存在するための必要十分条件は gcd(a, m) | b. 証明の 続き) その整数解を x = x0 + m'k (k'∈Z) とおくと, a'x0 ≡ 1 (mod m'). ∴ a'b'x0 ≡ b' (mod m'). ... ⛤ よって, 整数 q が存在して a'b'x0 - b' = m'q. 両辺に gcd(a, m) をかけると ab'x0 - b = mq したがって, x = b'x0 は ax ≡ b (mod m) の解である. // 補足) 式⛤より a'(b'x0 + tm') ≡ b' (mod m') (t∈Z) よって, 整数 q が存在して a'(b'x0 + tm') - b' = m'q. 両辺に gcd(a, m) をかけると a(b'x0 + tm') - b = mq したがって, mを法とすると gcd(a, m) 個の解が存在する. 例 x = b'x0, b'x0+m', b'x0+2m', ..., b'x0+(gcd(a,m)-1)m' m'を法とすると これらは合同だが mを法とすると 合同ではない

一次合同方程式の解 例 4x ≡ 2 (mod 6) を解け. gcd(4, 6) = 2 は 2を割り切る. そこで, まず 2x ≡ 1 (mod 3) を解く 2x + 3y = 1 を拡張ユークリッドの互除法で解くと 2 = 3×0 + 2. ∴ 2 - 0×3 = 2 ↓代入 3 = 2×1 + 1. ∴ 3 - 1×2 = 1 ∴ -2 + 3 = 1 ∴ x = -1 + 3k, y = 1 - 2k (k∈Z). ゆえに, 2x ≡ 1 (mod 3) の解は x = -1 + 3k (k∈Z) よって, 4x ≡ 2 (mod 6) の解は 6を法とすると x = -1 と x = -1+3 = 2 の 2つ. したがって, x = -1+6k, 2+6k (k∈Z).

中国の 剰余定理

連立一次合同方程式 3で割ると2余り 5で割ると3余る数ってな～んだ? xを3で割った余りは2である xを5で割った余りは3である x = 3q + 2 (q∈Z) x = 5q + 3 (q∈Z) x - 2 = 3q x - 3 = 5q x ≡ 2 (mod 3) x ≡ 3 (mod 5) 次の連立方程式を解け. {x ≡ 2 (mod 3) x ≡ 3 (mod 5)}

連立一次合同方程式 3で割ると2余る数 (x ≡ 2 (mod 3), x = 3q + 2 (q∈Z)) ... -4, -1, 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, ... 5間隔おき 5間隔おき 5×3=15おき 5で割ると3余る数 (x ≡ 3 (mod 5), x = 5q + 3 (q∈Z)) ... -2, 3, 8, 13, 18, 23, 28, 33, 38, 43, 48, ... 3間隔おき 3間隔おき 3×5=15おき 0 8 20 23 38 40 53 8で合流した3aと5bが次に出会うのは lcm(3, 5) = 15先 答. 8 + 15k (k∈Z) 解がひとつ求まれば 他も求まる. → ひとつ目の解を どうやって求める?

連立一次合同方程式 x ≡ 2 (mod 3), x ≡ 3 (mod 5) を眺めて 何となく "x = 2 + 3" と書いてから, つじつまを合わせてみよう. 5で割ったとき 3で割ったとき 消えてほしい項 消えてほしい項 → x = 2(5x1) + 3(3x2) x = 2( ? ) + 3( ? ) 3で割ったとき余りが 5で割ったとき余りが 2になってほしい項 3になってほしい項 → x = 2(3y1+1) + 3(5y2+1) 例えば, 拡張ユークリッドの互除法で よって, 5x1 = 3y1+1, 3x2 = 5y2+1 を解いて, ⛤ gcd(3,5)=1 x1 = -1+3k1, x2 = 2+5k2 (k1,k2∈Z). だから3x+5y=1は 解ける. したがって, x = 2×5(-1+3k1)+3×3(2+5k2) = 8+15k (k∈Z). //

連立一次合同方程式 3で割ると2余り 5で割ると3余り 7で割ると2余る数ってな～んだ? 次の連立方程式を解け. {x ≡ 2 (mod 3) x ≡ 3 (mod 5) x ≡ 2 (mod 7)} 3と5は互いに素 3と7は互いに素 5と7は互いに素 つまり, 3, 5, 7のどの2つも 互いに素なので, さっきと同様に解けそう.

連立一次合同方程式 x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7) を眺めて 何となく "x = 2 + 3 + 2" と書いてから, つじつまを合わせてみよう. 5と7で割ったとき 3と7で割ったとき 3と5で割ったとき 消えてほしい項 消えてほしい項 消えてほしい項 x = 2( ? ) + 3( ? ) + 2( ? ) 3で割ったとき余りが 5で割ったとき余りが 7で割ったとき余りが 2になってほしい項 3になってほしい項 2になってほしい項 x = 2(35x1) + 3(21x2) + 2(15x3) x = 2(3y1+1) + 3(5y2+1) + 2(7y3+1) よって, 35x1 = 3y1+1, 21x2 = 5y2+1, 15x3 = 7y3+1 を解いて, x1 = 2+3k1, x2 = 1+5k2, x3 = 1+7k3 (k1,k2,k3∈Z). したがって, x = 140+63+30 + 3×5×7k = 233+105k = 23+105k' (k,k'∈Z).

中国の剰余定理 chinese remainder theorem 定理. (中国の剰余定理) あるいは孫子の剰余定理 m1, m2, ..., mn のどの2つも互いに素であるとき, 連立一次合同方程式 {x ≡ a1 (mod m1) x ≡ a2 (mod m2) : : x ≡ an (mod mn)} は, M := m1・m2・...・mn を法として 唯一一組の解を持つ. 解き方. Mi := Π mk = M/mi とおく. k=1 k≠i つまり Mixi + Miyi = 1 を解いて, Mixi ≡ 1 (mod Mi) をみたす xi を1つ求めて ui とおく. x = a1M1u1 + a2M2u2 + ... + anMnUn + Mk (k∈Z).

オイラーの φ関数

オイラーのφ関数 正整数nに対して, → gcd(n,x)=1 1, 2, ..., n のうちmと互いに素なものの個数を φ(m) で表し, Euler's φ function Euler's totient function オイラーのφ関数とかオイラーのトーシェント関数と呼ぶ. 例 φ(1) = 1 (1のみ) φ(2) = 1 (1のみ) φ(3) = 2 (1, 2) φ(4) = 2 (1, 3) φ(5) = 4 (1, 2, 3, 4) φ(6) = 2 (1, 5) φ(7) = 6 (1, 2, 3, 4, 5, 6) φ(8) = 4 (1, 3, 5, 7) φ(9) = 6 (1, 2, 4, 5, 7, 8) φ(10) = 4 (1, 3, 7, 9) 問 φ(m) をnの式で表せるか? 観察 ① nが素数のときφ(n) = n-1 ② φ(9) > φ(10)なのはなぜ? 9 = 3² 3の倍数でなければ9と互いに素. 10 = 2 × 5 2の倍数でも5の倍数でもない数 だけが10と互いに素. 素因数の数が多いと不利?

素因数が1つのときのφ(m) 定理. 素数pと正整数kについて, φ(p^k) = p^k - p^(k-1) = p^k (1 - 1/p). 証明) pの倍数とp^kはpを公約数に持つので互いに素ではない. p^kの正の約数は 1, p, p², ..., p^k であるが, pの倍数ではない数は p, p², ..., p^k を約数に持たないから p^kと互いに素である. 1, 2, ..., p^k のうちpの倍数は [p^k/p] = p^(k-1) 個あるから, φ(p^k) = p^k - p^(k-1) = p^k (1 - 1/p). 系. 素数pについて, φ(p) = p-1.

一般のφ(m)と既約剰余類 2つの整数の間のmを法とする合同関係は同値関係である. residue class a∈Zの同値類を(法mに関するaの)剰余類と呼ぶ. 例 10を法としたとき以下の10個の剰余類にZを分割できる. [0] := {..., -20, -10, 0, 10, 20, ...} [1] := {..., -19, -9, 1, 11, 21, ...} [2] := {..., -18, -8, 2, 12, 22, ...} [3] := {..., -17, -7, 3, 13, 23, ...} [4] := {..., -16, -6, 4, 14, 24, ...} [5] := {..., -15, -5, 5, 15, 25, ...} [6] := {..., -14, -4, 6, 16, 26, ...} [7] := {..., -13, -3, 7, 17, 27, ...} [8] := {..., -12, -2, 8, 18, 28, ...} [9] := {..., -11, -1, 9, 19, 29, ...} [1], [3], [7], [9] に属する数は, いずれも10と互いに素である. [0], [2], [4], [5], [6], [8] に属する数は, いずれも10と互いに素ではない.

一般のφ(m)と既約剰余類 2つの整数の間のmを法とする合同関係は同値関係である. residue class a∈Zの同値類を(法mに関するaの)剰余類と呼ぶ. aとmが互いに素であるとき, aの剰余類に属する数はいずれもmと互いに素である. reduced residue class このような剰余類を既約剰余類と呼ぶ. 定理. φ(n) はnを法とする既約剰余類の個数に等しい. 例 10を法とする既約剰余類は [1] := {..., -19, -9, 1, 11, 21, ...} [3] := {..., -17, -7, 3, 13, 23, ...} [7] := {..., -13, -3, 7, 17, 27, ...} [9] := {..., -11, -1, 9, 19, 29, ...} よって, φ(10) = 4.

一般のφ(m)と既約剰余類 2つの整数の間のmを法とする合同関係は同値関係である. residue class a∈Zの同値類を(法mに関するaの)剰余類と呼ぶ. aとmが互いに素であるとき, aの剰余類に属する数はいずれもmと互いに素である. reduced residue class このような剰余類を既約剰余類と呼ぶ. φ(m)個の既約剰余類のそれぞれから, 自由に1つずつ元を reduced residue system ピックアップして作った集合を, 既約剰余系と呼ぶ. 例 10を法とする既約剰余類は [1] := {..., -19, -9, 1, 11, 21, ...} [3] := {..., -17, -7, 3, 13, 23, ...} [7] := {..., -13, -3, 7, 17, 27, ...} [9] := {..., -11, -1, 9, 19, 29, ...} よって, {1, 3, 7, 9}, {-19, -3, 29}などが既約剰余系.

φ(m)の乗法性 定理. 正整数a, bが互いに素ならば, φ(ab) = φ(a)φ(b). 例 φ(36) = 12 (1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35) φ(4) = 2 (1, 3) φ(9) = 6 (1, 2, 4, 5, 7, 8) φ(36) = φ(4)φ(9). φ(36) = φ(4)φ(9)の証明. (一般のφ(ab) = φ(a)φ(b)の証明も同様) Z4 := {0, 1, 2, 3}, Z9 := {0, 1, 2, ..., 8}, Z36 := {0, 1, 2, ..., 35} Z4* := {x|x∈Z4, gcd(x,4)=1} = {1, 3} ← 4を法とする既約剰余系 Z9* := {x|x∈Z9, gcd(x,9)=1} = {1, 2, 4, 5, 7, 8} ← 9を法とする既約剰余系 Z36* := {x|x∈Z36, gcd(x,36)=1} ← 36を法とする既約剰余系 とおく. φ(36) = |Z36*|, φ(4)φ(9) = |Z4*||Z9*| = |Z4* × Z9*| だから, |Z36*| = |Z4* × Z9*| を示せばよい.

φ(m)の乗法性 |Z36*| = |Z4* × Z9*| を示すには, Z36* と Z4* × Z9* の間の全単射の存在を示せばよい. S を Z36* の元とすると, 除法の定理より整数 q, r が唯一一組存在して S = 4q + r (0≦r < 4). ← Sを4で割った余りをrとおいた. S∈Z36* より gcd(S, 36) = 1 だから gcd(S, 4) = 1, よって gcd(r, 4) = 1. ゆえに r∈Z4*. 同様に, Sを9で割った余りも唯一存在し, Z9* に属する. したがって, f(S) = (r1, r2) (r1, r2はSを4, 9それぞれで割った余り) をみたすような Z36* から Z4* × Z9* への写像 f が存在する. f が全単射であることを示す.

φ(m)の乗法性 Z36* f Z4* × Z9* Z36 Z4 × Z9 0 (0,0) 1 (1,1) 2 (0,2) 3 (3,3) 4 (0,4) 5 (1,5) 6 (2,6) 7 (3,7) 8 (0,8) 9 (1,0) 10 (2,1) 11 (3,2) 12 (0,3) 13 (1,4) 14 (2,5) 15 (3,6) 16 (0,7) 17 (1,8) 18 (2,0) 19 (3,1) 20 (0,2) 21 (1,3) 22 (2,4) 23 (3,5) 24 (0,6) 25 (1,7) 26 (2,8) 27 (3,0) 28 (0,1) 29 (1,2) 30 (2,3) 31 (3,4) 32 (0,5) 33 (1,6) 34 (2,7) 35 (3,8) (r1, r2) を Z4* × Z9* の元とする. 4と9は互いに素だから, 中国の剰余定理より {x ≡ r1 (mod 4) x ≡ r2 (mod 9)} の解は36を法として唯一存在する. ゆえに, 解のうち Z36 に属するものが唯一存在し, それをSとおく. S ≡ r1 (mod 4) より, 整数qが存在して S-r1 = 4q. r1∈Z4* より gcd(r1, 4) = 1 だから gcd(S, 4) = 1. 同様に gcd(S, 9) = 1. よって, gcd(S, 36) = 1. ∴ S∈Z36*. ここで, r1は r1∈Z4*⊆Z4 かつ S≡r1 (mod 4) をみたすから, Sを4で割った余りである. 同様にr2はSを9で割った余りである. よって, f(S) = (r1, r2) となる S∈Z36* が唯一存在する. したがって, fは全単射である. ゆえに φ(36) = φ(4)φ(9).

一般のφ(n)の公式 定理. 正整数nが n = p1^α1・p2^α2・...・pk^αk (p1, ..., pkは相異なる素数, αi≧1). と素因数分解されるとき, φ(n) = φ(p1^α1・p2^α2・...・pk^αk) = φ(p1^α1)φ(p2^α2)...φ(pk^αk) ← p1^α1 と p1^αj は互いに素だから(注) = p1^α1(1 - 1/p1) p2^α2(1 - 1/p2) ... pk^αk(1 - 1/pk) = n(1 - 1/p1)(1 - 1/p2)...(1 - 1/pk). 例 36 = 2²・3² より φ(36) = 36(1 - 1/2)(1 - 1/3) = 12.

フェルマーの 小定理

a^k ≡ 1 は嬉しい 2 ≡ 2 (mod 5). 4 ≡ 4 (mod 6). 5 ≡ 5 (mod 9). 2² ≡ 4 (mod 5). 4² ≡ 16 ≡ 4 (mod 6). 5² ≡ 25 ≡ 7 (mod 9). 2³ ≡ 8 ≡ 3 (mod 5). 4³ ≡ 16 ≡ 4 (mod 6). 5³ ≡ 35 ≡ 8 (mod 9). 2⁴ ≡ 6 ≡ 1 (mod 5). 5⁴ ≡ 40 ≡ 4 (mod 9). 2⁵ ≡ 2 (mod 5). 5⁵ ≡ 20 ≡ 2 (mod 9). 5⁶ ≡ 10 ≡ 1 (mod 9). 2³⁰ ≡ (2⁴)⁷ (2²) 5⁷ ≡ 5 (mod 9). ≡ 1 × 4 ≡ 4 (mod 5) a^k ≡ 1 (mod m) となるkが分かると いろいろ楽になる.

オイラーの定理 定理. 整数aと正整数nが互いに素ならば, a^φ(n) ≡ 1 (mod n) (ただし, φはオイラーのφ関数.) 例 2^φ(3) ≡ 2² ≡ 4 ≡ 1 (mod 3). 7^φ(12) ≡ 7⁴ ≡ 49² ≡ 1² ≡ 1 (mod 12). 4^φ(105) ≡ 4^φ(3)φ(5)φ(7) ≡ 4^48 ≡ 4096^8 ≡ 1^8 ≡ 1 (mod 105). 例 4^1234565 を105で割った余りを求めよ. 4と105は互いに素だから 4^φ(105) ≡ 4^48 ≡ 1 (mod 105). よって, 4^1234565 ≡ 4^(48×25720 + 5) ≡ (4^48)^25720 × 4^5 ≡ 4^5 ≡ 79 (mod 105). よって, 答えは 79.

オイラーの定理 証明.) Z_n* = {x1, x2, ..., xφ(n)} をnを法とする既約剰余系とすると, xi ∈ Z_n* について, gcd(xi, n) = 1. よって, gcd(a, n) = 1 より gcd(axi, n) = 1. ゆえに, ax1, ax2, ..., axφ(n) はいずれも nを法とする既約剰余系の元である. axi ≡ axj (mod n) となる xi, xj (i≠j) があるとすると gcd(a, n) = 1 より両辺をaで割って xi ≡ xj (mod n) ⇔ xiとxjが となってしまい, Z_n* が既約剰余系であることに反する. 同じ剰余類に よって, どの xi, xj (i≠j) についても axi ≢ axj (mod n). ゆえに, A = {ax1, ax2, ..., axφ(n)} もnを法とする既約剰余系である. 例 a=3, n=10のとき Z_10* = {1, 3, 7, 9}, A={3, 9, 21, 27}とすると, 3∈[3], 9∈[9], 21∈[1], 27∈[7] だからAも既約剰余系 属していることを 意味する.

オイラーの定理 ゆえに, xiと同じ剰余類に属しているAの元 yi が存在して, x1 ≡ y1 (mod n) x2 ≡ y2 (mod n) : : xφ(n) ≡ yφ(n) (mod n). これらの辺々を掛けて x1・x2・...・xφ(n) ≡ y1・y2・...・yφ(n) (mod n). ≡ Π axj (mod n) j=1 ≡ a^φ(n) x1・x2・...・xφ(n) (mod n). xi は既約剰余系の元だから xi と n は互いに素. よって, x1・x2・...・xφ(n) と n も互いに素だから両辺を x1・x2・...・xφ(n) で割ると, 1 ≡ a^φ(n) (mod n). // 例 a=3, n=10のとき. x1 x2 x3 x4 Z_10* = {1, 3, 7, 9}. A = {3, 9, 21, 27}, " " " " y2 y4 y1 y3 1 ≡ 21 (mod 10) 3 ≡ 3 " 7 ≡ 27 " 9 ≡ 9 " 1・3・7・9 ≡ 21・3・27・9 ≡ 3⁴・7・1・9・3 ∴ 1 ≡ 3⁴ (mod 10).

オイラーの定理 定理. 整数aと正整数nが互いに素ならば, a^φ(n) ≡ 1 (mod n) (ただし, φはオイラーのφ関数.) フェルマーの小定理 定理. 整数aと素数pが互いに素ならば, a^(p-1) ≡ 1 (mod p) 応用 RSA暗号において, 必ず復号できることの証明に使われる.

RSA暗号

公開鍵暗号 暗号文 C ① m: メッセージ C = f(m, k) 暗号化 ② m = g(c, k) 復号 0 K: 鍵 事前に共有しておく K: 鍵 共通鍵暗号 ① m: メッセージ C = f(m, K1) 暗号化 C 0 K0: 秘密鍵 K1: 公開鍵 ② m = g(c, K0) 復号 事前に鍵共有しなくてよい 公開鍵暗号

RSA暗号 0 準備: 鍵の生成. p, q: 巨大な素数. N := pq. E: φ(N)と互いに素な整数. 2≦E<φ(N). φ(N) = φ(pq) = φ(p)φ(q) = (p-1)(q-1). D: EX ≡ 1 (mod φ(N)) の解の1つ. 2≦D<φ(N). オイラーのφ関数 EX + φ(N)y = 1 を拡張ユークリッドの互除法で解けばよい. 秘密鍵: D ← Nの素因数分解は 現実的な時間では不可能 公開鍵: E, N と信じられているため, φ(N)=(p-1)(q-1) をNから求められる心配はしない.

RSA暗号 ① 暗号化 m: 整数, 0≦m<N. C: m^E をNで割った余り. ← C ≡ x^E (mod N) を メッセージ: m 現実的な時間で解くのは 暗号文: C 不可能と信じられている. (RSA仮定と呼ぶ) ② 復号 C^D をNで割った余りを求めるとmを得る. ↑ 必ず得られることが 証明できる.

RSA暗号 定理. C^D をNで割った余りはmである. 証明) 0≦m<Nなので, C^D ≡ m (mod N) を示せばよい. ED ≡ 1 (mod φ(N)) より, 整数kが存在して ED - 1 = kφ(N) = kφ(pq) = kφ(p)φ(q) = k(p-1)(q-1). (1) mとpが互いに素なとき, フェルマーの小定理より C ≡ m^E ∴ C^D ≡ m^ED なので, m^EDに注目してる m^ED ≡ m^(k(p-1)(q-1)+1) ≡ (m^(p-1))^(k(q-1)) ・ m ≡ m (mod p). (2) mとpが互いに素でないとき, mはpの倍数だから m^ED ≡ 0 ≡ m (mod p). (1), (2)より, m^ED ≡ m (mod p). 同様に, m^ED ≡ m (mod q).

RSA暗号 {m^ED ≡ m (mod p) m^ED ≡ m (mod q)} より, 整数s, tが存在して, {m^ED - m = sp m^ED - m = tq} よって, sp = tq だから, spはpの倍数であると同時にqの倍数でもある. ゆえに, spは lcm(p, q) = pq の倍数である. ← p, qは素数なので lcm(p, q) = pq. よって, 整数uが存在して, sp = m^ED - m = upq. ゆえに, m^ED ≡ m (mod pq) したがって, C^D ≡ m^ED ≡ m (mod N). //