WisFaq!

Ggd gedeeltelijk bekend

ggd(a,b)=a·s+b·t

Dit is bekend: ggd(33220,b)=20
en ook dat: 33220·1+b·t

Ik dacht dat dit met de uitgebreide ggd wel op te lossen zou zijn, maar dat lukt ook niet. IS hier wel een methode voor? Behalve dan natuurlijk k·(20....1660) gaan proberen?

David

david
24-1-2005

Antwoord

33220=20·11·151 oftewel 33220 en 20 zijn niet copriem.
Dat uitgebreide ggd algoritme werkt alleen als ggd(..,..)=1.
Conclusie: voor alle b=k·20 geldt ggd(33220,b)=20.

hk
24-1-2005