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

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

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

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

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

Με είσοδο :
Αν το  είναι μηδέν, δώσε το  ως έξοδο.
Βρες το υπόλοιπο της διαίρεσης του  με το , έστω .
Τρέξε αναδρομικά τον αλγόριθμο (πήγαινε στο βήμα 1) με είσοδο . 

Στο παράδειγμά μας έχουμε την ακόλουθη εκτέλεση (καλείται την πρώτη φορά ευθέως και τις άλλες τρεις αναδρομικά):
ΜΚΔ(23,21)
ΜΚΔ(21,2)
ΜΚΔ(2,1)
ΜΚΔ(1,0) και επιστρέφεται το 1 που είναι ο μέγιστος κοινός διαιρέτης των 23, 21.

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

Δείτε επίσης 

Πρώτος αριθμός
Συνάρτηση Όιλερ, , η οποία μας δίνει το πλήθος των μικρότερων του  φυσικών αριθμών οι οποίοι είναι σχετικά πρώτοι με τον .
Μέγιστος κοινός διαιρέτης

Παραπομπές 

Πρώτοι αριθμοί
Θεωρία αριθμών