v2 of sum of divisors

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

v2 of sum of divisors

G H J

Reveal topic tags

sum of divisors

L

G H BBookmark kLocked kLocked NReply

Source: Romania 2018 TST Problem 4 Day 3

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

141 posts

#1 h May 25, 2020, 4:20 PM

Y by

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).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

RaduAndreiLecoiu

59 posts

RaduAndreiLecoiu

#2 h May 25, 2020, 5:31 PM • 1 Y

Y by parola

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.

This post has been edited 3 times. Last edited by RaduAndreiLecoiu, May 25, 2020, 6:05 PM
Reason: typo

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a