Maths Olympiad Prep

Library / /54 of 61

Number theory Difficulty 7.5 National Olympiad, round 2 Prove it Canada

Problem:

Two positive integers aa and bb are prime-related if a=pba = p b or b=pab = p a for some prime pp. Find all positive integers nn, such that nn has at least three divisors, and all the divisors can be arranged without repetition in a circle so that any two adjacent divisors are prime-related.

Note that 11 and nn are included as divisors.

Solution

Solution:

We say that a positive integer is good if it has the given property. Let nn be a good number, and let d1,d2,,dkd_{1}, d_{2}, \ldots, d_{k} be the divisors of nn in the circle, in that order. Then for all 1ik1 \leq i \leq k, di+1/did_{i+1} / d_{i} (taking the indices modulo kk) is equal to either pip_{i} or 1/pi1 / p_{i} for some prime pip_{i}. In other words, di+1/di=piϵid_{i+1} / d_{i} = p_{i}^{\epsilon_{i}}, where ϵi{1,1}\epsilon_{i} \in \{1, -1\}. Then
p1ϵ1p2ϵ2pkϵk=d2d1d3d2d1dk=1 p_{1}^{\epsilon_{1}} p_{2}^{\epsilon_{2}} \cdots p_{k}^{\epsilon_{k}} = \frac{d_{2}}{d_{1}} \cdot \frac{d_{3}}{d_{2}} \cdots \frac{d_{1}}{d_{k}} = 1
For the product p1ϵ1p2ϵ2pkϵkp_{1}^{\epsilon_{1}} p_{2}^{\epsilon_{2}} \cdots p_{k}^{\epsilon_{k}} to equal 11, any prime factor pp must be paired with a factor of 1/p1/p, and vice versa, so kk (the number of divisors of nn) must be even. Hence, nn cannot be a perfect square.

Furthermore, nn cannot be the power of a prime (including a prime itself), because 11 always is a divisor of nn, and if nn is a power of a prime, then the only divisor that can go next to 11 is the prime itself.

Now, let n=paqbn = p^{a} q^{b}, where pp and qq are distinct primes, and aa is odd. We write the divisors of nn in a grid as follows: In the first row, write the numbers 1,q,q2,,qb1, q, q^{2}, \ldots, q^{b}. In the next row, write the numbers p,pq,pq2,,pqbp, p q, p q^{2}, \ldots, p q^{b}, and so on. The number of rows in the grid, a+1a+1, is even. Note that if two squares are adjacent vertically or horizontally, then their corresponding numbers are prime-related. We start with the square with a 11 in the upper-left corner. We then move right along the first row, move down along the last column, move left along the last row, then zig-zag row by row, passing through every square, until we land on the square with a pp. The following diagram gives the path for a=3a=3 and b=5b=5:

Figure 1

Thus, we can write the divisors encountered on this path in a circle, so n=paqbn = p^{a} q^{b} is good.

Next, assume that nn is a good number. Let d1,d2,,dkd_{1}, d_{2}, \ldots, d_{k} be the divisors of nn in the circle, in that order. Let pp be a prime that does not divide nn. We claim that npen \cdot p^{e} is also a good number. We arrange the divisors of npen \cdot p^{e} that are not divisors of nn in a grid as follows:
d1pd1p2d1ped2pd2p2d2pedkpdkp2dkpe \begin{array}{cccc} d_{1} p & d_{1} p^{2} & \ldots & d_{1} p^{e} \\ d_{2} p & d_{2} p^{2} & \ldots & d_{2} p^{e} \\ \vdots & \vdots & \ddots & \vdots \\ d_{k} p & d_{k} p^{2} & \ldots & d_{k} p^{e} \end{array}
Note that if two squares are adjacent vertically or horizontally, then their corresponding numbers are prime-related. Also, kk (the number of rows) is the number of factors of nn, which must be even (since nn is good). Hence, we can use the same path described above, which starts at d1pd_{1} p and ends at d2pd_{2} p. Since d1d_{1} and d2d_{2} are adjacent divisors in the circle for nn, we can insert all the divisors in the grid above between d1d_{1} and d2d_{2}, to obtain a circle for npen \cdot p^{e}.

Finally, let nn be a positive integer that is neither a perfect square nor a power of a prime. Let the prime factorization of nn be
n=p1e1p2e2ptet n = p_{1}^{e_{1}} p_{2}^{e_{2}} \cdots p_{t}^{e_{t}}
Since nn is not the power of a prime, t2t \geq 2. Also, since nn is not a perfect square, at least one exponent eie_{i} is odd. Without loss of generality, assume that e1e_{1} is odd. Then from our work above, p1e1p2e2p_{1}^{e_{1}} p_{2}^{e_{2}} is good, so p1e1p2e2p3e3p_{1}^{e_{1}} p_{2}^{e_{2}} p_{3}^{e_{3}} is good, and so on, until n=p1e1p2e2ptetn = p_{1}^{e_{1}} p_{2}^{e_{2}} \cdots p_{t}^{e_{t}} is good.

Therefore, a positive integer nn has the given property if and only if it is neither a perfect square nor a power of a prime.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.