2024-10-14

Talteori

Diofantiska ekvationer

Från: Sats 5.25

Om $s g d (a, b) = 1$ har den diofantiska ekvationen

a x + b y = c

Den allmänna lösningen kan skrivas som:

(x, y) = (c u - b n, c v + a n), n \in Z

där $u, v \in Z$ är sådanna att $a u + b v = 1$

Exempel

Lös $45 x + 21 y = 72$

$s g d (45, 21) = 3$

Finns lösningar? $3 ∣ 72 ⟹$ Ja

Förkorta med 3:

15 x + 7 y = 24

$s g d (15, 7) = 1 ⟹ använd satsen ovan$
Betrakta $15 x + 7 y = 1$

En lösning: $x = 1, y = 2 : 15 \cdot 1 + 7 \cdot (- 2) = 15 - 14 = 1$

Enligt satsen: Allmänna lösningen till (**) ges av:

(x, y) = (24 \cdot 1 - 7 n, 24 \cdot (- 2) + 15 n), n \in Z

Vilket ger oss lösningen:

(x, y) = (24 - 7 n, - 48 + 15 n), n \in Z

Primtal

Ett heltal $p \geq 2$ kallas ett primtal om

\forall a \in Z_{+} : a ∣ p ⟹ (a = 1 \lor a = p)

Ett heltal $n$ som ej är ett primtal kallas ett sammansatt tal.

Sats 5.28

$a, b \in Z$ så att $s g d (a, b) = 1$ .
Tag $c \in Z$ . Då gäller $a ∣ b c ⟹ a ∣ c$ .

Bevis:
$s g d (a, b) = 1 ⟹ \exists x, y \in Z$ så att

a x + b y = 1

Multiplicera med $c$ :

a c x + b c y = c

Gäller att $a ∣ a c x$ . Eftersom $a ∣ b c$ gäller $a ∣ b c y$ .

⟹ a ∣ (a c x + b c y), d.v.s. a ∣ c

Sats 5.30

Tag $p$ primtal, $a, b \in Z$ .

Om $p ∣ a b$ gäller $p ∣ a$ eller $p ∣ b$ .

Bevis:
Det måste gälla att $p ∣ a$ eller $p ∤ a$ .
Om $p ∣ a$ : inget mer att visa.
Antag därför $p ∤ a$ .
$p ∤ a, p är ett primtal ⟹ s g d (a, p) = 1$

Sats 5.28 $⟹ p ∣ b$

Sats 5.31

Om $p$ ett primtal och $a_{1}, a_{2}, \dots, a_{n} \in Z$
är sådanna att $p ∣ \prod_{i = 1}^{n} a_{i}$
då gäller att $p ∣ a_{k}$ för minst ett index $k \in [1, n]$

Sats 5.33 (Arkimedes fundamentalsats)

Varje $z \in Z_{+}, z > 1$ , kan skrivas som en produkt av primtal, faktoriseringen är unik upp till ordningen av faktorerna.

Kongruensräkning

Börjar med en fråga: *Om idag (14/10) är en måndag, vilken veckodag är det om:

4 dagar? — Fredag — $4 = 7 \cdot 0 + 4$
12 dagar? — Lördag — $12 = 7 \cdot 1 + 5$
108 dagar? — Torsdag — $108 = 7 \cdot 15 + 3$

Tricket är att veckodagarna är i cykler av 7 dagar.

Det vi gör är resträkning modulo 7 eller kongruensräkning modulo 7.

Definition

Betrakta alla heltal $a$ med samma rest vid division med $n \in Z_{+}$ som "lika".

Formellt:
Låt $n \in Z_{+}$ : Vi definierar en relation " $\equiv$ modulo $n$ " (kongruens modulo $n$ ) genom att säga $a \equiv b mod n$ om $n ∣ a - b$ .

Notation

$a \equiv b mod n$

eller

$a \equiv b (n)$

Egenskaper

Sats

Kongruens modulo $n$ är en ekvivalensrelation på $Z$ .

Reflexiv

$a \equiv a mod n ⟺ n ∣ a - a ⟺ n ∣ 0$ Sant för alla $n$

Symmetrisk

Tag $a, b \in Z$

a \equiv b mod n ⟺ n ∣ a - b ⟺ n ∣ - (a - b) ⟺ n ∣ b - a ⟺ b \equiv a mod n

V.S.V.

Transitiv

Tag $a, b, c \in Z$

$a \equiv b mod n \land b \equiv c mod n$
$⟹ n ∣ a - b, n ∣ b - c$
$⟺ n ∣ (a - b) + (b - c)$ d.v.s. $n ∣ a - c$ V.S.V.

Ekvivalensklasser

För $a \in Z, b \in Z_{+}$ finns unika $q, r$ så att

a = q b + r, 0 \leq r \leq b - 1

varje heltal $a$ är kongruent med $b$ med en unik rest $r$ .

Välj $b$ som $n$ :

$a = q n + r, 0 \leq r \leq n - 1$
$⟹$ ekvivalensklasserna för " $\equiv mod n$ " ges av $[0], [1], \dots, [n - 1]$ där $[0]$ är representerar heltal $k$ sådana att $k = l \cdot n$ , för något $l \in Z$ .

Exempelvis är $[1]$ alla heltal $k$ så att $k = l \cdot n + 1$ för något $l \in Z$ .

Operationer på kongruens

Sats 5.38

Välj $n \in Z_{+}$

Antag att $a \equiv c mod n$ , $b \equiv d mod n$

Då gäller:

$a + b \equiv c + d mod n$
$a - b \equiv c - d mod n$
$a \cdot b \equiv c \cdot d mod n$

Operationer på ekvivalensklasser

$[a] + [b] = [a + b]$
$[a] - [b] = [a - b]$
$[a] \cdot [b] = [a \cdot b]$

Exempel

$[1] = {0, 1, 2, \dots}$
$[2] = {0, 2, 4, \dots}$

$[1] + [1] = {0 + 0, 1 + 1, 2 + 2, \dots} = {0, 2, 4, \dots} = [2]$