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

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

Συμβολικά γράφουμε: $\mathrm {MK\Delta } (x,y)=1$ ή $\mathrm {gcd} (x,y)=1$ ή $x\perp y$.

Για παράδειγμα οι ακέραιοι $14$ και $15$ είναι σχετικά πρώτοι γιατί ο μόνος κοινός διαιρέτης τους είναι το 1, δηλαδή $\mathrm {MK\Delta } (14,15)=1$. Οι $14$ και $21$ δεν είναι σχετικά πρώτοι γιατί $\mathrm {MK\Delta } (14,21)=7$.

Αυστηρός ορισμός

Δύο φυσικοί αριθμοί $x,y\in \mathbb {N}$ είναι σχετικά πρώτοι μεταξύ τους αν

$\max\{d\in \mathbb {N} :d|x{\text{ και }}d|y\}=1$,

όπου $\mathbb {N}$ το σύνολο των φυσικών αριθμών και $d|x$ δηλώνει ότι ο $d$ διαιρεί τον $x$.

Παραδείγματα

• Οι αριθμοί 4 και 9 είναι σχετικά πρώτοι, καθώς κανένας από τους πιθανούς κοινούς παράγοντες $2,3,4$ δεν διαιρεί και τους δύο αριθμούς.
• Οι αριθμοί 3 και 8 είναι σχετικά πρώτοι.
• Οι αριθμοί 21 και 23 είναι σχετικά πρώτοι.

• Οι αριθμοί 4 και 6 δεν είναι σχετικά πρώτοι μεταξύ τους, καθώς ο $2$ διαιρεί και τους δύο.
• Οι αριθμοί 3 και 9 δεν είναι σχετικά πρώτοι μεταξύ τους, καθώς ο $3$ διαιρεί και τους δύο.
• Οι αριθμοί 6 και 22 δεν είναι σχετικά πρώτοι μεταξύ τους, καθώς ο $2$ διαιρεί και τους δύο.

Αλγοριθμικός έλεγχος

Οποιοσδήποτε αλγόριθμος για την εύρεση του μέγιστου κοινού διαιρέτη (ΜΚΔ) δύο φυσικών αριθμών μπορεί να χρησιμοποιηθεί για να ελέγξουμε αν δύο αριθμοί είναι σχετικά πρώτοι μεταξύ τους, ελέγχοντας αν ο ΜΚΔ είναι 1.

Αλγόριθμος του Ευκλείδη

Ο αλγόριθμος του Ευκλείδη βρίσκει το μέγιστο κοινό διαιρέτη δύο αριθμών $x$ και $y$ (έστω $x>y$), με την ακόλουθη αναδρομική διαδικασία:

Με είσοδο $(x,y)$:

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

Για $x=23,y=21$ έχουμε την ακόλουθη εκτέλεση (καλείται την πρώτη φορά ευθέως και τις άλλες τρεις αναδρομικά):

1. $\mathrm {MK\Delta } (23,21)$
2. $\mathrm {MK\Delta } (21,2)$
3. $\mathrm {MK\Delta } (2,1)$
4. $\mathrm {MK\Delta } (1,0)$ και επιστρέφεται το $1$ που είναι ο μέγιστος κοινός διαιρέτης των $23$, $\mathrm {MK\Delta } 21$.

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

Σχετικές έννοιες

Συνάρτηση Όιλερ

Η συνάρτηση Όιλερ $\varphi (n)$ μας δίνει το πλήθος των φυσικών αριθμών μικρότερων του $n$ οι οποίοι είναι σχετικά πρώτοι με τον $n$. Για παράδειγμα, $\phi (10)=4$ καθώς οι αριθμοί $1,3,7,9$ είναι σχετικά πρώτοι με το $10$, ενώ οι $2,4,5,6,8$ δεν είναι σχετικά πρώτοι με το $10$ (έχουν κοινό παράγοντα το $2$ ή το $5$).

Δείτε επίσης

• Πρώτος αριθμός
• Συνάρτηση Όιλερ
• Μέγιστος κοινός διαιρέτης