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)