数論入門期末試験問題

数論入門期末試験問題（担当西澤）
• 試験時間は 80 分、持ち込みは全て不可です。
• 求める過程の概略を書いてください。部分点を考慮する場合があります。また、解答だけでは点数を与えません。講義
で用いた記法は断りなしで用いて構いませんが、それ以外の記号、記法を用いるときは、その定義を明確にしてくださ
い。
問題
1. 10001 = 73 × 137 であることを用い、10500 を 73 で割った余りを求めよ（5 点）
(2) 13300 を 198 で割った余りを求めよ（10 点）。
2. (1) φ(198) を求めよ。
3. 次の１次合同式の解の全体とその個数を求めよ。解がない場合もある。オイラーの定理が使える場合は使ってもよい
（35 点）。
(1)
87x ≡ 132 (mod 24)
def.
(2)
242x ≡ 33 (mod 2)
(3)
def.
56x ≡ 33 (mod 13)
def.
4. a, b, ∈ Z に対し、d := gcd(a, b)、aZ + bZ := {ak + bl | k, l ∈ Z}、dZ := {dm | m ∈ Z} とする。このとき、
aZ + bZ = dZ であることを示せ。ただし、「ax + by = d である x、y ∈ Z が存在する。」ことは証明なしで用いてよい。
（ヒント : (i) aZ + bZ ⊂ dZ、(ii) aZ + bZ ⊃ dZ をいう。）（10 点）
def.
5. n ∈ N、a ∈ Z に対し、C(a) := {x ∈ Z | x ≡ a (mod n)} とし、a、b ∈ Z に対し、C(a)、C(b) の和 C(a) + C(b)、
積 C(a)C(b) を、
def.
C(a) + C(b) := C(a + b),
def.
C(a)C(b) := C(ab)
で定義する。このとき、a、a′ 、b、b′ ∈ Z に対し、C(a) = C(a′ )、C(b) = C(b′ ) がいえるとき、次の (i)、(ii) が成り立
つことを示せ（10 点）。
(i)
C(a) + C(b) = C(a′ ) + C(b′ ),
6. 次の連立１次合同式の解全体とその個数を求めよ。解は


 x≡1
x≡2


x≡7
(ii) C(a)C(b) = C(a′ )C(b′ )
220 未満の正の整数で答えること（15 点）。
(mod 4)
(mod 5)
(mod 11)
7. a、b を互いに素である自然数とする。a を法とする既約剰余系を {a1 , · · · , am }, b を法とする既約剰余系を {b1 , · · · , bn }
とする。mn 個の連立一次合同式
{
x ≡ ai (mod a)
x ≡ bj
(mod b)
は、それぞれ、ab を法としてただひとつの解 x = cij を持つ。このとき、{cij | 1 ≤ i ≤ m, 1 ≤ j ≤ n} が ab を法とす
る既約剰余系をなすことをいうために、i = 1, · · · , m、j = 1, · · · , n に対し、次の (1) ∼ (3) を示せ。（15 点）
(1) cij が ab を法として互いに合同ではないこと、
(2) cij が ab を法とする既約剰余系の一部をなすこと、
(3) cij が ab を法とする既約剰余系を尽くすこと。

Download Report