🔢
★★★★★☆☆ Expert
maths
Combien de nombres entiers entre 1 et 1000 sont premiers avec 1000 (c'est-à-dire PGCD(n, 1000) = 1) ?
Réponse
400
C'est la fonction d'Euler φ(1000). 1000 = 2³ × 5³, donc φ(1000) = 1000 × (1 − 1/2) × (1 − 1/5) = 1000 × 1/2 × 4/5 = 400.