Tag archieven: ggd

Les 1: ax+by=c

Geplaatst op door

Aan de hand van enkele voorbeelden bespreken we Diophantische vergelijkingen: dit zijn vergelijkingen met gehele coëfficiënten waarvan gehele oplossingen gevraagd worden.

We starten in les 1 met de basisvergelijking ax+by=c met a,b,c :in \mathbb{Z}. Neem bijvoorbeeld 7x+13y=81.

  • Omdat de grootste gemene deler van 7 en 13 gelijk is aan 1 en dit een deler is van 81, heeft deze vergelijking oplossingen.
  • Volgens de stelling van Bezout kunnen we deze grootste gemene deler schrijven als een lineaire combinatie van 7 en 13. Dat kan door het recursief gebruiken van het algoritme van Euclides voor het bepalen van de grootste gemene deler.
  • Zo is  7.2+13.(-1)=1 en dus is 7.162+13.(-81)=81 . Bijgevolg is (162,-81) een particuliere oplossing van de gegeven vergelijking.
  • Als we nu de twee vergelijkingen 7.162+13.(-81)=81 en 7x+13y=81 van elkaar aftrekken vinden we 7(162-x)=13(81+y). Bijgevolg is 7 een deler van 81+y en 13 een deler van 162-x.
  • Er bestaat dus een geheel getal t zodat

        \[\frac{162-x}{13}=\frac{81+t}{7}=t\]

    en dus is x=162-13t en y=-81+7t. Alle gehele oplossingen van de gegeven vergelijking zijn van deze vorm.

GGD en KGV

Geplaatst op door

Gegeven zijn 2 natuurlijke getallen a en b. Het grootste natuurlijk getal dat zowel een deler is van a als van b heet de grootste gemene deler van a en b. Notatie : ggd[a,b). Het kleinste getal dat zowel een veelvoud is van a als van b , heet het kleinste gemene veelvoud van a en b. Notatie : kgv(a,b).

Men kan de grootste gemene deler en het kleinste gemene veelvoud van 2 getallen bepalen door beide getallen te ontbinden in priemfactoren. Vooral bij grotere getallen kan dit een omvangrijk werk zijn. Er is een veel snellere methode. Deze berust op de eigenschap dat als b=q.a+r , dan geldt er dat ggd (a,b) = ggd(a,r). Elke deler van a en b is immers ook een deler van r=b-q.a en omgekeerd elke deler van a en r is ook een deler van b. Deze werkwijze noemt men het algoritme van Euclides.

We berekenen  de ggd van 1970 en 1066 op twee manieren:

  1.  1970 = 2.5.197 en 1066 = 2.13.41, dus is ggd(1970,1066)=2
  2. 1970 = 1.1066 + 904 ; 1066=1.904+162 ; 904=5.162+94 ; 162=1.94+68 ; 94=1.68+26 ; 68=2.26+16 ; 26=1.16+10 ; 16=1.10+6 ; 10=1.6+4 ; 6=1.4+2 ; 4=2.2. Dus is ggd(1970,1066)=ggd(1066,904)=ggd(904,162)=ggd(162,94)=ggd(94,68) = ggd(68,26)=ggd(26,16)=ggd(16,10)=ggd(10,6)=ggd(6,4)=ggd(4,2)=2

Via dit algoritme kan men ( zoals hieronder in  de stelling van Bezout vermeld wordt) de grootste gemene deler van 2 getallen schrijven als een lineaire combinatie van die twee getallen.
ggd(1970,1066)= 2= 6 – 4 = 6 – (10 – 6) = 2.6 – 10 = 2.(16 – 10) – 10 = 2.16 – 3.10 = \ldots = 377.1066 – 204.1970.

Enkele eigenschappen

  • Elke gemeenschappelijke deler van a en b is ook een deler van ggd(a,b)
  •  Elk gemeenschappelijk veelvoud van a en b is ook een veelvoud van kgv(a,b).
  •  ggd(a,b).kgv(a,b)=a.b
  • Als n een deler is van a.b en als ggd(n,a) = 1 dan moet n een deler zijn van b.
  • Als ggd(a,b)=d dan geldt : ggd(\frac{a}{d},\frac{b}{d})=1
  • ggd(a,b) = ggd(b,a – qb)
  • De grootste gemene deler van 2 getallen is een lineaire combinatie van die twee getallen ( stelling van Bezout ).