Browse · MathNet
PrintBulgaria
Bulgaria number theory
Problem
Let be a positive integer. Denote by and respectively the number of all positive integers that divide and the number of all positive integers not greater than and relatively prime to . Find all positive integers having only two prime divisors and such that .
Solution
Let , where are prime numbers, and let . We have that and . Obviously and If , then and (), hence . Therefore and thus . If is a prime and , then . So, and again . Therefore . It follows now that and the equality implies It follows from the formula for that if and , then . i.e. and equality holds only if all prime factors of divide . When and we have Moreover the equality holds if and only if , i.e. . . Hence is a prime number and all prime factors of divide , i.e. . Therefore the desired numbers are all integers of the form , where is a prime number and .
Final answer
All such n are n = 2^{r^t - 1} · 3^{r - 1}, where r is a prime and t is a positive integer.
Techniques
φ (Euler's totient)τ (number of divisors)Prime numbers