] >
Voor met komt het rekenen modulo neer op het ‘simultaan’ rekenen modulo en modulo . Dat is de betekenis van de Chinese reststelling. In deze paragraaf zullen we dit aantonen.
11.25 Chinese reststelling. Laten voldoen aan . Dan is er bij ieder paar van gehele getallen een geheel getal zodat en . Als ook een geheel getal is met en , dan .
Bewijs. Er zijn met . Neem . Dan en dus, omdat , . Evenzo .
Stel dat ook en . Dan en , ofwel en . Dus , ofwel . □
De stelling zegt dat de afbeelding
bijectief is als . De verzameling heeft elementen, evenals de verzameling . (De surjectiviteit, het eerste deel van de stelling, impliceert dus in feite de injectiviteit, het tweede deel van de stelling.) Uit de stelling volgt dat je in plaats van te rekenen in , ook kunt ook rekenen in . Een element correspondeert dan met het element . Optellen, vermenigvuldigen en machtsverheffen geschieden daarbij componentsgewijs. Verder is inverteerbaar dan en slechts dan als en inverteerbaar zijn. M.a.w. beperken we de afbeelding tot de inverteerbare elementen, dan krijgen we een bijectie
11.26 Voorbeeld. Figuur 11.2 bestaat uit plaatjes van de permutaties
De eerste twee permutaties stemmen overeen volgens de Chinese reststelling. De laatste twee permutaties bepalen de permutatie van . Het is eenvoudig in te zien dat de orde van modulo gelijk is aan en dat hij modulo gelijk is aan . Modulo is die orde dus . Daarvoor is het dus niet nodig om de machten van in te bepalen.
Uit de Chinese reststelling volgt dat het aantal inverteerbare elementen in gelijk is aan het aantal inverteerbare elementen in onder componentsgewijs vermenigvuldigen. Om de orde van een modulo te bepalen, kun je dus ook de kleinste bepalen waarvoor en dat is de kleinste gemene veelvoud van de ordes van modulo en modulo . We hebben nu in het bijzonder:
De formule voor de Eulerindicator is hiervan weer een gevolg:
Bewijs. In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □
11.29 Voorbeeld. We berekenen opnieuw in , nu met behulp van de Chinese reststelling. Daartoe berekenen we eerst in en ook in . In hebben we want . Verder en , dus in : . Dus in : , want en . Op deze wijze ziet men in dat in zelfs geldt voor alle , want en (immers ).
11.30 Voorbeeld. In Voorbeeld 11.12 zagen we dat in . In plaats machtsverheffen in kunnen we ook machtsverheffen in . De orde van een in is of . In is de orde van een element een deler van . De orde van een geheel getal modulo is dus een deler van . De orde van modulo is en modulo is hij .
11.31 Definitie. Zijn en algebraïsche structuren als groepen of ringen, dan zeggen we dat een afbeelding een homomorfisme is als hij de bewerkingen behoudt. Zijn en groepen dan heet een isomorfisme van groepen of een groepsisomorfisme als de groepsbewerking behoudt (hoe die ook genoteerd wordt). Zijn en ringen dan heet een isomorfisme van ringen of een ringisomorfisme als hij zowel de optelling als de vermenigvuldiging behoudt (dus: en voor alle ) en bovendien . (We zien als een bewerking ).
Groepen en heten isomorf als er een groepsisomorfisme van naar bestaat. Evenzo heten ringen en isomorf als er een ringisomorfisme van naar bestaat. Notatie: .
Eisen we niet dat de afbeelding een bijectie is, maar wel dat hij de bewerkingen behoudt, dan spreken we van een homomorfisme. In het bijzonder hebben we dan homomorfismen van groepen en homomorfismen van ringen.
is volgens de Chinese reststelling bijectief als en we merkten al op dat hij de bewerkingen behoudt. Het is een isomorfisme van ringen. Hierbij is de ring met de bewerkingen componentsgewijs. Beide ringen zijn dus isomorf.
Beide groepen zijn dus isomorf.