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\ne 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=\frac{b}{a}=\frac{b}{a}\ast \frac{c}{c}$,

stąd: $\frac{bc}{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\le 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\le 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,\mathrm{...},p_k$.

Niech $n=p_1{p}_2\mathrm{...}{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\mathrm{...}{p}_k+1}{p_i}=p_1{p}_2\mathrm{...}{p}_{i-1}{p}_{i+1}\mathrm{...}{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\le r<b$.

Dowód:

Określmy zbiór

$M=\{x\in \mathbb{Z}\mid x\le \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\ge a-b\frac{a}{b}=a-a=0$ i $r<b$, ponieważ inaczej

$b\le r=a-bq$.

Oznacza to

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

co jest sprzeczne z maksymalnym q w zbiorze M.

Udowodnimy teraz unikalność q i r:

Niech $q^{\prime }$ i $r^{\prime }$ będą dwoma liczbami całkowitymi, które spełniają $a=b{q}^{\prime }+r^{\prime }$ i $0\le r^{\prime }<b$. Jest to

$|b(q-q^{\prime })|=|r^{\prime }-r|<b$

dlatego $|q-q^{\prime }|<1$ który oznacza $q=q^{\prime }$. To również pokazuje $r=r^{\prime }$.