Determine all positive, composite integers n that satisfy the following property: if the positive divisors of n are 1=d1<d2<⋯<dk=n, then di divides di+1+di+2 for every 1⩽i⩽k−2.
Solution
Answer: n=pr is a prime power for some r⩾2.
Solution 1. It is easy to see that such an n=pr with r⩾2 satisfies the condition as di=pi−1 with 1⩾i⩾k=r+1 and clearly pi−1∣pi+pi+1 Now, let us suppose that there is a positive integer n that satisfies the divisibility condition of the problem and that has two different prime divisors p and q. Without loss of generality, we assume p<q and that they are the two smallest prime divisors of n. Then there is a positive integer j such that d1=1,d2=p,…,dj=pj−1,dj+1=pj,dj+2=q and it follows that dk−j−1=qn,dk−j=pjn,dk−j+1=pj−1n,…,dk−1=pn,dk=n Thus dk−j−1=qndk−j+dk−j+1=pjn+pj−1n=pjn(p+1)(1) This gives pj∣q(p+1), which is a contradiction since gcd(p,p+1)=1 and p=q.
Solution 2. Since didk+1−i=n, we have the equivalence: dk−i−1dk−i+dk−i+1⟺di+2ndi+1n+din We multiply both sides by didi+1di+2 and cancel the n's to get didi+1∣didi+2+di+1di+2 Hence, di∣di+1di+2(2) Moreover, by the condition of the problem, di∣di+1(di+1+di+2)=di+12+di+1di+2 Combining this with (2) we get that di∣di+12 for all 1⩽i⩽k−2. Let d2=p be the smallest prime divisor of n. By induction on i we prove that p∣di for all 2⩽i⩽k−1. The base case d2=p is obvious. Let us suppose that p∣dj for some 2⩽j⩽k−2. Then we have that p∣dj∣dj+12⟹p∣dj+1 as p is prime, which completes the induction. This implies that n has to be a prime power, as otherwise there would be another prime q that divides n and we would get that p∣q which is obviously false. We finally check that the powers of p satisfy the condition in the statement of the problem as in Solution 1.
Solution 3. We start by proving the following claim: Claim. di∣di+1 for every 1⩽i⩽k−1. Proof. We prove the Claim by induction on i; it is trivial for i=1 because d1=1. Suppose that 2⩽i⩽k−1 and the Claim is true for i−1, i.e. di−1∣di. By the induction hypothesis and the problem condition, di−1∣di and di−1∣di+di+1, so di−1∣di+1. Now consider the divisors dk−i=di+1n,dk−i+1=din,dk−i+2=di−1n. By the problem condition, dk−idk−i+1+dk−i+2=di+1ndin+di−1n=didi+1+di−1di+1 is an integer. We conclude that didi+1 is an integer, so di∣di+1. By the Claim, n cannot have two different prime divisors because the smallest one would divide the other one. Hence, n must be a power of a prime, and powers of primes satisfy the condition of the problem as we saw in Solution 1.
Solution 4. We present here a more technical way of finishing Solution 1 after obtaining (1). We let vp(m) denote the p-adic valuation of m. Notice that vp(n/q)=vp(n) as gcd(p,q)=1 and that vp(pjn(p+1))=vp(n)−j as gcd(p,p+1)=1. But (1) implies vp(n)=vp(n/q)⩽vp(pjn(p+1))=vp(n)−j which is a contradiction. Thus n has only one prime divisor as desired.
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.