Number theoryDifficulty 8.3ShortlistFind the answer
Let S be a set of positive integers, such that n∈S if and only if d∣n,d<n,d∈S∑d≤n Find all positive integers n=2k⋅p where k is a non-negative integer and p is an odd prime, such that d∣n,d<n,d∈S∑d=n
A number or a short expression. Spacing and $ signs are ignored.
Solution
Let S be a set of positive integers such that n∈S if and only if d∣n,d<n,d∈S∑d≤n. We need to find all positive integers n=2k⋅p where k is a non-negative integer and p is an odd prime, such that d∣n,d<n,d∈S∑d=n.
Define the function f(n)=d∣n,d<n,d∈S∑d−n. The given condition translates to n∈S⇔f(n)≤0. Additionally, we have f(n)≤σ(n)−2n, where σ(n) denotes the sum of all positive divisors of n.
First, consider the powers of 2. For any m≥0, f(2m)≤σ(2m)−2m+1=−1, which implies 2m∈S.
Next, observe that 1∈S and for any odd prime p, f(p)=1−2p<0, thus p∈S.
Now, let a=⌊log2(p+1)⌋−1. We claim that for r∈N, 2rp∈/S if and only if a+1∣r.
Proof of Claim:
Write r=x(a+1)−y where 0≤y≤a and x∈N. We proceed by induction on x≥1.
Base Case:
For x=1 and y>0, we have r≤a. Then, f(2rp)≤σ(2rp)−2r+1p=2r+1−p−1≤2a+1−(p+1)≤0, so 2rp∈S for r≤a.
For x=1 and y=0, f(2rp)=f(2a+1p)=σ(2a+1p)−2a+2p=2a+2−(p+1)>0, which means 2a+1p∈/S. This proves the base case.
Inductive Step:
Suppose the result is true for some x. Let r=(x+1)(a+1)−y. If y>0, then r≤(x+1)(a+1)−1. Using the inductive hypothesis, f(2rp)≤σ(2rp)−2r+1p−(2a+1p+22(a+1)p+⋯+2x(a+1)p)=2r+1−1−p−2a+1−12a+1(2x(a+1)−1)p≤(2(x+1)(a+1)−1)−2a+1−1(2(x+1)(a+1)−1)p=(2(x+1)(a+1)−1)(1−2a+1−1p)≤0, so 2rp∈S when y>0.
If y=0, then f(2rp)=σ(2rp)−2r+1p−(2a+1p+22(a+1)p+⋯+2x(a+1)p)=2r+1−1−p−2a+1−12a+1(2x(a+1)−1)p=(2r+1−1)−2a+1−1(2(x+1)(a+1)−1)p≥(2(x+1)(a+1)+1−1)−2(2(x+1)(a+1)−1)=1, thus 2(x+1)(a+1)p∈/S, completing the induction step.
Conclusion:
The problem asks us to find all k and p such that f(2kp)=0. This implies equality must hold at all ≤ signs in the proof of the lemma above. The last equality holds only if p=2a+1−1. Also, the second equality holds when y=1, i.e., r+1=x(a+1) for some positive integer x.
Therefore, all solutions are of the form k=x(a+1)−1 and p=2a+1−1 for a,x∈N.
The answer is: \boxed{k = x(a+1) - 1 \text{ and } p = 2^{a+1} - 1 \text{ for } a, x \in \mathbb{N}}.
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.