Ik zou graag willen reageren op het eerste gedeelte. Ik begrijp dat je op zoek moet gaan naar a en b, zodat a·b=17k+1, maar bestaat er ook oplossingsmethode voor? Want de multiplicatieve inverse van 21 in Z 900, 55 in Z89 en 32 in Z 81 kun je niet zo maar een, twe drie vinden...althans het lukt mij niet. Als het getal geen m.i. heeft, kun je dat dan ook zien? B.v.d. Iris
iris
Student hbo - maandag 13 maart 2006
Antwoord
Deze stelling komt dan handig van pas: ax+by=1 heeft een gehele oplossing (x,y) als a en b onderling ondeelbaar zijn. Hoe bepaal je x en y? Wel, dat gaat met het Euclidisch algoritme: onderweg bereken je dan de ggd van a en b, dus dat moet dan wel op 1 uitkomen als je een invers wil. In je eerste voorbeeld is 3 een gemeenschappelijke deler van 21 en 900, dus heeft 21 geen invers in Z900. Dat is ook logisch: a·21-900·k is altijd een drievoud, dus kan nooit 1 zijn.
Laten we eens naar het laatste voorbeeld kijken: we hebben de getallen 81 en 32. 81 = 2·32 + 17 dus 32 en 17 32 = 1·17 + 15 dus 17 en 15 17 = 1·15 + 2 dus 15 en 2 15 = 7·2 + 1 dus 2 en 1. Dit laatste getal (1) is de ggd van 81 en 32.
Nu gaan we proberen de 1 te schrijven als combinatie van 32 en 81. De laatste regel hierboven geeft 1 als combinatie van 2 en 15. Die 2 kunnen we met de voorlaatste regel dan weer schrijven als combinatie van 15 en 17, die 15 kunnen we schrijven als combinatie van 17 en 32 met behulp van de regel daarboven, etc. Zo dus:
Dit is een reactie op vraag 23161 
