A.6 · Congruences, divisibility and arithmetic functions

大学卒GRE準備。検証済みETS範囲内の地域的な目標；これは独自の教育であり、公式テストや得点予測器ではありません。

前提知識：ユークリッドの互除法、素因数分解、合同計算。

• gcd条件を用いて線形合同方程式を解く
• 中国剰余定理を用いて互いに素な合同条件を組み合わせる
• 逆元が存在する余類に対してのみオイラーの定理を適用する
• 素指数の整除性を用いて最小の許容整数を見つける

合同: 剰余の等価性。剰余の差が剰数で割り切れるとき成立する。

トッティエン特異関数: 正の整数剰数と互いに素な剰類の個数。

方程式 ax≡b (mod n) が解を持つのは、d=gcd(a,n) が b を割るときだけである。その場合、a, b, n を d で割って逆元係数を持つ方程式を得る。これには mod n/d で剰類が1つあり、mod n で d 個の異なる解がある。係数を割ったまま元の剰数を使うと、一般に解が失われる。素因数分解による別の整除判定として、n^k が素数のべきの积 p^a で割り切れるなら、n の各素指数は ceil(a/k) 以上でなければならない。これらの最小指数は独立して最小の正の許容 n を定める。n⁴ が 2⁷·3⁵ で割り切れるなら、n には 2² と 3² を含み、最小値は 36 となる。これは合同による除法ではなく、素指数の条件である。

拡張ユークリデス法はgcd(a,n)をua+vnとして表す。gcdが1のとき、uはnを法とするaの逆元である。剰余後、必要な範囲の代表元を選択する。7および26について、1=15·7−4·26であるため、15は26を法とする7の逆元となる；符号誤りを検出するため積を確認せよ。

互いに素な正の剰数 m, n について、中国剰余定理は各剰類条件のペアに対し mod mn でちょうど1つの解を与える。x=r+mk を第2の合同に代入して k を解け。剰数が互いに素でない場合、剰類の値は gcd(m,n) 上で一致しなければならない。整合性が取れた場合、一意性は剰数の积ではなく最小公倍数で決まる。

オイラーのトッティエン φ(n) は n と互いに素な剰類の個数を数える。素因数 p が異なれば、φ(n)=n × ∏(1−1/p)。オイラーの定理は gcd(a,n)=1 のときのみ a^phi(n)≡1 を与える。素数の場合はフェルマーの小定理である。この条件を確認した後にのみ指数を減少させよ。非単位元は反復の累乗でゼロになることがある。

6x≡9 (mod 15) を解く。最大公約数は 3 であり、9 を割る。3つの量すべてを割って 2x≡3 (mod 5) を得る。2 の逆元は 3 であるから、x≡9≡4 (mod 5) となる。元の剰余類 15 における解は 4,9,14 である。x≡2 (mod 4) かつ x≡3 (mod 7) の場合、x=2+4k と書き、4k≡1 (mod 7) となり、k≡2 が得られる。よって x≡10 (mod 28) となる。

式 a^φ(n)≡1 は任意の a に対して偽である。例えば、2 は mod 8 で可逆ではなく、2^4 は mod 8 でゼロである。

$8x\equiv12\pmod{20}$ を完全に解け。7 の mod 20 における逆元を見つけて、なぜオイラーの定理を使って $2^8$ を 1 に置換できないかを説明せよ（mod 20）。

解例

gcdは4であり、12を割る。3つの数を全て$2x\equiv3\pmod5$で割ると$x\equiv4\pmod5$となる。20 mod で4つの答えは$4,9,14,19$であり、代入すると毎回余りは12となる。$7\cdot3=21$であるため、7の逆元は3である。$\phi(20)=8$虽是unitではないが、Eulerの定理は単元に必要とする。2と20のgcdは2であり、$2^8=256\equiv16$であり、1ではない。

$x\equiv2\pmod6$、$x\equiv5\pmod9$ を解くか、矛盾を証明せよ。一意性のための剰数を述べよ。$2^5\cdot3^7$ が $n^3$ を割るような最小の正の n を見つけよ。

解答後の確認

残差は最大公約数3で合同である。$x=2+6k$とすると、$6k\equiv3\pmod9$、よって$2k\equiv1\pmod3$および$k\equiv2\pmod3$となる。したがって$x\equiv14\pmod{18}$である。法線数は最小公倍数であり、54ではない。整除問題では、nの素因数の指数を記述する。これらは$3a\ge5$、$3b\ge7$を満たさねばならず、$a\ge2$、$b\ge3$となる。最小のnは$2^2\cdot3^3=108$であり、他の素因数は値を増大させるのみである。