Page 89 - Echte wiskunde

Echte Wiskunde 77
2.13 Allereenvoudigste getaltheorie
Getaltheorie houdt zich bezig met eigenschappen van gehele getallen. In deze sectie zullen, ook als het niet uitdrukkelijk wordt gezegd, alle Latijnse letters natuurlijke getallen voorstellen.
a heet deelbaar op b; b deelbaar door a, als ∃c ac = b. Notatie: a | b. bheetondeelbaarals∀a (a|b)⇒a=1∨a=b)]
p heet priemgetal als p ondeelbaar is en p > 1.
De kleinste priemgetallen zijn 2, 3, 5, 7, 11, 13, 17.
We vermelden zonder bewijs:
Eigenschap: Als p priem en p | ab, dan is p | a of p | b.
Eigenschap: (Hoofdstelling der rekenkunde) Elk natuurlijk getal n is te schrijven als pro- duct van een (eindig) aantal priemfactoren (waaronder gelijke mogen voorkomen). Twee verschil- lende ontbindingen van n in priemfactoren verschillen slechts in de volgorde der factoren.
Grootste gemene deler
Laat a en b natuurlijke getallen zijn. Beschouw de verzameling15 Vab ={ax+by|x∈Z,y∈Z}.
Bewering: De verzameling Vab is precies de verzameling van veelvouden van een getal g ∈ Z. Dit getal noemen we g = ggd(a, b).
Bewijs: Het kleinste positieve getal uit V noemen we g.
We laten eerst zien dat (i) ieder getal uit Vab een veelvoud is van g, ofwel
c ∈ Vab ⇒ g | c .
We kunnen namelijk schrijven c = ax + by, en ook c = gq + r (0 ≤ r < g), en ook g zelf kunnen
we schrijven als ax0 + by0. Nu blijkt dat
r = c − gq = a(x − qx0) + b(y − qy0) ,
dus r ∈ Vab. Als geldt 0 < r < g, dan was g niet het kleinste positieve element van Vab. Dus r = 0, en dus c = qg. (Dat was de eerste helft van het bewijs.)
Nu moeten we nog laten zien dat (ii) elk veelvoud van g in Vab ligt, ofwel
kg = k(ax0 +by0) = a(kx0)+b(ky0) ∈ Vab .
Dit bewijst de bewering.
Het is logisch om g de grootste gemene deler te noemen want (i) g | a en g | b. Dat komt omdat ook a en b in Vab liggen (kies x = 1, y = 0, resp. x = 0, y = 1). Verder (ii) is elke gemeenschappelijke deler van a, en b deelbaar door g:
d|a ∧ d|b ⇒ d|g, eenvoudig16 omdat g de vorm ax + by heeft.
15De verzameling Vab hangt dus af van de keuze van de twee gehele getallen a en b.
16Want enerzijds ∃α∈N a = αd, anerzijds ∃β∈N b = βd, zodat g = ax0 + by0 = αdx0 + βdy0 = d(αx0 + βy0), dwz d | g.