De vraag "los op: ax = b (mod m)" heeft als antwoord: Zij g=(a,m). Dan zijn er geen oplossingen als g geen deler van b is. En anders zijn er precies m/g restklassen mod m die oplossingen geven.
Definitie van groep, ring, lichaam.
Voorbeelden van een groep: optelgroep van reele getallen, vermenigvuldiggroep van reele getallen, vermenigvuldiggroep van positieve reele getallen, optelgroep van matrices, vermenigvuldiggroep van vierkante matrices met determinant ongelijk 0. Deze laatste groep is niet commutatief.
Restklassen modulo m vormen een groep voor de optelling.
Restklassen a modulo m met (a,m)=1 vormen een groep P_m voor de vermenigvuldiging.
Restklassen modulo m vormen een ring R_m.
Restklassen modulo p met p een priemgetal vormen een lichaam.
Er zijn ook andere eindige lichamen. Voorbeeld: het lichaam met vier elementen.
Ondergroepen. Nevenklassen. De grootte van een ondergroep is een deler van de grootte van de groep. Toepassing op repeterende breuken: de lengte van het repeterende stuk bij decimale schrijfwijze van 1/m (met (m,10)=1) is de orde van 10 modulo m: de kleinste macht van 10 die gelijk 1 is modulo m. Omdat 10 een cyclische ondergroep voortbrengt is de orde van 10 een deler van de grootte van P_m, en in het bijzonder een deler van p-1 als m=p een priemgetal is.
Dus: 1/3 = 0.333.. periode 1, 1/7 = 0.1428571428571.. periode 6, 1/9 = 0.111.. periode 1, 1/11 = 0.0909.. periode 2, 1/13 = 0.0769230769.. periode 6, 1/17 = 0.05882352941176470588.. periode 16, 1/19 = 0.05263157894736842105.. periode 18, 1/21 = 0.0476190476.. periode 6, 1/27 = 0.0370370.. periode 3, enzovoort.
De groep P_m heet cyclisch als hij bestaat uit de machten van een enkel element. Kennelijk is dat bij m=7,17,19 zo en kunnen we voor dat ene element 10 nemen. Bij m=13 zijn er maar 6 verschillende machten van 10, maar de machten van 2 zijn 1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, dus ook P_13 is cyclisch met genererend element (primitieve wortel) 2. Maar in P_12 = {1,5,7,11} hebben alle elementen orde 2, dus P_12 is niet cyclisch.
Het RSA cryptosysteem. Versleutelen. Ontsleutelen. Handtekeningen. (Zie ook een oud collegefragment.)
Opgave Bepaal de grootte van P_m voor een aantal waarden van m, en vind daarna een expliciete formule voor alle m.