Maths Olympiad Prep

Library / /73 of 97

Number theory Difficulty 8.3 Shortlist Find the answer

Let SS be a set of positive integers, such that nSn \in S if and only if dn,d<n,dSdn\sum_{d|n,d<n,d \in S} d \le n
Find all positive integers n=2kpn=2^k \cdot p where kk is a non-negative integer and pp is an odd prime, such that dn,d<n,dSd=n\sum_{d|n,d<n,d \in S} d = n

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let S S be a set of positive integers such that nS n \in S if and only if
dn,d<n,dSdn. \sum_{d \mid n, d < n, d \in S} d \leq n.
We need to find all positive integers n=2kp n = 2^k \cdot p where k k is a non-negative integer and p p is an odd prime, such that
dn,d<n,dSd=n. \sum_{d \mid n, d < n, d \in S} d = n.

Define the function
f(n)=(dn,d<n,dSd)n. f(n) = \left( \sum_{d \mid n, d < n, d \in S} d \right) - n.
The given condition translates to nSf(n)0 n \in S \Leftrightarrow f(n) \leq 0 . Additionally, we have f(n)σ(n)2n f(n) \leq \sigma(n) - 2n , where σ(n) \sigma(n) denotes the sum of all positive divisors of n n .

First, consider the powers of 2. For any m0 m \geq 0 ,
f(2m)σ(2m)2m+1=1, f(2^m) \leq \sigma(2^m) - 2^{m+1} = -1,
which implies 2mS 2^m \in S .

Next, observe that 1S 1 \in S and for any odd prime p p ,
f(p)=12p<0, f(p) = 1 - 2p < 0,
thus pS p \in S .

Now, let a=log2(p+1)1 a = \lfloor \log_2(p+1) \rfloor - 1 . We claim that for rN r \in \mathbb{N} , 2rpS 2^r p \notin S if and only if a+1r a+1 \mid r .

Proof of Claim:

Write r=x(a+1)y r = x(a+1) - y where 0ya 0 \leq y \leq a and xN x \in \mathbb{N} . We proceed by induction on x1 x \geq 1 .

Base Case:

For x=1 x = 1 and y>0 y > 0 , we have ra r \leq a . Then,
f(2rp)σ(2rp)2r+1p=2r+1p12a+1(p+1)0, f(2^r p) \leq \sigma(2^r p) - 2^{r+1} p = 2^{r+1} - p - 1 \leq 2^{a+1} - (p + 1) \leq 0,
so 2rpS 2^r p \in S for ra r \leq a .

For x=1 x = 1 and y=0 y = 0 ,
f(2rp)=f(2a+1p)=σ(2a+1p)2a+2p=2a+2(p+1)>0, f(2^r p) = f(2^{a+1} p) = \sigma(2^{a+1} p) - 2^{a+2} p = 2^{a+2} - (p + 1) > 0,
which means 2a+1pS 2^{a+1} p \notin S . This proves the base case.

Inductive Step:

Suppose the result is true for some x x . Let r=(x+1)(a+1)y r = (x+1)(a+1) - y . If y>0 y > 0 , then r(x+1)(a+1)1 r \leq (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+11p2a+1(2x(a+1)1)p2a+11(2(x+1)(a+1)1)(2(x+1)(a+1)1)p2a+11=(2(x+1)(a+1)1)(1p2a+11)0, \begin{align*} f(2^r p) &\leq \sigma(2^r p) - 2^{r+1} p - \left( 2^{a+1} p + 2^{2(a+1)} p + \dots + 2^{x(a+1)} p \right) \\ &= 2^{r+1} - 1 - p - \frac{2^{a+1} (2^{x(a+1)} - 1) p}{2^{a+1} - 1} \\ &\leq (2^{(x+1)(a+1)} - 1) - \frac{(2^{(x+1)(a+1)} - 1) p}{2^{a+1} - 1} \\ &= (2^{(x+1)(a+1)} - 1) \left( 1 - \frac{p}{2^{a+1} - 1} \right) \leq 0, \end{align*}
so 2rpS 2^r p \in S when y>0 y > 0 .

If y=0 y = 0 , then
f(2rp)=σ(2rp)2r+1p(2a+1p+22(a+1)p++2x(a+1)p)=2r+11p2a+1(2x(a+1)1)p2a+11=(2r+11)(2(x+1)(a+1)1)p2a+11(2(x+1)(a+1)+11)2(2(x+1)(a+1)1)=1, \begin{align*} f(2^r p) &= \sigma(2^r p) - 2^{r+1} p - \left( 2^{a+1} p + 2^{2(a+1)} p + \dots + 2^{x(a+1)} p \right) \\ &= 2^{r+1} - 1 - p - \frac{2^{a+1} (2^{x(a+1)} - 1) p}{2^{a+1} - 1} \\ &= (2^{r+1} - 1) - \frac{(2^{(x+1)(a+1)} - 1) p}{2^{a+1} - 1} \\ &\geq (2^{(x+1)(a+1) + 1} - 1) - 2(2^{(x+1)(a+1)} - 1) = 1, \end{align*}
thus 2(x+1)(a+1)pS 2^{(x+1)(a+1)} p \notin S , completing the induction step.

Conclusion:

The problem asks us to find all k k and p p such that f(2kp)=0 f(2^k p) = 0 . This implies equality must hold at all \leq signs in the proof of the lemma above. The last equality holds only if p=2a+11 p = 2^{a+1} - 1 . Also, the second equality holds when y=1 y = 1 , i.e., r+1=x(a+1) r + 1 = x(a+1) for some positive integer x x .

Therefore, all solutions are of the form k=x(a+1)1 k = x(a+1) - 1 and p=2a+11 p = 2^{a+1} - 1 for a,xN a, x \in \mathbb{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.