następny punkt » |
Rozpoczniemy od przedstawienia podstawowej własności, która mówi, że każdą liczbę naturalną m można przedstawić jako sumę wielokrotności dowolnej innej liczby naturalnej n i reszty z dzielenia liczby m przez n.
Twierdzenie
Dla każdej pary n, m liczb naturalnych, gdzie n > 0,
istnieje para liczb naturalnych k, l taka, że:
Na przykład dla: n = 5 i m = 12, to przedstawienie ma postać 12 = 2×5 + 2.
Podobne twierdzenie zachodzi, gdy liczba m jest całkowita, z tym że liczba k w tym przypadku nie musi być liczbą naturalną.
Twierdzenie
Dla każdej liczby całkowitej m i liczby naturalnej n > 0 znajdziemy dokładnie jedną parę liczb k, l gdzie k Î Z i 0 £ l < n o tej własności, że m = k × n + l.
Liczbę l nazywamy resztą z dzielenia m przez n.
Jeżeli l = 0 to mówimy, że m jest podzielna przez n i zapisujemy ten fakt używając symbolu n|m (n dzieli m). Liczba n jest wtedy dzielnikiem liczby m.
Przedstawiamy teraz cechy podzielności, to znaczy takie własności, które pozwalają wykazać podzielność danej liczby bez konieczności wykonywania dzielenia. Najprostszą cechą podzielności jest cecha podzielności przez 2.
Analogicznie wygląda cecha podzielności przez 2n, gdzie n > 0. Wystarczy rozpatrzyć liczbę złożoną z n ostatnich cyfr danej liczby.
Przykład:
Sprawdzić, czy liczba 123540 jest podzielna przez 4.
Liczba 40 dzieli się przez 4, a zatem liczba 123540 też dzieli się przez 4.
Przykład:
Sprawdzić, czy liczba 25479 jest podzielna przez 3.
Sprawdzamy sumę cyfr: 2+5+4+7+9 = 27. Ponieważ 27 dzieli się przez 3, to 25479 też dzieli się przez 3.
Analogicznie wygląda cecha podzielności przez 9.
Przykład:
Sprawdzić, czy liczba 5123535342562 jest podzielna przez 7.
Określamy trzy-cyfrowe bloki: 562, 342, 535, 123, 5. Obliczamy:
562 - 342 + 535 - 123 + 5 = 637 = 7×
91.
Zatem 5123535342562 również dzieli się przez 7.
Analogicznie wygląda cecha podzielności przez 11 i 13.
Przykład:
Sprawdzić, czy liczba 5123536342562 jest podzielna przez 11.
Zgodnie z podaną regułą obliczamy:
2-6+5-2+4-3+6-3+5-3+2-1+5 = 11 = 11 ×
1.
Zatem 5123536342562 też dzieli się przez 11.
Pytanie kontrolne 1: Zgodnie z podanymi regułami podzielności sprawdzić czy liczba 2913237360 jest podzielna przez 11.
Definicja liczby pierwszej
Liczbę naturalną p nazywamy pierwszą wtedy, gdy p ¹ 0 i dla każdej liczby naturalnej n: jeżeli n | p to n = p lub n = 1.
Liczba pierwsza to zatem taka liczba, której jedynymi dzielnikami są 1 i ona sama.
Początkowe liczby pierwsze to: 2, 3, 5, 7, 11, 13, 17, 19,...
Definicja
Liczba naturalna p jest największym wspólnym dzielnikiem liczb całkowitych m i n wtedy, gdy:
(i) p |m i p |n;
(ii) jeżeli q |m i q |n to q |p.
Liczba p jest zatem największą liczbą naturalną, która dzieli jednocześnie m i n.
Największy wspólny podzielnik p liczb m i n oznaczamy następująco: p = NWD(m, n). Liczba p jest zatem największą liczbą naturalną, która dzieli jednocześnie m i n. Na przykład: dla n = 36 i m =24, NWD(36, 24)=12.
Na przykład: względnie pierwsze są liczby 3 i 7 oraz 4 i 9: NWD(3,7)=1, NWD(4,19)=1.
Twierdzenie
Jeśli m i n są względnie pierwsze i m |( n × p) to m |p.
np. 3 | ( 7 × 9) Þ 3|9.
Pytanie kontrolne 2: Znajdź największy wspólny dzielnik liczb: 105 i 70.
Twierdzenie
Dla każdej liczby naturalnej m > 1 istnieją liczby pierwsze p1,.., pn, takie że m = p1× ...× pn. Rozkład taki jest jednoznaczny z dokładnością do przestawienia liczb pierwszych.
Na przykład liczby 324 i 510 możemy przedstawić w postaci:
324 = 2× 2× 3× 3× 3× 3, 510 = 2× 5× 3× 17.
Liczby pierwsze wchodzące w skład rozkładu mogą się powtarzać!
Przedstawimy teraz algorytm pozwalający wyliczyć największy wspólny dzielnik dowolnych liczb naturalnych m i n. Został on sformułowany przez Euklidesa ponad 2300 lat temu.
Można opisać go następująco:
Załóżmy, że np. m > n (jeśli m = n to NWD(m, n) = m). W pierwszym kroku dzielimy liczbą większą przez mniejszą, czyli m przez n. Jeśli reszta z dzielenia jest niezerowa, to staje się ona nową liczbą, przez którą dzielimy, a nowa liczbą dzieloną staje się liczba, przez którą dzieliliśmy w poprzednim kroku, czyli n. Procedurę tę kontynuujemy, aż do uzyskania zerowej reszty. Ostatnia niezerowa reszta jest szukanym największym wspólnym dzielnikiem. Zapiszmy to symbolicznie:
Dane: liczby naturalne m, n Î N, gdzie m > n.
Procedura:
Krok 1.
Korzystając z twierdzenia o podzielności zapisujemy liczbę m jako sumę
wielokrotności liczby n i reszty r1: m =
k1 n + r1 gdzie 0 £
r1 < n.
Uwaga: q |m i q |n Û q |n i q |r1, zatem NWD(m, n) = NWD(n, r1).
Krok 2. n = k2 r1 + r2 gdzie 0 £ r2 < r1
Uwaga: NWD(n,r1) = NWD(r1, r2).
Krok 3. r1 = k3 r2 + r3 gdzie 0 £ r3 < r2.
Uwaga: NWD(r1,r2) = NWD(r2, r3).
..........
Krok j. rj-2 = kj rj-1 + rj gdzie 0 £ rj < rj-1.
Uwaga: NWD(rj-2,rj-1) = NWD(rj-1, rj).
Dla pewnego j0, po j0 krokach musimy mieć rj0 = 0 tj. rj0-2 = kj0 rj0-1 + 0.
Cofamy się teraz, wykorzystując równości dla kolejnych kroków.
r j0-1 = NWD(rj0-2,rj0-1) = NWD(rj0-3,rj0-2) =... = NWD(r1,r2) = NWD(n,r1) = NWD(m, n).
rj0-1 = NWD(m, n) = a1 m + a2n, dla pewnych liczb całkowitych a1, a2.
Przykład 1
Stosując algorytm Euklidesa, znaleźć NWD(13013, 390).
Procedurę szukania największego wspólnego podzielnika stosujemy dla liczb m =13013, n = 390.
13013= 390× 33+ 143, (k1 = 33, r1 = 143)
390 = 143× 2 + 104
143 =104 × 1 + 39
104 = 39 × 2 + 26
39 = 26 × 1 + 13
26 = 13 × 2 + 0
NWD(13013, 390) = 13.
Przykład 2
Znaleźć NWD(17986, 595).
17986 = 30 ×
5 95 + 136
595 = 4 ×
136 + 51
136 = 2 ×
51 + 34
51 = 1 ×
34 + 17
34 = 2 ×
17 + 0
NWD(17986, 595)=17.
Pytanie kontrolne 3: Znajdź największy wspólny dzielnik liczb 346823 i 241.
następny punkt » |