Maths Olympiad Prep

Library / /34 of 42

Number theory Difficulty 6.8 National olympiad Prove it Romania

We will say that the positive integers mm and nn have property P\mathcal{P} if for every divisor d1d_1 of mm and every divisor d2d_2 of nn, the number d1+d2d_1 + d_2 is a prime.

a) Prove that if mm and nn have property P\mathcal{P} and are different, then m+nm+n is odd.

b) Find all the pairs (m,n)(m, n) of positive integers mnm \le n, having property P\mathcal{P}.

Solution

a) Without loss of generality, we may suppose 1m<n1 \le m < n.
If mm and nn are odd, then m1m \ge 1 and n3n \ge 3. Taking d1=1d_1 = 1 and d2=nd_2 = n yields d1+d2=n+1d_1 + d_2 = n + 1, which is an even number at least 44, so it is composite, contradiction.
If mm and nn are even, taking d1=2d_1 = 2 and d2=2d_2 = 2 yields d1+d2=4d_1 + d_2 = 4, contradiction.
In conclusion mm and nn have different parities, so m+nm + n is odd.

b) If m=nm = n, then d1=md_1 = m and d2=nd_2 = n leads to d1+d2=2md_1 + d_2 = 2m, which must be a prime, hence m=n=1m = n = 1.
If m<nm < n, then mnm \neq n and, from a), mm and nn have different parities.

* If mm is even and nn is odd, then m2m \ge 2 and n3n \ge 3. Then d1=1d_1 = 1 and d2=nd_2 = n yields d1+d2=n+14d_1 + d_2 = n + 1 \ge 4, contradiction.
* If mm is odd and nn is even, then m1m \ge 1 and n2n \ge 2. Take aNa \in \mathbb{N}^* and bb odd such that n=2abn = 2^a \cdot b.

I. If a3a \ge 3, then 88 divides nn and, taking d1=1d_1 = 1 and d2=8d_2 = 8 yields d1+d2=9d_1 + d_2 = 9, contradiction.

II. If a=1a = 1, then n=2bn = 2b, with odd bb.

i) If b3b \ge 3, then take d1=1d_1 = 1 and d2=bd_2 = b to get d1+d2=b+14d_1 + d_2 = b + 1 \ge 4, contradiction.

ii) If b=1b = 1, then n=2n = 2 and, since m<nm < n and mm is odd, m=1m = 1. It is easy to check that the pair (m,n)=(1,2)(m, n) = (1, 2) is a solution.

III. If a=2a = 2, then n=4bn = 4b, with odd bb.

i) If b3b \ge 3, then d1=1d_1 = 1 and d2=bd_2 = b yields d1+d2=b+14d_1 + d_2 = b + 1 \ge 4, contradiction.

ii) If b=1b = 1, then n=4n = 4 and, since m<nm < n and mm is odd, m{1,3}m \in \{1, 3\}. It is easy to check that only (m,n)=(1,4)(m, n) = (1, 4) satisfies the statement.

Finally, the solutions are (1,1)(1, 1), (1,2)(1, 2), (1,4)(1, 4).

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.