[Wi]Vergelijking waar ik niet uitkom..

[BrightEyes]

13*d=1(mod 112)
oftewel:
13*d=1+k*112
oftewel:
1=d*13-k*112

2 onbekenden dus, de d is het belangrijkste, die moeten we weten. Het moeten overigens beide wel hele getallen zijn.

BrightEyes schreef op 15-03-2005 @ 13:01 :
13*d=1(mod 112)
oftewel:
13*d=1+k*112
oftewel:
1=d*13-k*112

2 onbekenden dus, de d is het belangrijkste, die moeten we weten. Het moeten overigens beide wel hele getallen zijn.

1 onbekende, want die k is elke willekeurige integer.

[BrightEyes]

Hoe kun je die d dan berekenen?

BrightEyes schreef op 15-03-2005 @ 13:01 :
13*d=1(mod 112)
oftewel:
13*d=1+k*112
oftewel:
1=d*13-k*112

13d = 1 + k*112
d = 1/13 + k*112/13
d = 1/13 (mod 112/13)
(dus bijvoorbeeld d = 1/13, d = 113/13, d = 225/13 etc. zijn allemaal goede oplossingen)

[IvdSangen]

Hier is het algoritme van Euclides ook zeer geschikt voor als je met gehele getallen werkt.

Edit: Ik zie net dat het gehele getallen betreft. Uitwerking van het algoritme van Euclides:

13*d=1(mod 112)

We zoeken dus een x en een y, zodat x*13 + y*112=1

We zoeken stap voor stap de ggd van 13 en 112 (die 1 is) en terwijl we dat doen houden we een administratie bij waar we de laatst verkregen waarde schrijven als x*13 + y*112.

112 = 1*112
13 = 1*13
8 = 1*112 - 8*13 (112 - 8*13)
5 = -1*112 + 9*13 (13 - 8)
3 = 2*112 - 17*13 (8 - 5)
2 = -3*112 + 26*13 (5 - 3)
1 = 5*112 - 43*13 (3 - 2)

Je inverse (de d dus) is dus 43 als het goed is.