WisFaq!

Klokrekenen

A.X=1 voor elke A is niet 0 geldt voor priemklokken. Bij andere klokken is dat niet zo. Lever bwijs.

Rick
22-4-2002

Antwoord

Hoe het bewijs precies gaat mag je zelf bedenken, maar volgens mij zou het iets moeten zijn als:
Voor elke A¹0 is er een X, zodat A·X=1 (modulo P). Dit betekent dat X de inverse is van A bij vermeniguldigen modulo P. Als P geen priem is, dan is de functie f(n)=A·n (modulo P) geen 1 op 1 functie... (d.w.z. het is aan te tonen dat als b.v. X·n=8 (modulo P) deze vergelijking meerdere oplossingen heeft als GGD(X,P)¹1). En een functie die niet 1 op 1 is heeft (uiteraard) geen inverse.
Zie Klokrekenen voor een voorbeeld bij P=12.
Je ziet daar dat a·8 (modulo 12) geen eenduidige oplossing heeft... a kan 1, 4, 7 of 10 zijn... waarom? Omdat ggd(8,12)=4 en geen 1.

WvR
27-4-2002