Given two positives integers $m$ and $n$, prove that there exists a positive integer $k$ and a set $S$ of at least $m$ multiples of $n$ such that the numbers $\frac {2^k{\sigma({s})}} {s}$ are odd for every $s \in S$. $\sigma({s})$ is the sum of all positive integers of $s$ (1 and $s$ included).
Problem
Source: Romania 2018 TST Problem 4 Day 3
Tags: number theory, sum of divisors
25.05.2020 20:31
Very nice problem ! First of all we build $n^{*} = \prod p_i^{\alpha_i}$ where $p_i$ are all odd prime factors of $n$ and $\alpha _i$ is $1$ if $\nu_{p_i}(n)$ is odd and 0 otherwise. Now we will build our set $S$ with terms of the form $$s = n \cdot n^{*} \cdot 2^t \cdot q$$where $t$ and $q$ are unknwons and $(q,n) = 1$ Let $a = \nu_2(n)$. Note that $\nu_{p_i}(nn^{*})$ is even so $1+p_i+\dots p_i^{\alpha_i}$ is odd . Hence $$\frac{\sigma({s})} {s} = \frac{P\cdot \sigma({q})\cdot (2^{a+t+1}-1)}{n\cdot n^{*} \cdot 2^t \cdot q}$$where $P$ is the product of $1+p_i+\dots p_i^{\alpha_i^{\prime}}$ , divisors of $n\cdot n^{*}$. From our previous observation , $P$ is odd. Now we pick $m$ odd perfect squares $q_i$ with $(q_i,n) = 1$ . Then $\sigma({q_i})$ is also odd , from a similar reason as above. We show that $$t = \prod \phi(\frac{n\cdot n^{*}\cdot q_i}{2^a})-a-1$$and $k = t+a$ work (Note that we can pick $q_i$ large enough to make $t$ positive) It's easy to see this since $$\frac{2^k\cdot \sigma({s})} {s} = \frac{2^k \cdot P\cdot \sigma({q_i})\cdot (2^{a+t+1}-1)}{n\cdot n^{*} \cdot 2^t \cdot q_i} = \frac{2^{a+t+1}-1}{\frac{n}{2^a}\cdot n^{*} \cdot q_i} \cdot {P \cdot \sigma({q_i})} $$which is a positive integer from Euler's Theorem and it's also odd since every term is odd.