Τετάρτη 20 Σεπτεμβρίου 2023

Μικρότερος θετικός

Η συνάρτηση Euler totient του $n$, που συμβολίζεται ως $ϕ(n)$, δίνει τον αριθμό των θετικών ακεραίων μικρότερων ή ίσων του $n$, που είναι σχετικά πρώτοι του $n$. 
Βρείτε τον μικρότερο θετικό ακέραιο $m$ έτσι ώστε 

3 σχόλια:

  1. Υπολογίζω, κάπως πρόχειρα, ότι ο ελάχιστος m είναι ο 8069 (+/-1 ίσως). Αν ασχολήθηκε κάποιος φίλος, ας επιβεβαιώσει ή διαψεύσει..

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. Υπενθυμίζεται ότι αν η έκφραση του n ως γινόμενο πρώτων παραγόντων είναι n=p1^a1*p2^a2*p3^a3*.., τότε:
      Φ(n)=[p1^(a1-1)(p1-1)]*[p2(a2-1)(p2-1)]*..
      Η πιο πάνω φόρμουλα νομίζω αρκεί για να διαπιστώσουμε γρήγορα σε πόσες επαναληπτικές εφαρμογές της, με αρχικό n=29^2017, καταλήγει στο 1.

      Διαγραφή
    2. Διόρθωση:
      Φ(n)=[p1^(a1-1)(p1-1)]*[p2^(a2-1)(p2-1)]*..

      Διαγραφή