Η συνάρτηση Euler (ή αλλιώς συνάρτηση φ του Euler, σημειώνεται ως φ(n)) είναι μια αριθμητική συνάρτηση που έχει ιδιαίτερη σημασία στην θεωρία αριθμών. Ο σκοπός της συνάρτησης αυτής είναι να μετρήσει το πλήθος των θετικών ακεραίων μικρότερων ή ίσων ενός δεδομένου θετικού ακεραίου $n$, οι οποίοι είναι σχετικώς πρώτοι προς το $n$ (δηλαδή δεν έχουν κοινούς διαιρέτες με το $n$ εκτός από το 1).

Ορισμός

Για έναν θετικό ακέραιο $n$, ορίζουμε τη συνάρτηση Euler, φ(n), ως τον αριθμό των θετικών ακεραίων $k$ με $1 \leq k \leq n$ που είναι σχετικά πρώτοι προς το $n$.

Συμβολισμός: $φ(n) = |\{ k \leq n : \text{gcd}(k, n) = 1 \}|$

όπου $\text{gcd}(k, n)$ είναι ο μέγιστος κοινός διαιρέτης (ΜΚΔ) των $k$ και $n$.

Ιδιότητες της Συνάρτησης Euler

1. Υπολογισμός με χρήση πρώτων παραγόντων: Εάν ο αριθμός $n$ έχει πρώτους παράγοντες $p_1, p_2, \ldots, p_m$, τότε η συνάρτηση Euler υπολογίζεται ως εξής: $φ(n) = n \left( 1 - \frac{1}{p_1} \right) \left( 1 - \frac{1}{p_2} \right) \cdots \left( 1 - \frac{1}{p_m} \right)$

   Για παράδειγμα, για $n = 12$ (που έχει πρώτους παράγοντες $2$ και $3$), έχουμε: $φ(12) = 12 \left(1 - \frac{1}{2}\right) \left(1 - \frac{1}{3}\right) = 12 \times \frac{1}{2} \times \frac{2}{3} = 4$

2. Ιδιότητα αμοιβαία πρώτων αριθμών: Αν δύο αριθμοί $m$ και $n$ είναι αμοιβαία πρώτοι, τότε ισχύει: $φ(m \cdot n) = φ(m) \cdot φ(n)$

3. Άρρηκτες τιμές για πρώτους αριθμούς: Αν $p$ είναι πρώτος, τότε $φ(p) = p - 1$, αφού όλοι οι αριθμοί από το 1 έως το $p-1$ είναι σχετικά πρώτοι με τον $p$.

4. Άρτια και περιττή φύση της φ(n): Εάν $n > 2$, τότε η $φ(n)$ είναι άρτιος αριθμός.

Η συνάρτηση Euler βρίσκει εφαρμογές στην κρυπτογραφία, ειδικά στο σύστημα κρυπτογράφησης RSA, και σε προβλήματα που αφορούν τον μικρό θεώρημα του Fermat.

Παράδειγμα Υπολογισμού της Συνάρτησης

Για να υπολογίσουμε το $φ(9)$:

1. Οι πρώτοι παράγοντες του 9 είναι μόνο το 3.
2. Άρα, $φ(9) = 9 \left( 1 - \frac{1}{3} \right) = 9 \cdot \frac{2}{3} = 6$. Επομένως, υπάρχουν 6 θετικοί ακέραιοι μικρότεροι ή ίσοι του 9 που είναι σχετικά πρώτοι με το 9 (οι αριθμοί αυτοί είναι οι: 1, 2, 4, 5, 7 και 8).

Θα θέλατε περισσότερες λεπτομέρειες ή άλλες απορίες;

---

1. Πώς συνδέεται η συνάρτηση Euler με το Μικρό Θεώρημα του Fermat;
2. Τι ιδιότητες έχουν οι αριθμοί για τους οποίους ισχύει φ(n) = n - 1;
3. Πώς εφαρμόζεται η συνάρτηση Euler στην κρυπτογραφία RSA;
4. Ποια είναι η σχέση της συνάρτησης Euler με την αναζήτηση των πρώτων αριθμών;
5. Πώς μπορούμε να υπολογίσουμε τη φ(n) όταν ο αριθμός έχει πολλούς πρώτους παράγοντες;

Tip: Η συνάρτηση Euler υπολογίζεται εύκολα αν πρώτα βρούμε τους πρώτους παράγοντες του αριθμού.