Tag archieven: lineaire congruentie

Lineaire congruenties

Geplaatst op door

Naast lineaire vergelijkingen , kunnen we ook lineaire congruenties bekijken:

    \[ax \equiv b \text{ mod } m \text{ met } a,b,m\in \mathbb{Z}\]

Hier is de vraag of er een gehele x te vinden is zodat  ax-b deelbaar is door m. Het is duidelijk dat als x_0 een oplossing is, dan zijn alle getallen uit de restklasse x_0 \text{ mod } m ook oplossingen. De oplossingsverzameling verandert ook niet als we a en b veranderen in andere getallen uit hun restklasse mod m. Onder een oplossing van een lineaire congruentie verstaat men dus een restklesse mod m.

  • Wanneer is een congruentie oplosbaar?  Dat is zo als en slechts als de grootste gemene deler van a en m een deler is van b. Als a en m onderling ondeelbaar zijn, bestaat het inverse element van a mod m en is dus x=a^{-1}b \text{ mod } m. Als de grootste gemene deler d van a en m niet 1 is , dan delen we eerst door d en dan krijgen we vorige situatie.
  • In het geval dat ggd(a,m) = 1 hebben we een unieke oplossing. Als echter ggd(a,m) = d , dan hebben we d oplossingen. We krijgen immers 1 oplossing mod \frac{m}{d} en deze geeft precies volgende verschillende restklassen mod m: x_0, x_0+\frac{m}{d},x_0+2\frac{m}{d},\cdots, x_0+(d-1)\frac{m}{d}.

Los op : 6x \equiv 8 \text{ mod }10 .

  • Delen door de ggd(6,10) = 2 geeft 3x \equiv 4 \text{ mod } 5 .
  • Omdat 3.2 = 6 \equiv 1 \text{ mod } 5 is 3^{-1} =2
  • En dus is x\equiv 2.4 \equiv 3 \text{ mod } 5.
  • Alle oplossingen zijn dus de restklassen 3 en 8 modulo 10. De oplossingsverzameling is:

        \[\{3+10k, 8+10l \text{ met } k,l\in \mathbb{Z}\}\]