Σχετικά πρώτοι

Στη θεωρία αριθμών, δύο ακέραιοι αριθμοί ${\displaystyle x}$ και ${\displaystyle y}$ ονομάζονται σχετικά πρώτοι ή πρώτοι προς αλλήλους ή μεταξύ τους πρώτοι αν ο μέγιστος κοινός διαιρέτης τους είναι η μονάδα.^[1][2][3] Ισοδύναμα, θα μπορούσαμε να πούμε ότι είναι σχετικά πρώτοι εάν δεν έχουν άλλο κοινό διαιρέτη πλην του 1. Εξ ορισμού δύο (διαφορετικοί) πρώτοι αριθμοί είναι και σχετικά πρώτοι μεταξύ τους. Συμβολικά γράφουμε: ΜΚΔ(x, y) = 1 ή gcd(x, y) = 1 ή x  ⊥  y.^[4]

Για παράδειγμα οι ακέραιοι 14 και 15 είναι σχετικά πρώτοι γιατί ο μόνος κοινός διαιρέτης τους είναι το 1, δηλαδή ΜΚΔ(14, 15) = 1. Οι 14 και 21 δεν είναι σχετικά πρώτοι γιατί ΜΚΔ(14, 21) = 7.

Παράδειγμα

Για παράδειγμα οι αριθμοί 23 και 21 είναι σχετικά πρώτοι και για να το διαπιστώσουμε αυτό αρκεί να τρέξουμε τον αλγόριθμο του Ευκλείδη.

Να θυμίσουμε ότι ο αλγόριθμος του Ευκλείδη βρίσκει το μέγιστο κοινό διαιρέτη (ΜΚΔ) δύο αριθμών ${\displaystyle x}$ και ${\displaystyle y}$ (έστω ${\displaystyle x>y}$), με την ακόλουθη αναδρομική διαδικασία:

Με είσοδο ${\displaystyle (x,y)}$:

1. Αν το ${\displaystyle y}$ είναι μηδέν, δώσε το ${\displaystyle x}$ ως έξοδο.
2. Βρες το υπόλοιπο της διαίρεσης του ${\displaystyle x}$ με το ${\displaystyle y}$, έστω ${\displaystyle \upsilon }$.
3. Τρέξε αναδρομικά τον αλγόριθμο (πήγαινε στο βήμα 1) με είσοδο ${\displaystyle (y,\upsilon )}$.

Στο παράδειγμά μας έχουμε την ακόλουθη εκτέλεση (καλείται την πρώτη φορά ευθέως και τις άλλες τρεις αναδρομικά):

1. ΜΚΔ(23,21)
2. ΜΚΔ(21,2)
3. ΜΚΔ(2,1)
4. ΜΚΔ(1,0) και επιστρέφεται το 1 που είναι ο μέγιστος κοινός διαιρέτης των 23, 21.

Άρα, δείξαμε ότι οι αριθμοί 23 και 21 είναι σχετικά πρώτοι.

Δείτε επίσης

• Πρώτος αριθμός
• Συνάρτηση Όιλερ, ${\displaystyle \varphi (n)}$, η οποία μας δίνει το πλήθος των μικρότερων του ${\displaystyle n}$ φυσικών αριθμών οι οποίοι είναι σχετικά πρώτοι με τον ${\displaystyle n}$.
• Μέγιστος κοινός διαιρέτης

Παραπομπές

1. Παπαδημητράκης, Μιχάλης. «Θεωρία αριθμών: Πρόχειρες σημειώσεις» (PDF). Τμήμα Μαθηματικών, Πανεπιστήμιο Κρήτης. Ανακτήθηκε στις 6 Απριλίου 2023.
2. Γκότσης, Κ. (2017). «Σημειώσεις στοιχειώδους θεωρίας αριθμών» (PDF). Ανακτήθηκε στις 6 Απριλίου 2023.
3. Αντωνιάδης, Ιωάννης· Κοντογεώργης, Αριστείδης (2015). Θεωρία αριθμών και εφαρμογές. Κάλλιπος, Ανοικτές Ακαδημαϊκές Εκδόσεις. Ανακτήθηκε στις 6 Απριλίου 2023.^{[νεκρός σύνδεσμος]}
4. Κάτος, Β., Στεφανίδης, Γ., (2003). «Τεχνικές Κρυπτογραφίας και Κρυπτανάλυσης. 3.Θεωρία αριθμών - αλγεβρικές δομές», σελ. 7, Εκδόσεις: ΖΥΓΟΣ, (ISBN 960-8065-40-2). Αρχειοθετήθηκε 26/01/2019. Ανακτήθηκε 26/01/2019.