Maths Olympiad Prep

Library / /51 of 106

Number theory Difficulty 8.4 Shortlist Find the answer

Determine all composite integers n>1n>1 that satisfy the following property: if d1d_1, d2d_2, \ldots, dkd_k are all the positive divisors of nn with 1=d1<d2<<dk=n1 = d_1 < d_2 < \cdots < d_k = n, then did_i divides di+1+di+2d_{i+1} + d_{i+2} for every 1ik21 \leq i \leq k - 2.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

To solve the problem, we analyze the divisors of a composite integer n n and determine for which n n the divisibility condition holds.

Let n n be a composite integer with the positive divisors d1,d2,,dk d_1, d_2, \ldots, d_k such that 1=d1<d2<<dk=n 1 = d_1 < d_2 < \cdots < d_k = n . We must check that for every 1ik2 1 \leq i \leq k - 2 , di d_i divides di+1+di+2 d_{i+1} + d_{i+2} .

First, consider the case where n=pm n = p^m for some prime p p and integer m2 m \geq 2 . The divisors of n n are 1,p,p2,,pm 1, p, p^2, \ldots, p^m .

For each i i , the divisibility condition is:
didi+1+di+2. d_i \mid d_{i+1} + d_{i+2}.
Substituting the divisors gives:
pi1pi+pi+1. p^{i-1} \mid p^i + p^{i+1}.
Simplifying, we have:
pi1pi(1+p), p^{i-1} \mid p^i (1 + p),
which holds true because pi1 p^{i-1} clearly divides pi p^i .

Therefore, if n=pm n = p^m for some prime p p and integer m2 m \geq 2 , the condition is satisfied.

Now, assume n n has at least two distinct prime factors, say n=paqb n = p^a q^b for distinct primes p p and q q . The divisors include 1,p,q,pq,p2,q2, 1, p, q, pq, p^2, q^2,\ldots .

Consider n=6=23 n = 6 = 2 \cdot 3 as a small example. The divisors are 1,2,3,6 1, 2, 3, 6 , and for i=1 i = 1 , d1=1 d_1 = 1 should divide d2+d3=2+3=5 d_2 + d_3 = 2 + 3 = 5 , which it does. For i=2 i = 2 , d2=2 d_2 = 2 should divide d3+d4=3+6=9 d_3 + d_4 = 3 + 6 = 9 , which is not divisible by 2.

Hence, having multiple distinct prime factors can violate the divisibility condition, verifying that only numbers of the form n=pm n = p^m satisfy the given property.

The solution is that n n must be of the form:
n=pm for some prime p and integer m2. \boxed{n = p^m \text{ for some prime } p \text{ and integer } m \geq 2.}

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.