Indbyrdes primisk

Fra Wikipedia, den frie encyklopædi
Gå til: navigation, søg

I talteorien siges to heltal a og b at være indbyrdes primiske eller relative primtal, hvis de eneste tal, der går op i begge tal, er 1 og −1, eller, ækvivalent, hvis deres største fælles divisor er 1.

Eksempelvis er 6 og 35 indbyrdes primiske, men 6 og 27 er ikke, da 3 går op i begge tal. Tallene 1 og −1 er indbyrdes primiske med alle andre heltal. 0 er kun indbyrdes med 1 og −1

En hurtig måde at bestemme om to tal er indbydes primiske er givet ved Euklids algoritme.

Eulers totientfunktion (eller Eulers phifunktion) af et naturligt tal n er antallet af tal mellem 1 og n, der er indbyrdes primiske med n.