2024-10-10

Talteori

Delbarhet

Euklides algoritm

Se även: 2024-10-09#Euklides algoritm

Sats 5.18 (Bézout's identitet)

Låt $a, b \in Z_{+}$ . Det finns $m, n \in Z$ så att

s g d (a, b) = m a + n b

OBS: $m$ och $n$ är ej bägge positiva.
Ej heller entydigt.

Euklides baklänges

Tip

Euklides algoritm kan även köras baklänges från näst sista raden:

r_{n - 2} = r_{n - 1} q_{n} + r_{n} ⟺ r_{n} = r_{n - 2} - q_{n} r_{n - 1}

På så sätt fär vi ut $r_{n} = a m + b k$ där $m, k \in Z$

Exempel

Det här är Exempel 3 från förra föreläsningen baklänges

$r_{n} = r_{n - 2} - r_{n - 1} q_{n} ⟺ 12 = 60 - 2 \cdot 24$
$= 60 - 2 (204 - 60 \cdot 3)$
$= 60 - 2 \cdot 204 + 6 \cdot 60$
$= 7 \cdot 60 - 2 \cdot 204$
$= 7 \cdot (876 - 4 \cdot 204) - 2 \cdot 204$
$= 7 \cdot 876 - 28 \cdot 204 - 2 \cdot 204$
$= 7 \cdot 876 - 30 \cdot 204$

$Svar: {\begin{cases} m = 7 \\ k = - 30 \end{cases}$

Relativt prima

Två heltal $a, b \in Z$ sådana att $s g d (a, b) = 1$ kallas relativt prima.

Diofantiska ekvationer

Ekvationer med heltalskoefficienter där vi söker heltalslösningar.

Ex: $x^{n} + y^{n} = z^{n}, n \in Z_{+}, x, y, z \in Z$

Linjära ekvationer

I den här kursen kommer vi enbart lösa linjära ekvationer i två variabler:

Givet $a, b, c \in Z$ , hitta $x, y \in Z$ i den allmänna ekvationen:

a x + b y = c

När finns det lösningar i den allmänna ekvationen?

Vi benämner den allmänna ekvationen ovan (**)

Från Bézout's identitet: om $c = s g d (a, b)$ , finns $x, y$ så att:

a x + b y = s g d (a, b)

Antag nu att $d = s g d (a, b)$ och $d ∣ c$ i ekvationen (**)
$⟹ \exists s \in Z : c = s \cdot d$

Ekvationen kan skrivas som $a x + b y = d s$

Vi vet att det finns $m, n \in Z$ så att $a m + b n = d$ från Bézout's identitet. Vi multiplicerar med $s$ :
$a m s + b n s = d s$
$⟹ en lösning till (**) ges av (x, y) = (s m, s n)$
$⟹ (**) är lösbar om d = s g d (a, b) är sådan att d ∣ c$

Antag att det finns en lösning $(x, y)$ till (**).

Måste gälla att $d ∣ c$ , $d ∣ a$ , $d ∣ b$
$⟹ d ∣ a x, d ∣ b y$
$⟹ d ∣ (a x + b y)$

Sats 5.22

Den diofantiska ekvationen $a x + b y = c$ är lösbar om och endast om $s g d (a, b) ∣ c$

Lös diofantiska ekvationer

Givet att $s g d (a, b) ∣ c$ , hur hittar vi $(x, y)$ som löser (**)?

Sätt $d = s g d (a, b)$ , definiera $r = \frac{c}{d}$
Från Bézout's: $\exists m, n \in Z$ så att $a m + b n = d$

Multiplicerar med $r$ :

$a r m + b r n = d r = d \cdot \frac{c}{d} = c$
$⟹ (x, y) = (r m, r n)$ är en lösning

Kan hitta $d, m, n$ från #Euklides algoritm.

Exempel

Hitta en lösning till $3 x + 7 y = 2$

$s g d (3, 7) = 1$ (Euklides algoritm)
$1 ∣ 2 ⟹ det finns en lösning$

#Euklides baklänges ger oss:

$1 = 7 - 2 \cdot 3, m = - 2, n = 1$

Multiplicera med $r = \frac{c}{d} = \frac{2}{1} = 2$ :

$(x, y) = (r m, r n) = (2 m, 2 n) = (- 4, 2)$ är en lösning

Allmänna lösningen

Sats 5.25

Om $s g d (a, b) = 1$ och $r, \sin n \in Z$ är sådanna att:

a r + b s = c

Då gäller att mängden av alla lösningar till (**) ges av:

{(x, y) = (r - b m, s + a m), m \in Z}

Alternativ formulering:
Den diofantiska ekvationen (**) har den allmänna lösningen

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

Där $u, v$ är sådanna att $a u + b v = 1$ .