Hvis A .subset setZ^{+}, eksisterer et m i A så m .le a, .forall a .isin A. m kaldes for minimum i A.
Hvis a, b .isin setZ, a .ne 0, siger vi at a er en divisor i b hvis der eksisterer et tal k i ℤ så ak = b, og vi skriver a | b. Omvendt, hvis a ikke er divisor i b, skriver vi a ∤ b
Hvis a, b .isin setZ .setminus {0}, findes et entydigt bestemt positivt heltalt, d, kaldet den største fælles divisor, så:
d .divides a .and d .divides b - d er fælles divisor.
e .divides a .and e .divides b .drarrow e .divides d - d er den størte fælles divisor.
Den største fælles divisor noteres d = (a,b). Hvis (a,b) = 1, siger vi at a og b er indbyrdes primiske.
Hvis a, b .isin setZ .setminus {0}, findes et entydigt bestemt heltal, l, kaldet det mindste fælles multiplum, så
a .divides l .and b .divides l - l er et multiplum af både a og b.
a .divides m .and b .divides m .drarrow l .divides m - l er det mindste multiplum af både a og b.
Forbindelsen mellem den største fælles divisor, d, og det mindste fælles multiplum, l, er givet ved dl = ab.
(Divisionsalgoritmen) Hvis a, b .isin setZ, b .ne 0, eksisterer entydigt bestemte q, r .isin setZ så a = qb + r, 0 .le r .lt |b|, hvor q er kvotionten og r er rest.
Til at regne den største fælles divisor mellem to tal kan vi benytte Euklids algoritme. Den fungerer ved at man fræser divisionsalgoritmen igennem igen og igen indtil resten r er 0. Sådan her:
Hvor r_n er den mindste rest forskellig fra 0. Sådanne r eksisterer da |b| .gt |r_0| .gt |r_1| .gt ... .gt |r_n| er en serie af positive heltal, og resten r_{n + 1} = 0.
Jeg har lavet algoritmen, den kan prøves her:
En direkte konsekvens af Euklids Algoritme er, at hvis a, b .isin setZ .setminus {0}, eksisterer x, y .isin setZ så (a,b) = ax + by hvor x og y findes ved at regne baglæns i Euklids algoritme. Hvis feks. a = 12398 og b = 126, indsætter vi og trykker baglæns og får:
Prop. 1 del 2
Et heltal p kaldes et primtal hvis p > 1, og hvis den eneste positive divisor i p er 1.
En egenskab ved primtal, p, er: p .divides ab .drarrow p .divides a .or p .divides b
Aritmetikkens fundamentalsætning: Hvis n .isin, setZ n .gt 1, kan n på entydig vis skrives som et produkt af primtal, altså for p, k .isin setZ, k .ne 1 .drarrow k .ndivides p, %alpha .isin setN kan vi skrive
Denne faktorisering er unik hvilket betyder, at hvis vi også har:
er t = n, og hvis faktoriseringen sættes i orden efter største først, mindste sidst, er qi = pi og αi = βi
Lad nu a og b være en primtalsfaktorisering af to heltal. Da er (a,b) lig med produktet af de primtal a og b har tilfælles, hvor vi tager den mindste eksponent for hver faktor hvor vi tillader en eksponent at være 0 (for faktorer de ikke har tilfælles). Feks er:
På samme måde, bare omvendt, er det største fælles multiplum lig med produktet af de fælles primtal, men med den største eksponent:
Hvis to tal, a og b, er heltal og ikke har en eneste fælles primfaktor, siger vi at de er indbyrdes primiske og skriver (a,b) = 1, feks: a = 2 .sdot 3^2 = 18, b = 7 .sdot 5 = 35.
Eulers φ-funktion : Lad n .isin setZ^{+}, og lad φ(n) være antallet af positive heltal a ≤ n der er indbyrdes primiske med n. Feks. for n = 12 er 1, 5, 7, 11 indbyrdes primiske samt mindre end eller lig med 12. Så φ(12) = 4. 1, 2 opfylder φ for n = 3, så φ(3) = 2 osv.
For primtal, p, gælder φ(p) = p - 1, og generelt for a ≥ 1 gælder:
Funktionen er multiplikativ forstået på den måde at:
og på den måde kan formlen generaliseres til et hvilket som helt helt tal n, , feks:
som så er antallet af tal, a ≤ 202, for hvilke (a,202) = 1.