Resten

De Chinese reststelling

Lagrange interpolatie stelt je in staat een polynoom van graad n te vinden waarvan de grafiek door n+1 gegeven punten gaat. De formule is een som van termen waarbij elke term op alle plaatsen op 1 na verdwijnt (nul is) en op die ene plaats precies de goede waarde heeft.

Hetzelfde idee werkt om de Chinese reststelling te bewijzen:

Laten moduli m₁, ..., m_r gegeven zijn, paarsgewijs onderling priem, en laten a₁, ..., a_r voorgeschreven resten zijn. Dan is er een x zo, dat x = a_i modulo m_i voor alle i.

Voorbeeld Als we een getal willen vinden dat congruent 3 is modulo 5, en 1 modulo 7, en 6 modulo 12, dan zoeken we getallen met respectievelijke resten 3,0,0 en 0,1,0 en 0,0,6 modulo 5,7,12 en tellen die op.
Het eerste getal is een veelvoud van 7 en 12, dus van 84 (dat 4 is modulo 5) en om dat 3 modulo 5 te krijgen moeten we 2*84 = 168 nemen.
Het tweede getal is een veelvoud van 5 en 12, dus van 60 (dat 4 is modulo 7) en om dat 1 modulo 7 te krijgen moeten we 2*60 = 120 nemen.
Het derde getal is een veelvoud van 5 en 7, dus van 35 (dat 11 is modulo 12) en om dat 6 modulo 12 te krijgen moeten we 6*35 = 210 nemen.
Nu voldoet x = 168+120+210 = 498, en ook alle getallen die congruent 498 zijn modulo 5*7*12 = 420, dus bijvoorbeeld x = 78 is ook goed. In feite is de oplossing uniek (modulo 420).

Fermat

De kleine stelling van Fermat.

Kwadraatresten

Een getal a heet kwadraatrest modulo m als de vergelijking x² = a (mod m) oplossingen heeft.

We zullen alleen naar het geval m = p, een oneven priemgetal, kijken.

Als x² = a, dan is ook (-x)² = a. We zien dat de resten mod p uiteenvallen in 0, in (p-1)/2 niet-nul kwadraten, en in (p-1)/2 niet-kwadraten.

Definieer het symbool van Legendre (a/p) als 0 voor a = 0, als 1 voor a een niet-nul kwadraat, en als -1 voor a een niet-kwadraat modulo p.

Omdat de vermenigvuldiggroep van niet-nul resten mod p cyclisch is, volgt dat (a/p) = a^(p-1)/2 (modulo p).

Dit is belangrijk omdat het rechterlid efficient uitgerekend kan worden, ook als p een paar honderd cijfers heeft, terwijl het oplossen van x² = a niet doenlijk is.

Voorbeeld Neem p = 7. We vinden (0/7) = 0, (1/7) = (2/7) = (4/7) = 1, en (3/7) = (5/7) = (6/7) = -1. Aan de ene kant volgt dit door alle kwadraten uit te rekenen: 1² = 1, 2² = 4, 3² = 2, 4² = 2, 5² = 4, 6² = 1 (mod 7). Aan de andere kant volgt dit uit de formule: (2/7) = 2³ = 8 = 1 (mod 7), en (3/7) = 3³ = 27 = -1 (mod 7).

Hetzelfde argument dat de kleine stelling van Fermat bewees (d.w.z. dat gebruikt werd om a^p-1 uit te rekenen) kan gebruikt worden om a^(p-1)/2 uit te rekenen. We vinden: neem de resten 1,2,...,(p-1)/2 mod p, vermenigvuldig ze alle met a en reduceer mod p tot de kleinst mogelijke absolute waarde. Telkens vinden we een rest in 1,2,...,(p-1)/2, of een rest in -1,-2,...,-(p-1)/2. Het getal a is een kwadraat precies als het aantal keren dat een negatieve rest optreedt even is.

Voorbeeld Neem p = 7. Als we 1,2,3 met 5 vermenigvuldigen en reduceren vinden we -2,3,1 dus 5 is geen kwadraat. Als we 1,2,3 met 2 vermenigvuldigen en reduceren vinden we 2,-3,-1 dus 2 is een kwadraat.

Dit leidt eenvoudig tot:

-1 is een kwadraat precies wanneer p = 1 (mod 4).

2 is een kwadraat precies wanneer p = 1 of 7 (mod 8).

Kwadratische reciprociteit

Omdat het product van twee kwadraten of van twee niet-kwadraten weer een kwadraat is, terwijl het product van een kwadraat en een niet-kwadraat een niet-kwadraat is (zodat het symbool van Legendre multiplicatief is) kunnen we (a/p) uitrekenen door a in factoren te ontbinden, bovenstaande regels te gebruiken voor factoren -1 en 2, en onderstaande stelling voor factoren die oneven priemen zijn.

Met een lichte aanpassing van de theorie is dat ontbinden in factoren niet eens nodig, en het uitrekenen van (a/m) kost niet meer tijd dan het uitrekenen van een ggd.

Stelling Laten p en q verschillende oneven priemgetallen zijn. Dan is (p/q).(q/p) = (-1)^(p-1)(q-1)/4.

Met andere woorden, (p/q) en (q/p) zijn gelijk als minstens een van p en q congruent 1 (mod 4) is, en ze hebben tegengesteld teken als p = q = 3 (mod 4).

Voorbeeld (40/109) = (2/109)(2/109)(2/109)(5/109) = -(5/109) = -(109/5) = -(-1/5) = -1.