Euler's Totient Function (phi function)

Ο Euler συνέχισε να ερευνά τις ιδιότητες των αριθμών-

ειδικά την κατανομή των πρώτων αριθμών.

Μια σημαντική συνάρτηση που όρισε

ονομάζεται "συνάρτηση του Φ".

Μετράει τη δυνατότητα εύρεσης παραγώντων δυο αριθμών.

Οπότε, δοθέντως ενός αριθμού, έστω, 'ν',

επιστρέφει πόσοι ακέραιοι που είναι μικρότεροι ή ίσοι από το ν

δεν έχουν κοινούς παράγοντες με το ν.

Για παράδειγμα, αν θέλουμε να βρούμε το Φ του 8,

παίρνουμε όλες τις τιμές από το 1 έως το 8,

και μετά μετράμε με πόσους ακεραίους

το 8 δεν έχει κοινό παράγοντα μεγαλύτερο του 1.

Παρατηρούμε, ότι το 6 δεν το μετράμε,

γιατί το 6 και το 8 έχουν κοινό τον παράγοντα 2,

ενώ τα 1, 3, 5 και 7 τα μετράμε,

γιατί έχουν κοινό μόνο τον παράγοντα 1.

Επομένως, Φ(8)=4.

Αυτό που παρουσιάζει ενδιαφέρον είναι ότι

ο υπολογισμός της συνάρτησης Φ είναι δύσκολος, με εξαίρεση μια περίπτωση.

Κοιτάξτε αυτό το γράφημα.

Είναι ένα σχέδιο των τιμών του Φ για ακεραίους από το 1 έως το 1000.

Τώρα, παρατηρείτε κάποιο προβλέψιμο μοτίβο;

Η ευθεία που ενώνει τα πάνω σημεία

παριστάνει όλους τους πρώτους αριθμούς.

Αφού οι πρώτοι αριθμοί δεν έχουν παράγοντες μεγαλύτερους του 1,

το Φ κάθε πρώτου αριθμού, "ρ", είναι απλά ρ-1.

Για να υπολογίσουμε το Φ του 7 - ενός πρώτου αριθμού -

μετράμε όλους τους ακεραίους εκτός από το 7 -

αφού κανένας από αυτούς δεν μοιράζεται έναν παράγοντα με το 7.

Φ(7)=6