Let $n > 1$ be a natural number. We write out the fractions $\frac{1}{n}$, $\frac{2}{n}$, $\dots$ , $\dfrac{n-1}{n}$ such that they are all in their simplest form. Let the sum of the numerators be $f(n)$. For what $n>1$ is one of $f(n)$ and $f(2015n)$ odd, but the other is even?
Problem
Source: All Russian Olympiad 2015 11.2
Tags: number theory
ngv
11.12.2015 23:35
utkarshgupta wrote: Let $n > 1$ be a natural number. We write out the fractions $\frac{1}{n}$, $\frac{2}{n}$, $\dots$ , $\dfrac{n-1}{n}$ such that they are all in their simplest form. Let the sum of the numerators be $f(n)$. For what $n>1$ is one of $f(n)$ and $f(2015n)$ odd, but the other is even? Let $S(n)$ be the sum of the positive integers less than or equal to $n$ and co-prime to $n$. Since $\gcd(a,n)=1\implies\gcd(a,n-a)=1$, by pairing, $S(n)=\dfrac{n\varphi(n)}2$. Then note that, $\sum\limits_{d|n}\varphi(d)=n$ and for any $i\leq n$, $\gcd(i,n)|n$. Therefore, $f(n)=\sum\limits_{d|n}S(d)$. Since $a(n)=n$ and $b(n)=\varphi(n)$ are multiplicative, so is $\sum\limits_{d|n}a(d)b(d)$. Now, use the approach used here: http://www.artofproblemsolving.com/community/q1h1161827p5534620 After you get to prime factorization, it will be easier to look at the parity of both functions.
kreegyt
22.04.2016 20:23
First of all, $\frac{i}{n}$ will have an even numerator if and only if its 2-adic valuation is strictly greater than the 2-adic valuation of n.
Therefore, the parity of f(n) is the same as the parity of $n - 1 - \lfloor { \frac{n}{2^{v2(n)+1}} } \rfloor $
The parity of f(2015n) is the same as the parity of $2015n - 1 - \lfloor { \frac{2015n}{2^{v2(2015n)+1}} } \rfloor $.
Of course, we only have to compare the parity of $ \lfloor { \frac{n}{2^{v2(n)+1}} } \rfloor $ and$ \lfloor { \frac{2015n}{2^{v2(n)+1}} } \rfloor $
let $n = 2^{\alpha}\beta$ with $\beta$ odd.
$ \lfloor { \frac{n}{2^{v2(n)+1}} } \rfloor = \lfloor { \frac{n}{2^{\alpha+1}} } \rfloor = \lfloor { \frac{2^{\alpha}\beta}{2^{\alpha+1}} } \rfloor = \lfloor { \frac{\beta}{2} } \rfloor$. Similarly: $ \lfloor { \frac{2015n}{2^{v2(2015n)+1}} } \rfloor = \lfloor { \frac{2015n}{2^{\alpha+1}} } \rfloor = \lfloor { \frac{2015*2^{\alpha}\beta}{2^{\alpha+1}} } \rfloor = \lfloor { \frac{2015\beta}{2} } \rfloor = \lfloor { 1007\beta + \frac{\beta}{2}} \rfloor $
$\lfloor { 1007\beta + \frac{\beta}{2}} \rfloor $and $\lfloor { \frac{\beta}{2} } \rfloor$ will always have different parities. Therefore all n are solutions.
Is it correct?
Rushery_10
21.04.2022 03:25
redacted.
JAnatolGT_00
22.12.2022 19:28
We claim, that this holds for all $n>1.$ All numbers below are supposed to be nonnegative integers. It's obvious that numbers $\frac{m}{\gcd (m,n)}, \frac{m}{\gcd (m,2015n)}$ has the same parity for $m<n,$ thus it's suffice to prove, that the sum $\sum_{i=1}^{2015n-1}\frac{i}{\gcd (i,2015n)}$ is odd. Note that $2\nmid \frac{i}{\gcd (i,2015n)}\iff v_2(i)\leq v_2(n)\iff i=n+2av_2(n).$ Hence there are exactly $\frac{2014n}{2v_2(n)}$ suitable values of $i,$ which is odd. The conclusion follows.