2016年度現代数学入門 B 第8回演習

2016 年度現代数学入門 B 第 8 回演習
演習 8.29. 次の a, b について，a, b の最大公約数 d と ax + by = d となる整数 (x, y) を，拡
張されたユークリッドの互除法を用いて求めよ．
(1) (a, b) = (3107, 975).
(2) (a, b) = (76080, 43200).
(3) (a, b) = (15015819, 11449711).
演習 8.30. （小問の間に直接の関係はない．
）
(1) 463 mod 127 および 41204 mod 127 の値を求めよ．（なお 127 は素数である．）
(2) p = 97 は素数である．このとき，596 mod 97 を直接計算し，この場合にフェルマーの
小定理が成り立っていることを確認せよ．
(3) n = 385 は素数ではない．オイラー関数 φ に対して，φ(385) を求め，6φ(385) mod 385
を直接計算し，この場合にオイラーの定理が成り立っていることを確認せよ．
演習 8.31. （小問の間に直接の関係はない．
）
(1) Z56 と Z58 の中で，45−1 はそれぞれ何になるか求めよ．
(2) Z173 の中で 5−1 ，49−1 をそれぞれ求めよ．
(3) 合同方程式 201x ≡ 2 mod 2839 を解け．
演習 8.32. （小問の間に直接の関係はない．
）
(1) 連立合同式 x ≡ 2 mod 5, x ≡ 3 mod 8, x ≡ 4 mod 9 を解け．
(2) 連立合同式 x ≡ 13 mod 20, x ≡ −12 mod 21, x ≡ −7 mod 23 を解け．
(3) 机の上に n 枚のコインがある．2 枚ずつ数えると 1 枚余る．3,4,5,6,7 枚ずつ数えると，
それぞれ 2,3,4,5,6 枚余る．n の最小値を求めよ．
演習 8.33. a ∈ Z2465 に対して，a2465 mod 2465 はどのような値になるか．フェルマーの
小定理と中国剰余定理を用いて求めよ．（なお，2465 は素数ではない．また a = 0∼2464
までを直接調べるのはもちろん非現実的であることに注意せよ．
）

Download Report