合同、整除および算術関数
導入済み| English | 意味 |
|---|---|
| congruence/ˈkɒŋɡruːəns/ | 合同 |
| totient/ˈtəʊʃənt/ | オイラー関数 |
解答前に考えるべきこと
- 機械Aが4分周期で、機械Bが7分周期で動作します。同時位置問題は十進近似ではなく合同問題です。
- 目標: gcd条件を使って線形合同方程式を解くこと。
関係性を読む
- 方程式 ax≡b (mod n) が解を持つのは、d=gcd(a,n) が b を割る場合のみです。そうであれば、a, b, n を d で割って、係数が逆元を持つ方程式を得ます。これは n/d modulo で1つの剰余解を持ち、n modulo で d 個の相異なる解を持ちます。係数を割ったまま元の剰余をそのままにすると、一般的に解を失います。素因数分解は別の整除性の道具を提供します：n^k が素数幂の積 p^a で割れる必要がある場合、n の各素数の指数は ceil(a/k) 以上でなければなりません。これらの最小指数は独立して、最も小さい正の許容される n を生成します。n⁴ が 2⁷·3⁵ で割れる必要がある場合、n は 2² と 3² を含み、最小値は 36 です。これは合同除法で解くものではなく、素数指数に関する条件です。
- 互いに素な合同方程式を中国剩余定理で組み合わせる。
How many distinct solutions modulo 18 satisfy 6x≡12?
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
gcd(6,18)=6 divides 12, so there are six solutions; after dividing the modulus too, x≡2 modulo 3.
定義ルールを使う
- 拡張ユークリッド算法は gcd(a,n) を ua+vn の形で表します。gcd が 1 の場合、u は a の mod n における逆元となります。簡約後に必要な範囲の代表者を選んでください。7 と 26 について、1=15·7−4·26 であるため、15 は 7 mod 26 における逆元です。符号誤りを検出するために積を確認してください。
- 可逆な剰余類にのみオイラーの定理を適用する。
What is the least nonnegative x with x≡1 modulo 3 and x≡2 modulo 5?
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
Among 1,4,7,10,13 modulo 15, only 7 has residue 2 modulo 5.
条件を確認する
- 互いに素な正の剰余類 m, n に対して、中国剰余の定理により、各剰余条件のペアに対してtn mod mn における解が唯一つ存在する。第二の合同式に x=r+mk を代入して k について解け。剰余類が互いに素でない場合、剰余値は gcd(m,n) mod において一致しなければならない。整合性がある場合、一意性は積ではなく最小公倍数 mod となる。
- 素数べきの整除利用により、許容される最小整数を求める。
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) となる。
phi(12) equals ____.
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
The coprime residues are 1,5,7,11, or use 12(1−1/2)(1−1/3)=4.
タスク形式を適用する
- Eulerの位相関数 phi(n) は n と互いに素な剰余類の数を数える。異なる素因数 p について、phi(n)=n times the product of (1−1/p)。Eulerの定理により a^phi(n)≡1 となるのは gcd(a,n)=1 の場合のみである。素数の場合はフェルマーの小定理である。この条件を確認した後にのみ指数を縮小せよ。非単位元は反復の乗によって0になりうる。
- 素数べきの整除利用により、許容される最小整数を求める。
式 a^φ(n)≡1 は任意の a に対して偽である。例えば、2 は mod 8 で可逆ではなく、2^4 は mod 8 でゼロである。
このケースに当てはまる答えはどれか？
最大公約数の条件を用いて線形合同方程式を解く
x≡0 modulo 4 and x≡1 modulo 6 have a simultaneous solution.
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
The first condition makes x even, the second makes it odd; residues disagree modulo gcd(4,6)=2.
区別を保つ
- 合同 — 剰余類の差を剰余類が割ることに由来する剰余類の等価性。
- トテント — 正の整数剰余類と互いに素な剰余類の個数。
- 最大公約数の条件を用いて線形合同式を解く。
- 互いに素な合同方程式を中国剩余定理で組み合わせる。
- 可逆な剰余類にのみオイラーの定理を適用する。
- 素数べきの整除利用により、許容される最小整数を求める。
Match each term with its precise meaning in this lesson.
難易度 2/5 · 140 コイン + 今日初回完了時に小ボーナス付与
Keep the distinctions stated in the teaching example.
Put this lesson’s reasoning or event sequence in order.
難易度 3/5 · 200 コイン + 今日初回完了時に小ボーナス付与
The order follows the stated process; check each stage before the next.