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  

 

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

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.

Eksterne lenker 
 A. Hashemi, Forkurs i matematikk for nye studenter ved UiB, Bergen (2013).

Aritmetikk
Tallteori