Elementarna teoria liczb/Elementy podzielności liczb

Elementy podzielności liczb

Podzielność jest bardzo ważnym pojęciem w teorii liczb. Mówimy, że liczba całkowita a jest podzielna przez liczbę całkowitą b, jeśli istnieje liczba całkowita c taka, że a = b * c.

Na przykład: liczba 123456 jest podzielna przez 643, ponieważ istnieje liczba całkowita, czyli 192. Tak więc $123456=643\cdot 192\,$.

Podzielność zaznaczamy pionową kreską: a | b oznacza "a dzieli b". Na przykład możemy napisać $643|123456\,$

Liczby pierwsze

Liczbą pierwszą nazywamy liczbę naturalną, która ma dokładnie dwa dzielniki: jedynkę i samą siebie. Jedenaście pierwszych takich liczb to: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 i 31. Istnieje nieskończenie wiele liczb pierwszych o czym przekonamy się udowadniając poniższe twierdzenia. Powszechnie liczba 1 nie jest uważana za liczbę pierwszą chociaż nie posiada innych dzielników niż siebie. Przyczyny tego będą omówione później.

Twierdzenie 1

Załóżmy, że $a,b,d,r,\,$ i $s\,$ są liczbami całkowitymi i $d|a,d|b\,$. Wtedy $d|(ra+sb)\,$.

Dowód
Istnieje $e\,$ i $f\,$ taki, że $a=de\,$ i $b=df\,$. Dlatego:

$ra+sb=rde+sdf=d(re+sf).\,$

Wiemy, że $re+sf\,$ jest także liczbą całkowitą, stąd $d|(ra+sb)\,$.

Wniosek
Załóżmy, że $a,b,d\,$ i $r\,$ są liczbami całkowitymi i $d|a,d|b\,$. Wtedy $d|(a+b),d|(a-b),\,$ i $d|ra\,$.

Twierdzenie 2

Jeśli $a,b,c\,$ są liczbami całkowitymi i $a|b,b|c\,$ wtedy $a|c\,$.

Dowód
Zapiszmy b jako $b=ad\,$ i c jako $c=be\,$ dla kilku liczb całkowitych $d\,$ i $e\,$.

Wynika z tego, że:
$c=ade=a\left(de\right)\,$, więc $a|c\,$.

Twierdzenie 3

Jeśli $a,b,c\,$ są liczbami całkowitymi i $c\neq 0$, a następnie $a|b\,$ wtedy i tylko wtedy, gdy $ac|bc\,$
Dowód:

$a|b\,$ implikuje istnienie takiej liczby całkowitej d, która

$b=ad\,$

Więc wynika z tego, że

$bc=\left(ac\right)d$ i stąd $ac|bc\,$.

Z drugiej strony możemy założyć, że mamy taką liczbę n, że $n\in \mathbb {Z}$ i $an=b$, stąd:

$n={b \over a}={b \over a}*{c \over c}$,

stąd: ${bc \over ac}\in \mathbb {Z}$, więc $ac|bc\,$

Twierdzenie udowodnione.

Twierdzenie 4

Podstawowe twierdzenie arytmetyki
Każdą liczbę całkowitą dodatnią można jednoznacznie przedstawić w postaci iloczynu liczb pierwszych.

Dowód:
Twierdzenie udowodnimy za pomocą dowodu nie wprost.

Niech N będzie najmniejszą dodatnią liczbą całkowitą, że nie jest iloczynem liczb pierwszych. Ponieważ N musi liczbą złożoną to możemy zapisać jako N = a b gdzie a, b > 1. To jest

$1<a,b<N$.

Wykazaliśmy, że twierdzenie jest prawdziwe dla a i b ponieważ N było kontrprzykładem. Stąd są to liczby $p_{1},p_{2},\dots ,p_{k}$ takie, że

$a=p_{1}p_{2}\cdots p_{k}$

i liczby $q_{1},q_{2},\dots ,q_{l}$ takie, że

