Keskenään jaottomat luvut -laskuri

Keskenään jaottomat luvut -laskuri

Tällä laskurilla voit tarkistaa, ovatko kaksi lukua keskenään jaottomia. Laskuri kertoo lukujen suurimman yhteisen tekijän, mahdolliset yhteiset alkutekijät sekä supistetun murtoluvun, jonka luvut muodostavat.

Mitä keskenään jaottomuus tarkoittaa?

Kaksi lukua ovat keskenään jaottomia eli suhteellisia alkulukuja, kun niiden ainoa yhteinen positiivinen tekijä on ykkönen. Tällöin luvuilla ei ole yhtään yhteistä alkutekijää:

a ja b ovat keskenään jaottomia ⇔ syt(a, b) = 1

Huomaa, että luvut eivät tarvitse olla alkulukuja. Esimerkiksi 8 ja 15 ovat keskenään jaottomia, vaikka kumpikaan ei ole alkuluku.

Suurin yhteinen tekijä ratkaisee

Keskinäinen jaottomuus tarkistetaan suurimman yhteisen tekijän avulla. Jos syt on 1, luvuilla ei ole yhteistä jakajaa ykköstä lukuun ottamatta. Suurin yhteinen tekijä lasketaan tehokkaasti Eukleideen algoritmilla, joka jakaa toistuvasti suuremman luvun pienemmällä ja ottaa jakojäännöksen:

syt(a, b) = syt(b, a mod b),  kunnes jälkimmäinen on 0

Vaiheittainen esimerkki

Tarkistetaan, ovatko 8 ja 15 keskenään jaottomia. Lasketaan syt Eukleideen algoritmilla:

syt(15, 8): 15 = 1·8 + 7
syt(8, 7): 8 = 1·7 + 1
syt(7, 1): 7 = 7·1 + 0 → syt = 1

Suurin yhteinen tekijä on 1, joten 8 ja 15 ovat keskenään jaottomia. Vertailun vuoksi 12 ja 18 eivät ole, koska syt(12, 18) = 6.

Alkutekijöiden vertailu

Toinen tapa on hajottaa luvut alkutekijöihin ja katsoa, onko yhteisiä tekijöitä:

8 = 2 · 2 · 2  ja  15 = 3 · 5

Luvuilla ei ole yhtään yhteistä alkutekijää, joten ne ovat keskenään jaottomia. Jos luvuilla olisi yhteinen alkutekijä, syt olisi vähintään tuo tekijä.

Yhteys murtolukujen supistamiseen

Keskinäinen jaottomuus kertoo suoraan, onko murtoluku jo supistetussa muodossa. Murtoluku on supistettu, kun osoittaja ja nimittäjä ovat keskenään jaottomia:

a/b on supistettu ⇔ syt(a, b) = 1

Jos syt on suurempi kuin 1, murtoluvun voi supistaa jakamalla sekä osoittajan että nimittäjän sillä.

Peräkkäiset luvut ovat aina keskenään jaottomia

Mitkä tahansa kaksi peräkkäistä kokonaislukua ovat aina keskenään jaottomia. Esimerkiksi 14 ja 15 tai 99 ja 100. Tämä johtuu siitä, että peräkkäisten lukujen erotus on 1, eikä mikään ykköstä suurempi luku voi jakaa molempia tasan.

Käyttökohteet

Keskinäistä jaottomuutta tarvitaan murtolukujen supistamisessa, jakojäännöslaskennassa eli modulaariaritmetiikassa sekä lukuteorian todistuksissa. Sillä on käytännön merkitystä myös tietoturvassa, sillä monet salausmenetelmät perustuvat keskenään jaottomien lukujen ominaisuuksiin.