Kryptografia_zadania_04.pdf

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 a 2 + b 2

= c 2 . Pokazać, że

60|abc.

(3)

4.4.

Niech p będzie liczbą pierwszą, k ∈

i b ∈

Z. Mówimy, że p k

jest dzielnikiem

dokładnym liczby b, co zapisujemy p k b, jeżeli p k |b, ale p k+1

nie jest dzielnikiem liczby

b. Wykazać, że

(a) p k a ∧ p m b ⇒ p k+m ab,

(1)

(b) p k a ∧ p m b ∧ k < m ⇒ p k a + b.

(1)

p k a ∧ p k b ∧ ⇒ p k a + b

nie jest, na ogół, prawdziwa.

(1)

4.5. (a) Wykazać, że jeżeli n jest liczbą nieparzystą, to NWD(n, n + 2 k ) = 1 dla każdej

liczby k ∈ N. (1)

(b) Znaleźć 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)

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: