Relativt primisk

Relativt primiskeer toheltallhvis 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 multiplumav to tall er gitt ved deres produkt når de er relativt primiske. Slike tallpar spiller en viktig rolle i modernetallteoriogkryptografi.

Denne definisjonen er ekvivalent med å si at to tallmogner relativt primiske når deresstørste felles faktorgcd(m,n) = 1. Da denne kan beregnes ved bruk avEuklids 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 toheltallxogyslik 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 at3⋅42 - 5⋅25 = 1.

Tallteori

Antall positiveheltallsom er relativt primisk til et tallnog mindre enn dette, er gitt vedEulers 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 primtallpgjelder generelt atφ(p) =p- 1.

Imodulær aritmetikkgjør man ofte bruk av relativt primiske tall. For eksempel, enlineær kongruenssomax = b(mod n ) har én løsning nåraogner relativt primiske. Da er gcd(a,n) = 1 og talletahar da en inversx = a^-1slik ata⋅a^-1= 1 (mod n ) og kalles enenhet.Det betyr at hvis man ifaktorringenZ/n Z  kun beholder de tallene som er relativt primiske tiln,så vil de kunne kombineres multiplikativt og utgjør engruppeav enheter. Den har i altφ(n) element og betegnes ofte som (Z/n Z )^×.Slike grupper benyttes i dagenskryptografi.

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 matematikkfor nye studenter ved UiB, Bergen (2013).