Olympiad Maths Prep

Library / /6 of 14

Number theory Difficulty 6.3 National olympiad Prove it Czech Republic

Find all positive integers nn which are not powers of 22 and which satisfy the equation n=3D+5dn = 3D + 5d, where DD (and dd) denote the greatest (and the least) numbers among all odd divisors of nn which are larger than 11.
(Tomáš Jurík)

Solutions — 2

Solution 1

Let n=p1α1p2α2pkαkn = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k} be the prime factorization of a satisfactory number nn. Here p1<p2<<pkp_1 < p_2 < \dots < p_k are all the prime divisors of nn and the exponents αi\alpha_i are positive integers. The given equation implies that p1=2p_1 = 2 (otherwise D=nD = n which contradicts to n=3D+5dn = 3D + 5d) and that k2k \ge 2 (otherwise nn is a power of 22). Thus we have D=p2α2pkαkD = p_2^{\alpha_2} \dots p_k^{\alpha_k}, d=p2d = p_2 and the equation becomes
2α1p2α2pkαk=3p2α2pkαk+5p2or(2α13)p2α21pkαk=5. 2^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k} = 3 p_2^{\alpha_2} \dots p_k^{\alpha_k} + 5p_2 \quad \text{or} \quad (2^{\alpha_1} - 3) p_2^{\alpha_2 - 1} \dots p_k^{\alpha_k} = 5.
(In the case when k=2k=2 the left-hand of the last equation is simply (2α13)p2α21(2^{\alpha_1} - 3)p_2^{\alpha_2-1}.)
Since the number 55 has only two divisors 11 and 55, it holds that 2α13{1,5}2^{\alpha_1} - 3 \in \{1, 5\} and
hence either α1=2\alpha_1 = 2 or α1=3\alpha_1 = 3.

i. The case α1=2\alpha_1 = 2. The simplified equation
p2α21pkαk=5 p_2^{\alpha_2-1} \dots p_k^{\alpha_k} = 5
holds if and only if either k=2k=2, p2=5p_2=5 and α21=1\alpha_2 - 1 = 1, or k=3k=3, α21=0\alpha_2 - 1 = 0, p3=5p_3 = 5 and α3=1\alpha_3 = 1 — then from 2<p2<p3=52 < p_2 < p_3 = 5 it follows that p2=3p_2 = 3. Consequently, there are exactly two solutions in the case (i), namely n=2252=100n = 2^2 5^2 = 100 and n=223151=60n = 2^2 3^1 5^1 = 60.

ii. The case α1=3\alpha_1 = 3. The simplified equation
p2α21pkαk=1 p_2^{\alpha_2-1} \dots p_k^{\alpha_k} = 1
holds only for k=2k=2 and α21=0\alpha_2 - 1 = 0. Notice that there is no restriction on the prime number p2p_2 excepting the inequality p2>2p_2 > 2. Consequently, there are infinitely many solutions in the case (ii) and all of them are given by n=23p21=8p2n = 2^3 p_2^1 = 8p_2, where p2p_2 is any odd prime number.

Answer. All the solutions nn are: n=60n = 60, n=100n = 100 and n=8pn = 8p, where pp is any odd prime number.

Solution 2

The given equation n=3D+5dn = 3D + 5d implies that n>3Dn > 3D and n3D+5D=8Dn \le 3D + 5D = 8D (because of dDd \le D). Since the ratio n:Dn:D must be a power of 22, it follows from 3<n:D83 < n: D \le 8 that either (i) n=4Dn = 4D, or (ii) n=8Dn = 8D.

i. The case n=4Dn = 4D. From 4D=n=3D+5d4D = n = 3D + 5d we have D=5dD = 5d and thus n=4D=20dn = 4D = 20d. Since dd must be a prime odd divisor of nn which is a multiple of 55, we conclude that p{3,5}p \in \{3, 5\} and hence n{60,100}n \in \{60, 100\} (both the values are clearly satisfactory).

ii. n=8Dn = 8D. Our way of deriving the inequality n8Dn \le 8D implies now that D=dD = d and hence DD is an (odd) prime number. All such n=8Dn = 8D are solutions indeed.

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.