Olympiad Maths Prep

Library / /42 of 45

Number theory Difficulty 7.5 National olympiad, round 2 Prove it Ukraine

For a positive integer nn we write out all its divisors 1=d1<d2<<dk=n1 = d_1 < d_2 < \cdots < d_k = n. A divisor did_i is called a good divisor if di1di+1d_{i-1}d_{i+1} is not divisible by did_i, 2ik12 \le i \le k-1. Find all nn for which the number of their good divisors is smaller than the number of their different prime divisors.

(Mykhailo Shtandenko)

Solution

Answer. pβp^\beta and pαqp^\alpha q, where q>pαq > p^\alpha where p,qp, q are prime numbers.

Solution:

First, let's prove that if a number has at least three different prime divisors, it is not suitable for us. Let mm be the number of different prime divisors and p<qp < q be the two smallest prime divisors of nn. Then it is clear that there exists α\alpha such that the first consecutive divisors of nn will be the numbers 1<p<p2<<pα<q1 < p < p^2 < \cdots < p^\alpha < q. Note that taking as di+1d_{i+1} all prime divisors of nn except for the smallest, we get m1m-1 numbers that satisfy the condition. Indeed, all divisors smaller than a prime number are coprime with that number, so (di,di+1)=1(d_i, d_{i+1}) = 1, and since di1<did_{i-1} < d_i we get the conclusion. It remains to find another good number. Let n:pα+1n : p^{\alpha+1}. Then the divisor qq is a good divisor. Indeed, it cannot be followed by a divisor divisible by qq, because the smallest of these not yet chosen divisors is pqpq, but pα+1<pqp^{\alpha+1} < pq. So pα+1p^{\alpha+1} is the next composite divisor. Then take the last prime number that comes after qq (possibly qq), after which the next composite number will be pα+1p^{\alpha+1}. Then it will be the desired mm-th good number. Now let nn be not divisible by pα+1p^{\alpha+1}. Then the next composite divisor is pqpq. If between qq and pqpq there is at least one prime divisor, then we take the last of them as our mm-th good number. Otherwise, the divisors pα,q,pqp^\alpha, q, pq will be consecutive divisors, and hence npq,nq,npα\frac{n}{pq}, \frac{n}{q}, \frac{n}{p^\alpha} will be consecutive divisors, but then the divisor nq\frac{n}{q} will be the desired one, because since α\alpha is the degree of occurrence of a prime pp in the number nn, npα\frac{n}{p^\alpha} is not divisible by pp, and npq\frac{n}{pq} is not divisible by pαp^\alpha, but nq:pα\frac{n}{q} : p^\alpha, and npα\frac{n}{p^\alpha} is divisible by more than one prime divisor of nn, which means that we have not yet taken it into account, which is what we wanted to prove.

If a number is a power of a prime, then obviously it suits us, because it has no good divisors at all. It remains to consider the case when a number has two different prime divisors, which we denote p<qp < q. Then it is clear that there exists α\alpha that the first consecutive divisors of nn will be the numbers 1<p<p2<<pα<q1 < p < p^2 < \cdots < p^\alpha < q. The divisor pαp^\alpha is a good divisor, which means it is the only good divisor of our number. Hence, the next divisor after qq is a divisor that is divisible by qq, but the smallest such divisor not yet used is pqpq, and therefore it comes after qq. However, pα+1<pqp^{\alpha+1} < pq, and hence our number nn is not divisible by pα+1p^{\alpha+1}. Then, similarly, the divisors npq,nq,npα\frac{n}{pq}, \frac{n}{q}, \frac{n}{p^\alpha} will be consecutive divisors, and the divisor nq\frac{n}{q} will be a good divisor. So, nq=pα\frac{n}{q} = p^\alpha, so n=pαqn = p^\alpha q, and pα<qp^\alpha < q, and the above answer follows. A simple check shows that both answers do indeed satisfy the condition.

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.