中間追試験の解答

情報代数学 I 中間追試験問題 2015.07.07
学籍番号：氏名 1
(1) 1728 を素因数分解せよ。
総得点 (2) φ(1728) を求めよ。
(10 点)
【解答】 (1): 1728 = 26 · 33
(2): φ(1728) = φ(26 · 33 ) = φ(26 )φ(33 ) = 25 · (2 − 1) · 32 · (3 − 1) = 576
2 次の連立合同式を解け。ただし答は 0 ≤ x < 143 の範囲で求めること。(10 点)
{
x≡2
mod 11
x≡8
mod 13
【解答】拡張ユークリッドの互除法より 11 · 6 + 13 · (−5) = 1 であることが示せる。これより
13 · (−5) ≡ 1 mod 11, 11 · 6 ≡ 1 mod 13 である。ここで x = 8 · 11 · 6 + 2 · 13 · (−5) とおくと
x = 8 · 11 · 6 + 2 · 13 · (−5) ≡ 2 · 13 · (−5) ≡ 2 · 1 ≡ 2 mod 11
≡ 8 · 11 · 6 ≡ 8 · 1 ≡ 8
mod 13
より x は与えられた連立方程式の解となる。x = 8 · 11 · 6 + 2 · 13 · (−5) = 398 ≡ 112 mod 143 より
x = 112 が求める解となる。
3
2197 と 2561 の最大公約数を d とするとき、以下の問に答えよ。(10 点)
(1) d を求めよ。
(2) 2197u + 2561v = d を満たす u, v ∈ Z を一組求めよ。
(3) 2197x + 2561y = 117 を満たす x, y ∈ Z をすべて求めよ。
【解答】 (1): ユークリッドの互除法により
2561 = 2197 × 1 + 364 ⇝ 2197 × (−1) + 2561 × 1 = 364
2197 = 364 × 6 + 13
⇝ 2197 × 7 + 2561 × (−6) = 13
364 = 13 × 28 + 0
よって d = (2197, 2561) = (2197, 364) = (13, 364) = (13, 0) = 13 である。
(2): 上の計算より u = 77, v = −6 とすればよい。
(3): 117 = 13 · 9 より 2197x + 2561y = 117 の両辺を 13 で割った 169x + 197y = 9 を解けばよい。
(2) で得た 2197 · 7 + 2561 · (−6) = 13 の両辺を 13 で割ると 169 · 7 + 197 · (−6) = 1 となる。この式
の両辺を 9 倍して引くことで次を得る。
169 · x
+ 197 · y
= 9
−) 169 · 7 · 9
+ 197 · (−6) · 9 = 9
169 (x − 63) + 197 (y + 54) = 0
これより 169(63 − x) = 197(y + 54) である。ここで 169 · 7 + 197 · (−6) = 1 より (169, 197) = 1
なのである整数 k を用いて 63 − x = 197k, y + 54 = 169k と表せる。以上から x = −197k + 63
63,
y = 169k − 54 (kk ∈ Z
Z) が解となる。

Download Report