Number theoryDifficulty 6.3National olympiadProve itCzech Republic
**Find all functions f:N→N such that for every positive integer m the following is true: If we denote by d1,d2,…,dn all the divisors of number m then** f(d1)⋅f(d2)⋯f(dn)=m.
Solution
We will show that the only solution is a function f such that f(m)={p,1,if m is a non-trivial power of a prime p, i.e. m=pk,k≥1,otherwise. Number 1 has the unique divisor 1, hence plugging m=1 in the given equality we get f(1)=1. Let m=p be a prime. Then f(1)⋅f(p)=pi.e.f(p)=p. For m=p2 we get f(1)⋅f(p)⋅f(p2)=p2i.e.f(p2)=p and in general for k>1 and m=pk f(1)⋅f(p)⋅f(p2)⋯f(pk)=pk. By induction, f(pk)=p for all positive integers k. Now let us consider positive integer m with at least two distinct prime factors whose factorization is m=p1α1p2α2…pkαk, where k≥2 and αi≥1 for every i∈{1,2,…,k}. The divisors of m include the powers p1,p12,…,p1α1,p2,p22,…,p2α2,…,pk,pk2,…,pkαk, of its prime factors but the product of the corresponding function values f(p1)f(p12)…f(p1α1)f(p2)f(p22)…f(p2α2)…f(pk)f(pk2)…f(pkαk)=α1p1p1…p1α2p2p2…p2…αkpkpk…pk=p1α1p2α2…pkαk=m yields m. This means that the product of all the other function values (none of which is a non-trivial power of a prime), including f(m), is equal to 1 so all the other function values, including f(m), are equal to 1. This specifies f uniquely and also shows that it has the desired properties.
Looking for a route rather than an archive? The track puts 2,000
problems in a working order, from AMC 10 level to the IMO shortlist.
Source: MathNet,
licensed CC-BY-4.0.
Statement and solution reproduced as published; topic and difficulty added by this site.