Relativt primisk

Relativt primiske er to heltall hvis det ikke finnes noe tall større enn 1 som deler begge tallene. For eksempel er 42 og 25 relativt primiske, mens 42 og 15 ikke er det da 3 deler begge tallene. Minste felles multiplum av to tall er gitt ved deres produkt når de er relativt primiske. Slike tallpar spiller en viktig rolle i moderne tallteori og kryptografi.

Denne definisjonen er ekvivalent med å si at to tall m og n er relativt primiske når deres største felles faktor gcd(m,n) = 1. Da denne kan beregnes ved bruk av Euklids algoritme, vil den derfor også gi svar på om to tall er relativt primisk. Når det er tilfelle, vil det alltid være mulig å finne to heltall x og y slik at

mx+ny=1

To slike tall vil ha motsatt fortegn og kan ikke entydig bestemmes. For eksempel, for de relativt primiske tallene 42 og 25, finner man ved bruk av den euklidske algoritmen at 3⋅42 - 5⋅25 = 1.

Tallteori

Antall positive heltall som er relativt primisk til et tall n og mindre enn dette, er gitt ved Eulers totientfunksjon φ(n). For eksempel er φ(5) = 4 da tallene 1,2,3,4 er alle relativt primiske til 5. Derimot er φ(6) = 2 da bare 1 og 5 er relativt primisk blant de tallene som er mindre enn 6. For et primtall p gjelder generelt at φ(p) = p - 1.

I modulær aritmetikk gjør man ofte bruk av relativt primiske tall. For eksempel, en lineær kongruens som ax = b (mod n ) har én løsning når a og n er relativt primiske. Da er gcd(a,n) = 1 og tallet a har da en invers x = a^-1 slik at a⋅a^-1 = 1 (mod n ) og kalles en enhet. Det betyr at hvis man i faktorringen Z/n Z kun beholder de tallene som er relativt primiske til n, så vil de kunne kombineres multiplikativt og utgjør en gruppe av enheter. Den har i alt φ(n) element og betegnes ofte som (Z/n Z )^×. Slike grupper benyttes i dagens kryptografi.

Litteratur

J. Reed og J. Aarnes, Matematikk i vår tid, Universitetsforlaget, Oslo (1967).
T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, New York (1976). ISBN 0-387-90163-9.