WisFaq!

Getaltheorie

Beste

ik heb volgende twee opgaven:
a) 3124x + 151y = 14 en b) 204x+51y=6
opgave: bepaal telkens twee gehele getallen x en y, of leg uit waarom dit niet mogelijk is.

voor a) heb ik al de ggd bepaald en dat is 1 via het algoritme van Euclides. Het zou nu moeten mogelijk zijn om via dit algoritme de coëfficiënten te vinden en deze dan met 14 te vermenigvuldigen en zo moet ik tot een oplossing komen van x = -26 en y=538
maar hiertoe kom ik niet kan u mij helpen?

Alvast bedankt

Thomas
29-8-2014

Antwoord

Je moet blijven boekhouden als je het algoritme toepast:

 
3124 = 20 * 151 + 104    dus  104 = 1*3124 - 20*151 
151 = 1*104 + 47         dus   47 = 151 - 104 = 21 * 151 - 1*3124 
104 = 2*47 + 10          dus   10 = 104 -2*47 = ... 

als je zo voortgaat vind je
$$
1= 931\times151-45\times3124
$$

kphart
29-8-2014