Maths Olympiad Prep

Library / /9 of 28

Number theory Difficulty 8.2 Shortlist Prove it China

Find all integers k3k \ge 3, with the following properties: There exist integers mm and nn satisfying (m,k)=(n,k)=1(m, k) = (n, k) = 1 and k(m1)(n1)k \mid (m-1)(n-1) with 1<m<k1 < m < k, 1<n<k1 < n < k and m+n>km+n > k.

Solution

If kk has a factor of square number greater than 11, let t2kt^2 \mid k, t>1t > 1, then taking m=n=kkt+1m = n = k - \frac{k}{t} + 1, we see that such kk has the properties.

If kk has no factor of square number, if there are two primes p1,p2p_1, p_2 such that (p12)(p22)4(p_1-2)(p_2-2) \ge 4 and p1p2kp_1 p_2 \mid k. Let k=p1p2prk = p_1 p_2 \cdots p_r and p1,p2,,prp_1, p_2, \dots, p_r be pairwise different, r2r \ge 2. Since there is at least one of (p11)p2p3pr+1(p_1-1)p_2 p_3 \cdots p_r + 1 and (p12)p2p3pr+1(p_1-2)p_2 p_3 \cdots p_r + 1 is coprime with p1p_1 (otherwise p1p_1 divides their difference p2p3prp_2 p_3 \cdots p_r, which is a contradiction), taking this number as the number mm, then, 1<m<k1 < m < k, (m,k)=1(m, k) = 1. Similarly, we can take a number nn of (p21)p1p3pr+1(p_2-1)p_1 p_3 \cdots p_r + 1 or (p22)p1p3pr+1(p_2-2)p_1 p_3 \cdots p_r + 1 such that 1<n<k1 < n < k, (n,k)=1(n, k) = 1. So p1p2pr(m1)(n1)p_1 p_2 \cdots p_r \mid (m-1)(n-1), and
m+n(p12)p2p3pr+1+(p22)p1p3pr+1=k+((p12)(p22)4)p3pr+2>k. m + n \ge (p_1 - 2)p_2 p_3 \cdots p_r + 1 + (p_2 - 2)p_1 p_3 \cdots p_r + 1 \\ = k + ((p_1 - 2)(p_2 - 2) - 4)p_3 \cdots p_r + 2 > k.
Such m,nm, n will satisfy the conditions.

If there are no two primes p1,p2p_1, p_2 such that (p12)(p22)4(p_1-2)(p_2-2) \ge 4, p1p2kp_1 p_2 \mid k, then it is easy to verify such integer k3k \ge 3 can only be 1515, 3030 or as pp, 2p2p (where pp is an odd prime). It is easy to see that, if k=p,2p,30k = p, 2p, 30, then there are no m,nm, n satisfying the conditions; if k=15k = 15, then m=11,n=13m = 11, n = 13 satisfy the conditions.

Summing up, integer k3k \ge 3 satisfies the conditions if and only if kk is not an odd prime, nor double of an odd prime and nor 3030.

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.