情報基礎数学 I ・構造数理 問題

1. 8 桁の自然数 25x22341 が 11 で割り切れるときの x の値を求めよ.

2. 7 桁の自然数 n = 1x540y4 が 72 で割り切れるとき, x, y の組 (x, y) を全て求めよ. (ヒント. 72 = 9 × 8 より, n が 72 で割り切れることと, n が 8, 9 で割り切れることが同値であることを用いる.)

3. 6 桁の自然数 n を前 3 桁と後 3 桁の数に分けて, その差が 7 で割り切れるときに, n も 7 で割り切れる, ことを証明せよ.

4. R(7) ∈ ℤ/103ℤ = {R(0), R(1), …, R(102)} に対して, (R(7))^{−1} = R(x) をみたす自然数 x (1 ≤ x ≤ 102) を求めよ.

5. (1) ℤ/13ℤ = {R(0), R(1), …, R(12)} において, 次の等式をみたす整数 x (0 ≤ x ≤ 12) を求めよ. (次の式の演算は ℤ/13ℤ での演算である.)

K(x) = (R(7) + R(9)) ÷ R(6)

(2) ℤ/13ℤ の元 R(a), R(b) で, R(a)R(b) = R(0) かつ 0 < a, b < 13 となるものは存在するかどうか理由をつけて答えよ.

6. ℤ/nℤ の任意のゼロ元 (注. ゼロ元とは R(0) のこと) でない 2 つの元 R(a), R(b) の積 R(a)R(b) がゼロ元にならないとき, ℤ/nℤ は整域 (せいいき) であるという. ℤ/nℤ が整域であることと, n が素数であることが同値であることを示せ.

7. 一次合同式 21x ≡ 9 (mod 15) を解け. 更に, 15 を法としたときの解の個数を求めよ.

8. 次の (1), (2) を答えよ.

(1) ある自然数 x は 10, 11, 21 で割るとそれぞれ, 2, 3, 1 余るという. これの x に関する連立一次合同式を書け.

(2) (1) の連立一次合同式の正の最小解を求めよ.

9. 次の連立一次合同式を解け. 更に, 0 以上 1000 以下となる整数解を全て求めよ.

x ≡ 2 (mod 5)
x ≡ 3 (mod 7)
x ≡ 2 (mod 11)

(注. オイラー関数を φ(n) と表す.)

10. φ(n) = 2 となるような自然数 n を全て求めよ.

11. n > 2 となる自然数 n に対して, φ(n) は偶数になることを示せ.

12. (1) φ(n) = \frac{2n}{3} をみたす自然数 n を求めよ.

(2) φ(n) = \frac{n}{3} をみたす自然数 n を求めよ.

(3) 問題 (1) を一般化した命題を作り, その命題を証明せよ.

13. (a, 561) = 1 をみたす任意の整数 a に対して, a^{560} ≡ 1 (mod 561)

が成り立つことを示せ. (補足. (a, n) = 1 をみたす任意の整数 a に対して, a^{n−1} ≡ 1 (mod n) となる合成数 n をカーマイケル数と呼ぶ.)

14. 次の割り算の余りを求めよ.

(1) 13^{100} ÷ 16 (2) 10^{100} ÷ 17 (3) (2^{11213} − 1) ÷ 13 (4) 267^{311} ÷ 37

15. (1) 3^{100} を 35 で割ったときの余りを求めよ.

(2) 全ての整数 a に対して, a^{25} ≡ a (mod 35) が成り立つかどうか理由をつけて答えよ.

16. 暗号化鍵 (n, e) = (91, 7) をもつ暗号文 y = 3 を解読せよ. (すなわち, 暗号化鍵 (91, 7) から復号化鍵 d を求め, 暗号文 y を復号化し, 元の平文 x を求めよ.)

17. 暗号化鍵 (公開鍵) が (n, e) = (187, 23) となる RSA 暗号について, 次の (1) と (2) を答えよ.

(1) 復号化鍵 (秘密鍵) d を求めよ.

(2) 暗号文 y = 3 を復号化し, 元の平文 x を求めよ.

18. n を自然数, x と y は x ≡ y (mod φ(n)) となる整数とする. このとき, (a, n) = 1 となる任意の整数 a に対して,

a^{x} ≡ a^{y} (mod n)

が成立することを示せ.

19. p, q が異なる奇素数で, 2^{p} ≡ 2 (mod q), 2^{q} ≡ 2 (mod p)

が成り立つとする. このとき, 2^{pq} ≡ 2 (mod pq) であることを証明せよ.

20. 整数 n に対して n^{2} を 100 で割ったとき, 余りが 35 になることがあるかどうか理由をつけて答えよ.