Keskenään jaottomat luvut

Lukuteoriassa kokonaislukuja ${\displaystyle a}$ ja ${\displaystyle b}$ sanotaan keskenään jaottomiksi tai suhteellisiksi alkuluvuiksi tai alkuluvuiksi toistensa suhteen, jos ${\displaystyle a}$:n ja ${\displaystyle b}$:n suurin yhteinen tekijä on 1.^[1] Luku 1 on keskenään jaoton jokaisen kokonaisluvun kanssa, ja luku 0 on keskenään jaoton vain 1:n ja −1:n kanssa.

Keskenään jaottomille luvuille pätee Bézout’n lemma: jos ${\displaystyle a}$ ja ${\displaystyle b}$ ovat keskenään jaottomia, niin on olemassa sellaiset kokonaisluvut ${\displaystyle x}$ ja ${\displaystyle y}$, että ${\displaystyle ax+by=1}$.

Kahden kokonaisluvun suurin yhteinen tekijä voidaan määrittää Eukleideen algoritmilla.

Eulerin φ-funktio ${\displaystyle \phi (n)}$ positiiviselle kokonaisluvulle ${\displaystyle n}$ on niiden 1:n ja ${\displaystyle n}$:n välillä olevien kokonaislukujen lukumäärä, jotka ovat keskenään jaottomia ${\displaystyle n}$:n kanssa.^[2]

Katso myös

• Alkuluku

Lähteet

• Rosen, Kenneth H.: Elementary Number Theory and Its Applications. Reading, Massachusetts: Addison-Wesley, 1984. ISBN 0-201-06561-4. (englanniksi)

Viitteet