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

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

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

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

Παράδειγμα[Επεξεργασία | επεξεργασία κώδικα]

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

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

Με είσοδο :

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

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

3. Τρέξε αναδρομικά τον αλγόριθμο (πήγαινε στο βήμα 1) με είσοδο .


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

1. μκδ(23,21)

2. μκδ(21,2)

3. μκδ(2,1)

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

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

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

  • Πρώτος αριθμός
  • Συνάρτηση 'Οιλερ (Euler), , η οποία μας δίνει το πλήθος των μικρότερων του φυσικών αριθμών οι οποίοι είναι σχετικά πρώτοι με τον .

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

  1. Παπαδημητράκης Μιχάλης. «Θεωρία Αριθμών», σελ. 11, από Πανεπιστήμιο Κρήτης-Τμήμα Μαθηματικών. Αρχειοθετήθηκε 03/04/2018. Ανακτήθηκε 16/01/2019.
  2. Κάτος, Β., Στεφανίδης, Γ., (2003). «Τεχνικές Κρυπτογραφίας και Κρυπτανάλυσης. 3.Θεωρία αριθμών - αλγεβρικές δομές», σελ. 7, Εκδόσεις: ΖΥΓΟΣ, (ISBN 960-8065-40-2). Αρχειοθετήθηκε 26/01/2019. Ανακτήθηκε 26/01/2019.