Relativt primisk

Fra Wikipedia, den frie encyklopedi
Hopp til: navigasjon, søk

Relativt primisk[rediger | rediger kilde]

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 a og b er relativt primiske når deres største felles faktor gcd(a,b) = 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 tall x og y slik at

 ax + by = 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[rediger | rediger kilde]

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 blandt de tallene som er mindre enn 6. For et primtall p er generelt φ(p) = p - 1.

I modulær aritmetikk gjør man ofte bruk av relativt primiske tall. For eksempel, i en kongruens som am = an (mod b ) kan man forkorte med a på begge sider med resultatet m = n (mod b ) kun når a og b er relativt primiske. Likedan, løsningen av kongruensen ax = 1 (mod b ) med hensyn på x, er bare mulig når a og b er relativt primiske. Tallet a har da en invers x = a -1 slik at a⋅a -1 = 1 (mod b ) og kalles en enhet. Det betyr at hvis man i faktorringen Zb = Z/< b > kun beholder de tallene som er relativt primiske til b, så vil de kunne kombineres multiplikativt og utgjør en gruppe av enheter. Den har i alt φ(b) slike element og betegnes ofte som Zb×. Slike grupper benyttes i dagens kryptografi.

Litteratur[rediger | rediger kilde]

  • 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[rediger | rediger kilde]