情報代数学 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) が解となる。
© Copyright 2024 ExpyDoc