▪ Συνάρτηση Euler

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

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

Ιδιότητες
Aν φ(n) = 0, τότε n = 0 και αντίστροφα.
φ(1) = 1
φ(n) = n - 1, αν και μόνο αν ο n είναι πρώτος αριθμός.
Γενικότερα, για έναν πρώτο αριθμό p και τον φυσικό αριθμό e έχουμε

φ(p^e) = p^e -  p^{e - 1}.

Μια θεμελιώδης ιδιότητα της συνάρτησης του Euler είναι ότι είναι πολλαπλασιαστική. Αν n, m φυσικοί αριθμοί είναι μεταξύ τους πρώτοι αριθμοί, τότε

φ(m∙n) = φ(m)∙φ(n).

Παραδείγματα
φ(4) = φ(2²) = 2² - 2
φ(55) = φ(5∙11) = φ(5)∙ φ(11) = (5 – 1)∙(11 – 1) = 4∙10 = 40.