Maths Olympiad Prep

Library / /48 of 144

Number theory Difficulty 8.0 National olympiad, round 2 Find the answer

Determine all pairs (n,k)(n, k) of distinct positive integers such that there exists a positive integer ss for which the number of divisors of snsn and of sksk are equal.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Given the problem, we need to determine all pairs (n,k)(n, k) of distinct positive integers such that there exists a positive integer s s for which the number of divisors of sn sn and sk sk are equal.

To solve this problem, we use the property that the number of divisors d(x) d(x) of an integer x x is determined by its prime factorization. Suppose n=p1a1p2a2prar n = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r} and k=q1b1q2b2qtbt k = q_1^{b_1} q_2^{b_2} \cdots q_t^{b_t} where pi p_i and qi q_i are primes.

d(sn)=d(s)d(n)andd(sk)=d(s)d(k). d(sn) = d(s) \cdot d(n) \quad \text{and} \quad d(sk) = d(s) \cdot d(k).

Given d(sn)=d(sk) d(sn) = d(sk) , we have:

d(n)=d(k). d(n) = d(k).

This means that n n and k k must have the same divisor count. If n=p1a1p2a2prar n = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r} and k=q1b1q2b2qtbt k = q_1^{b_1} q_2^{b_2} \cdots q_t^{b_t} , then:

(a1+1)(a2+1)(ar+1)=(b1+1)(b2+1)(bt+1). (a_1 + 1)(a_2 + 1) \cdots (a_r + 1) = (b_1 + 1)(b_2 + 1) \cdots (b_t + 1).

For the pair (n,k)(n, k) to satisfy d(n)=d(k) d(n) = d(k) with a valid s s , n n and k k should not be related as divisibility by each other; otherwise, one would directly have a greater count of divisors through multiplication by any factor s s that includes extra prime factors from n n or k k .

Thus, a necessary condition is that neither integer divides the other, ensuring complete freedom in choosing s s to balance out the divisor counts.

Therefore, all pairs (m,n)(m, n) satisfying the conditions are those for which:
mnandnm. m \nmid n \quad \text{and} \quad n \nmid m.

The solution is given by:
all pairs (m,n) such that mn,nm. \boxed{\text{all pairs } (m, n) \text{ such that } m \nmid n, n \nmid m.}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.