Kryptografia zadania 04


4 Podzielność i NWD
4.1. Wykazać, że relacja podzielności w zbiorze Z ma następujące własności:
1. a|b '" b|a Ò! |a| = |b|, (1)
2. a|c '" b|c '" NWD(a, b) = 1 Ò! ab|c, (1)
3. a|bc '" NWD(a, b) = 1 Ò! a|c dla dowolnych x, y " Z. (1)
4.2. Najmniejszą wspólną wielokrotnością dwóch liczb naturalnych a i b nazywamy
najmniejszą liczbę naturalną (oznaczaną NWW(a, b)), która jest wielokrotnością każdej
z tych liczb. Wykazać, że
1. NWW(na, nb) = n · NWW(a, ) dla każdej liczby naturalnej n, (1)
2. NWD(a, b) · NWW(a, b) = ab. (1)
4.3. Niech a, b, c " Z będą liczbami spełniającymi warunek a2 + b2 = c2. Pokazać, że
60|abc. (3)
4.4. Niech p będzie liczbą pierwszą, k " N i b " Z. Mówimy, że pk jest dzielnikiem
dokładnym liczby b, co zapisujemy pk b, jeżeli pk|b, ale pk+1 nie jest dzielnikiem liczby
b. Wykazać, że
(a) pk a '" pm b Ò! pk+m ab, (1)
(b) pk a '" pm b '" k < m Ò! pk a + b. (1)
(c) implikacja
pk a '" pk b '" Ò! pk a + b
nie jest, na ogół, prawdziwa. (1)
4.5. (a) Wykazać, że jeżeli n jest liczbą nieparzystą, to NWD(n, n+2k) = 1 dla każdej
liczby k " N. (1)
(b) Znalezć wszystkie liczby naturalne n, dla których zachodzi równość NWD(n, n+
4) = 4. (1)
4.6. Dla każdego z poniższych równań zbadać, czy istnieją liczby całkowite x, y speł-
niające to równanie. Jeżeli tak, to wyznaczyć takie rozwiązanie (x, y), w którym x ma
możliwie najmniejszą wartość bezwzględną. (2)
1. 4543x + 4484y = 59,
2. 4543x + 4484y = 324,
3. 4543x + 4484y = 177.
4.7. Niech a, b będą względnie pierwszymi liczbami całkowitymi. Wykazać, że jeżeli
równanie
ax + by = 1
(z niewiadomymi x, y) ma jedno rozwiązanie, to ma nieskończenie wiele rozwiązań.
Wyznaczyć je. (2)


Wyszukiwarka