Modulär aritmetik
Modulär aritmetik är en variant villig heltalsystemetsaritmetik. Ibland refereras modulär aritmetik somklockaritmetik eftersom den, precis som klockan, slår runt när talen når ett okej värde (modulustalet). Tillexempel så vet vi ju att fem timmar efter klockan åtta så är klockanett, ej tretton. Detta för att klockan börjar försåvitt från noll närmodulustalet (24) uppnås.Om modulustalet, n, är ett positivt heltal så kallas par (eller flera) heltal, x samt y, kongruenta om, samt endast försåvitt deras farit när de delas med n är densamma. De sägs då tillhöra samma ekvivalensklass.Matematiskt skrivs detta som
x = y (mod n)
eller
n | x - y
Ekvivalensklasserna i sig har väldigt intressanta egenskaper.Det visar sig att nästföljande räknelagar (som den intresserade lätt kan härleda)gäller.
Om v = x (mod n)ochy = z (mod n)
där c, n, v, x, y, z tillhör Z
så gäller
i) cv = cx (mod n)ii)v + y = x + z (mod n)iii) vy = xz (mod n)
Detta är väldigt användbart för att reducera beräkningsstorleken i stora besvär.
Ett exempel
Vad blir resten då man dividerar 68^(45) med 23?
Genom att använda i) samt låta c = 68^(44) samt v = 68så vet vi att 68 = (-1) (mod 23)ty69 = 3 * 23Men det stämmer likaså för x = (-1) + 23 * p (där p tillhör Z). Eftersom 0 <= x < 23 så återstår endast 22 som möjlig farit (om resten var 23 ellerstörre så kan man ju dividera med 23 minst en passage till).Kvar att göra
- Talringar (koppla mot ekvivalensklasser?)
- Primtal (Fermat, Euler)
- Historik (Gauss)
- M-serier
- Kopplingen mot elliptiska ekvationer
Artikeln skriven 2009-01-15 av Learning4sharing
Inga kategorier för denna artikel än...Intresserad av fler artiklar?
YnkryggVardagshjälte
Rockhjälte
Sporthjälte
Transpiranto
Gott nytt år
Janne Rydberg
Rydbergs konstant
Biff Rydberg