$b=q_{1}q_{2}\cdots q_{l}$.

Stąd

$N=ab=p_{1}p_{2}\cdots p_{k}q_{1}q_{2}\cdots q_{l}$,

co jest sprzecznością.

Inny sposób udowodnienia twierdzenia

Za pomocą indukcji matematycznej.

Twierdzenie jest prawdziwe dla N = 2.

Załóżmy, że twierdzenie jest prawdziwe dla wszystkich $k\leq N$

N + 1 jest albo liczbą pierwszą, albo złożoną. If N + 1 jest liczbą pierwszą, wtedy twierdzenie jest prawdziwe dla $k=N+1$

Jeśli N + 1 jest liczbą złożoną, wtedy N + 1 jest podzielne przez pewną liczbę pierwszą $p<N+1$, więc $k=N+1$ możemy zapisać jako iloczyn $p$ i pewnych liczb $<N+1$.

Stąd, N + 1 możemy zapisać jako iloczyn liczb pierwszych.

Wynika z tego, że twierdzenie jest prawdziwe dla wszystkich $k\leq N+1$ i przez indukcję matematyczną dla wszystkich liczb $\mathbb {N}$.

Twierdzenie 5

Istnieje nieskończenie wiele liczb pierwszych.

Dowód:

Załóżmy, że istnieje tylko $k\,$ liczb pierwszych.

Oznaczmy te liczby pierwsze jako: $p_{1},p_{2},...,p_{k}\,$.

Niech $n=p_{1}p_{2}...p_{k}+1.\,$. Wtedy, albo n jest liczbą pierwszą, albo iloczynem liczb pierwszych. Jeśli jest iloczynem liczb pierwszych to musi być podzielna przez liczbę pierwszą $p_{i}$ dla niektórych $i$. Jednakże, ${\frac {n}{p_{i}}}={\frac {p_{1}p_{2}...p_{k}+1}{p_{i}}}=p_{1}p_{2}...p_{i-1}p_{i+1}...p_{k}+{\frac {1}{p_{i}}}$ co oczywiście nie jest liczbą całkowitą: $n$ nie jest podzielna przez $p_{i}$.

Stąd, $n\,$ nie jest iloczynem liczb pierwszych.

Jest to sprzecznością, jako w twierdzeniu 4 wszystkie liczby mogą być wyrażone jako iloczyn liczb pierwszych.

Dlatego, albo $n\,$ jest liczbą pierwszą, albo jest podzielna przez pewną liczbą pierwszą większa od $p_{k}\,$.

Wywnioskowaliśmy, że założenie, że istnieje tylko $k\,$ liczb pierwszych jest fałszywe.

W ten sposób udowodniliśmy, że istnieje nieskończenie wiele liczb pierwszych.

Twierdzenie 6

Dzielenie z najmniejszą nieujemną resztą

Niech a i b będą liczbami całkowitymi, gdzie $b>0$. Wtedy będą istnieć liczby całkowite q i r takie, że

$a=bq+r$

i $0\leq r<b$.

Dowód:

Określmy zbiór

$M=\{x\in \mathbb {Z} \mid x\leq {\frac {a}{b}}\}$

który jest niepusty i ograniczony z góry.Stąd maksymalny elementy oznaczyliśmy przez q.

Przekształćmy: $r=a-bq$. Jest to $r=a-bq\geq a-b{\frac {a}{b}}=a-a=0$ i $r<b$, ponieważ inaczej

$b\leq r=a-bq$.

Oznacza to

$q+1\leq {\frac {a}{b}}$

co jest sprzeczne z maksymalnym q w zbiorze M.

Udowodnimy teraz unikalność q i r:

Niech $q'$ i $r'$ będą dwoma liczbami całkowitymi, które spełniają $a=bq'+r'$ i $0\leq r'<b$. Jest to

$|b(q-q')|=|r'-r|<b$

dlatego $|q-q'|<1$ który oznacza $q=q'$. To również pokazuje $r=r'$.