Relativt primisk

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

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

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 blant 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]