Da się to szybko zrobić? Antek: Mam pytanie czy da się szybko wyznaczyć liczebność takiego zbioru: {n∊ℕ | φ(n) =8} , Czyli zbiór liczb dla których funkcja Eulera przyjmuje wartość 8.

Adamm: φ(n)=p₁^α₁−1(p₁−1)...p_n^α_n−1(p_n−1) φ(11^k)=11^k−1*10≥8 więc liczb pierwszych ≥11 nie może być wśród rozkładu n na liczby pierwsze n=2^a*3^b*5^c*7^d 3|φ(7^d) dla d≥1 więc musi być n=2^a3^b5^c dla c≥2, 5|φ(5^c), więc musi być c=1 lub c=0 b≥2 to 3|φ(3^b) więc b=1 lub b=0 1. c=1 φ(5)=4 b=1 to φ(3)=2 i musi być φ(2^a)=2^a−1=1 czyli a=1 lub a=0 n=5*3*2 lub n=5*3 b=0 to φ(2^a)=2^a−1=2 czyli a=2 n=5*2² 2. c=0 b=1 to φ(2^a)=2^a−1=4 czyli a=3 n=3*2³ b=0 to φ(2^a)=2^a−1=8 czyli a=4 n=2⁴ zbiór={5*3*2, 5*3, 5*2², 3*2³, 2⁴} ma 5 elementów