Kryptografia_zadania_07.pdf

7 Kongruencje

7.1. Niech a, b ∈ Z i m, n ∈ N będą takie, że a ≡ b (mod m) i a ≡ b (mod n).

(a) Wykazać, że jeżeli NWD(m, n) = 1, to a ≡ b (mod mn).

(1)

(b) Uzasadnić, że założenia NWD(m, n) = 1 w punkcie (a) nie można pominąć.

(1)

7.2. Rozstrzygnąć, które z poniższych kongruencji mają rozwiązania, a następnie zna

leźć wszystkie te rozwiązania.

(2)

(a) 27x ≡ 72 (mod 900),

(b) 27x ≡ 72 (mod 999),

7.3. Znaleźć najmniejszą liczbę naturalną, która daje resztę 1 przy dzieleniu przez 11,

resztę 2 przy dzieleniu przez 12 i resztę 3 przy dzieleniu przez 13.

(2)

7.4. Niech p > 2 będzie liczbą pierwszą. Wykazać, że jedynymi rozwiązaniami kongru

encji

x 2

≡ 1 (mod p)

w zbiorze Z p

są x = 1 i x = p − 1.

(2)

7.5. (a) Udowodnić twierdzenie Wilsona:

Dla dowolnej liczby pierwszej p: (p − 1)! ≡ −1 (mod p).

(2)

(b) Wykazać, że jeżeli n jest liczbą złożoną, to (n − 1)! ≡ −1 (mod n).

(1)

7.6. Rozwiązać układy kongruencji

(a)

2x + 3y ≡ 1 (mod 26)

(1)

7x + 8y ≡ 2 (mod 26)

(b)

x + 3y ≡ 1 (mod 26)

(2)

7x + 9y ≡ 1 (mod 26)

(a)

x + 3y ≡ 1 (mod 26)

(2)

7x + 9y ≡ 2 (mod 26)