3582320318

Wykład 1-3 2,9,16 września 2012

1 Arytmetyka liczb całkowitych

Poniżej przypomnimy niektóre definicje i własności liczb całkowitych, które potrzebne nam będą w dalszym ciągu wykładu. Później zobaczymy, że twierdzenia, które podamy i udowodnimy w tym krótkim wprowadzeniu są bardzo szczególnymi przypadkami twierdzeń znacznie bardziej ogólnych. Niemniej warto już teraz o nich powiedzieć ponieważ będą nam bardzo szybko potrzebne oraz dlatego, że łatwiej będzie później dowody twierdzeń dotyczących struktur abstrakcyjnych zrozumieć.

2 Liczby pierwsze

Liczbami pierwszymi nazywamy liczby naturalne¹, których nie da się przedstawić w postaci iloczynu co najmniej dwóch liczb naturalnych różnych od 0 i 1. Czasami liczby te oznacza się przez P = {2,3,5,7,...}. Znane były od starożytności. Dzięki swoim bardzo praktycznym zastosowaniom w teorii szyfrowania stanowią bardzo atrakcyjny przedmiot badań. Liczby naturalne, które można przedstawić jako iloczyn co najmniej dwóch liczb naturalnych (różnych od 0 i 1) nazywamy liczbami złożonymi

Szczególnie ważny dla nas jest podany przez Euklidesa znany fakt, że zbiór liczb pierwszych jest nieskończony.

Rzeczywiście, przypuśćmy, że P = (pi,P2,-■•,?>«}• Oznaczałoby to, że każda liczba naturalna różna od 0 i 1 jest podzielna przez jedną z co najmniej liczb Pi,P2, "‘iPn- Zdefiniujmy liczbę

a = PlP2 • ... • Pn + 1

a jest liczbą naturalną większą od każdej z liczb Pi,P2i—iPni która nie jest podzielna przez żadną z nich, bowiem reszta z dzielenia a przez pi jest równa 1. Udowodniliśmy w ten sposób fakt znany już Euklidesowi.

1

1

Za znane przyjmujemy zbiory liczbowe i ich oznaczenia. Warto •uczynić jednak wyjątek dla zbioru liczb naturalnych. N, poniewaą bywa on definiowany w różnych książkach rozmaicie. Tu przez liczby naturalne rozumieć będziemy liczby całkowite nieujemne, a więc. N = {0,1,2,3,...}.