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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση

Δύο αριθμοί x και y ονομάζονται σχετικά πρώτοι αν ο μέγιστος κοινός διαιρέτης τους είναι η μονάδα. Αλλιώς, θα μπορούσαμε να πούμε ότι είναι σχετικά πρώτοι εάν δεν έχουν άλλο κοινό διαιρέτη πλην του 1. Καμιά φορά χρησιμοποιείται και η σημειογραφία x  ⊥  y.

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

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

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

1. Αν το y είναι μηδέν, δώσε το x ως έξοδο.

2. Βρες το υπόλοιπο της διαίρεσης του x με το y, έστω \upsilon.

3. Τρέξε αναδρομικά τον αλγόριθμο με είσοδο (y, \upsilon).


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

1. μκδ(23,21)

2. μκδ(21,2)

3. μκδ(2,1)

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


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

Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]