7 Kongruencje
7.1. Niech a, b " Z i m, n " N będą takie, że a a" b (mod m) i a a" b (mod n).
(a) Wykazać, że jeżeli NWD(m, n) = 1, to a a" b (mod mn). (1)
(b) Uzasadnić, że założenia NWD(m, n) = 1 w punkcie (a) nie można pominąć. (1)
(c) Rozstrzygnąć, czy, bez dodatkowych założeń, a a" b (mod NWW(m, n)). (1)
7.2. Rozstrzygnąć, które z poniższych kongruencji mają rozwiązania, a następnie zna-
lez
ć wszystkie te rozwiązania. (2)
(a) 27x a" 72 (mod 900),
(b) 27x a" 72 (mod 999),
(c) 100x a" 37 (mod 999).
7.3. Znalez
ć 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
x2 a" 1 (mod p)
w zbiorze Z+ sÄ… x = 1 i x = p - 1. (2)
p
7.5. (a) Udowodnić twierdzenie Wilsona:
Dla dowolnej liczby pierwszej p: (p - 1)! a" -1 (mod p). (2)
(b) Wykazać, że jeżeli n jest liczbą złożoną, to (n - 1)! a" -1 (mod n). (1)
7.6. Rozwiązać układy kongruencji
Å„Å‚
ôÅ‚
òÅ‚
2x + 3y a" 1 (mod 26)
(a) (1)
ôÅ‚
ół
7x + 8y a" 2 (mod 26)
Å„Å‚
ôÅ‚
òÅ‚
x + 3y a" 1 (mod 26)
(b) (2)
ôÅ‚
ół
7x + 9y a" 1 (mod 26)
Å„Å‚
ôÅ‚
òÅ‚
x + 3y a" 1 (mod 26)
(a) (2)
ôÅ‚
ół
7x + 9y a" 2 (mod 26)