practice problems pending
Q. Find the form of all positive integers n satisfying τ(n)=10. What is the smallest positive integer for which this is true? τ(n) is totient function. Solution: Let's call it phi(n). 10 = phi(n) = p1^k1.p2^k2.p3^k3.(1- 1/p1)(1-1/p2)(1-1/p3)... = p1^(k1-1).p2^(k2-1).(p1-1).(p2-1)... => each of (p1-1),(p2-1),... will divide 10. So possible prime factors are p-1 = 1,2,5,10 => p = 2,3,6,11 Since 6 is not a prime, p = 2,3,11 And n is of the form: 2^a.3^b.11^c Since 2^a,3^b,11^c are pairwise co-primes => phi(n) = phi(2^a).phi(3^b).phi(11^c) 1. Consider 3^b phi(3^b) = (3-1).3^(b-1) = 2.3^(b-1) b has to be 1 since 10 is not divisible by 3. So phi(3^b) = 2 => phi(2^a).phi(11^c) = 5 But phi(n) is always even except for phi(1) and phi(2). Why? Because (p-1) is a factor and each prime except 2 is odd hence phi(n) is even. So b = 0 => phi(n) = phi(2^a).phi(11^c) and n = 2^a.11^c if c = 0 then n = 2^a and phi(n) = (2-1).2^(a-1) which can never be 10. If c >= 2 then...