Let $n$ be a positive integer and let $d_1, d_2, \dots, d_k$ be its positive divisors. Consider the number $$f(n) = (-1)^{d_1}d_1 + (-1)^{d_2}d_2 + \dots + (-1)^{d_k}d_k$$Assume $f(n)$ is a power of 2. Show if $m$ is an integer greater than 1, then $m^2$ does not divide $n$.
Problem
Source: Mexico National Olympiad 2015 Problem 6
Tags: number theory
djmathman
25.11.2015 05:20
Can someone check this solution? I'm not sure this is entirely correct. (Sorry for deleting this earlier - I somehow thought $(-1)^1=1$ so I thought my solution was completely broken )
Rewrite as \[f(n)=\sum_{d|n}(-1)^dd.\]Remark that the function $g(n)=(-1)^nn$ is multiplicative (this is easy to check), and so we can write \[\sum_{d|n}(-1)^dd=\prod_{p|n}\sum_{i=0}^{\nu_p(n)}(-1)^{p^i}p^i.\]Note that this is a power of two if and only if each of its parts is a power of $2$, so it suffices to prove the proposition for $n$ a power of a prime. This has the advantage that $(-1)^{p^i}=(-1)^{p^j}$ for all $i$ and $j$; because of this, it suffices to show that if \[1+p+\cdots+p^k=2^m\]for some positive integer $m$, then $k\leq 1$.
(Actually, the above isn't quite true; it's only true when $p$ is odd, since then $(-1)^1$ and $(-1)^p$ will be equal. The case $p=2$ is separate; however, upon closer inspection it's trivial due to parity.)
Now assume that $p$ is a prime greater than or equal to $3$. Remark that \[1+p+p^2+\cdots+p^k=\dfrac{p^{k+1}-1}{p-1}.\]By LTE, \begin{align*}\nu_2\left(\dfrac{p^{k+1}-1}{p-1}\right)&=\nu_2\left(p^{k+1}-1\right)-\nu_2(p-1)\\&=\nu_2(p-1)+\nu_2(p+1)+\nu_2(k+1)-1-\nu_2(p-1)\\&=\nu_2(p+1)+\nu_2(k+1)-1.\end{align*}Thus, if $1+p+\cdots+p^k$ is a power of $2$, we must have \[\dfrac{p^{k+1}-1}{p-1}=2^{\nu_2(p+1)+\nu_2(k+1)-1}=2^{\nu_2[(p+1)(k+1)]-1}.\]Note that $\nu_2(n)\leq\log_2(n)$ for all $n$, so \[2^{\nu_2[(p+1)(k+1)]-1}\leq 2^{\log_2[(p+1)(k+1)]-1}=\dfrac12(p+1)(k+1),\]which implies \[\dfrac{p^{k+1}-1}{p^2-1}\leq\dfrac{k+1}2.\]This inequality is extremely false for $k\geq 2$; note that the LHS is asymptotic to $p^{k-1}$ and the RHS is linear in $k$, and a simple check shows that the base case of $k=2$ is false for $p\geq 3$, so the only possibility is when $k\leq 1$ as desired.
XmL
25.11.2015 06:01
djmathman wrote:
it suffices to show that if \[1+p+\cdots+p^k=2^m\]for some positive integer $m$, then $k\leq 1$.
(Actually, the above isn't quite true; it's only true when $p$ is odd, since then $(-1)^1$ and $(-1)^p$ will be equal. The case $p=2$ is separate; however, upon closer inspection it's trivial due to parity.)
Here's a proof of this cool lemma without using LTE: First note that $k+1$ cannot have an odd prime divisor. If it does and say that odd $a|k+1$, then it is necessary for $\frac {p^a-1}{p-1}=p^{a-1}+p^{a-2}+...+1$ to be a power of two because it divides $p^{k+1}-1$, but this cannot happen because the term is clearly odd. Thus $k+1=2^t$. Note that $p^{2^{t-1}}+1|\frac {p^{k+1}-1}{p-1}$ so it must be a power of two, but $p^{2^{t-1}}+1\equiv 2 \mod 4$ for $t>1$ and it is clearly greater than $2$, therefore $t=1$ and $k=1$
suli
29.11.2015 19:26
djmathman wrote: Can someone check this solution? I'm not sure this is entirely correct. (Sorry for deleting this earlier - I somehow thought $(-1)^1=1$ so I thought my solution was completely broken )
Rewrite as \[f(n)=\sum_{d|n}(-1)^dd.\]Remark that the function $g(n)=(-1)^nn$ is multiplicative (this is easy to check), and so we can write \[\sum_{d|n}(-1)^dd=\prod_{p|n}\sum_{i=0}^{\nu_p(n)}(-1)^{p^i}p^i.\]Note that this is a power of two if and only if each of its parts is a power of $2$, so it suffices to prove the proposition for $n$ a power of a prime. This has the advantage that $(-1)^{p^i}=(-1)^{p^j}$ for all $i$ and $j$; because of this, it suffices to show that if \[1+p+\cdots+p^k=2^m\]for some positive integer $m$, then $k\leq 1$.
(Actually, the above isn't quite true; it's only true when $p$ is odd, since then $(-1)^1$ and $(-1)^p$ will be equal. The case $p=2$ is separate; however, upon closer inspection it's trivial due to parity.)
Now assume that $p$ is a prime greater than or equal to $3$. Remark that \[1+p+p^2+\cdots+p^k=\dfrac{p^{k+1}-1}{p-1}.\]By LTE, \begin{align*}\nu_2\left(\dfrac{p^{k+1}-1}{p-1}\right)&=\nu_2\left(p^{k+1}-1\right)-\nu_2(p-1)\\&=\nu_2(p-1)+\nu_2(p+1)+\nu_2(k+1)-1-\nu_2(p-1)\\&=\nu_2(p+1)+\nu_2(k+1)-1.\end{align*}Thus, if $1+p+\cdots+p^k$ is a power of $2$, we must have \[\dfrac{p^{k+1}-1}{p-1}=2^{\nu_2(p+1)+\nu_2(k+1)-1}=2^{\nu_2[(p+1)(k+1)]-1}.\]Note that $\nu_2(n)\leq\log_2(n)$ for all $n$, so \[2^{\nu_2[(p+1)(k+1)]-1}\leq 2^{\log_2[(p+1)(k+1)]-1}=\dfrac12(p+1)(k+1),\]which implies \[\dfrac{p^{k+1}-1}{p^2-1}\leq\dfrac{k+1}2.\]This inequality is extremely false for $k\geq 2$; note that the LHS is asymptotic to $p^{k-1}$ and the RHS is linear in $k$, and a simple check shows that the base case of $k=2$ is false for $p\geq 3$, so the only possibility is when $k\leq 1$ as desired.
$g(n) = (-1)^n n$ is not multiplicative: $g(3) g(5) = -g(15).$ Instead, we can bypass multiplicativity using the fact that the desired sum is the sum of factors minus twice the sum of odd factors, or if $n = 2^{e_1} p_2^{e_2} \dots p_k^{e_k}$: $$(-1 + 2 + 4 + \dots + 2^{e_1})(1 + p_2 + p_2^2 + \dots + p_2^{e_2}) \dots (1 + p_k + p_k^2 + \dots + p_k^{e_k}).$$Then each term is a power of $2$, so we conclude that each $e_i = 1$ by using lifting the exponent lemma and bounding.
djmathman
30.11.2015 02:12
^^ Right, okay, $g(n)$ is not multiplicative. Whoops! Interestingly enough, though, this doesn't seem to affect anything, in the sense that $$(-1 + 2 + 4 + \dots + 2^{e_1})(1 + p_2 + p_2^2 + \dots + p_2^{e_2}) \dots (1 + p_k + p_k^2 + \dots + p_k^{e_k})$$is the same expression you get after assuming multiplicativity and breaking up the sum into products of relatively prime factors. Does this just happen to be a coincidence, or is it based off the fact that $g(n)$ is "almost" multiplicative?
suli
30.11.2015 02:59
What you do is disregard the $(-1)^n$ term and find a multiplicative expression for the $n$ part (which is easy); then, add some + and - signs somewhere and prove the identity holds by expanding everything.
Math_CYCR
30.11.2015 04:32
Proposed by Irving Calderon
codyj
30.11.2015 19:35
for odd $m$, \[f(2^nm)=\sum_{i=0}^n\sum_{d\mid m}(-1)^{2^id}2^id=-\sum_{d\mid m}d+\sum_{i=1}^n\sum_{d\mid m}2^id=(2^{n+1}-3)\sum_{d\mid m}d\] so $n=1$. also \[\sum_{d\mid m}d=\prod_i\frac{p_i^{\alpha_i+1}-1}{p_i-1}\] which forces $\alpha_i=1$ else Zsigmondy contradicts
codyj
30.11.2015 19:37
alternate finish: $\frac{p^\alpha-1}{p-1}=1+p+\dots+p^\alpha=2^r$. If $\alpha$ is odd then the LHS is odd. if $\alpha$ is even then $1+p^2$ divides the LHS. so $\alpha=1$
suli
01.12.2015 05:18
codyj wrote: if $\alpha$ is even then $1+p^2$ divides the LHS. so $\alpha=1$ For this to hold we must have $\alpha$ be multiple of $4$.
aravind_C
01.12.2015 05:38
That is correct.
jampm
26.05.2021 05:57
This is a nice problem, here's my solution:
The given function is basically adding the even divisors and subtracting the odd ones. Therefore $f(n)$ would be equivalent to $\sigma(n)$ minus twice the sum of odd divisors of $n$.
Thus:
\[f(n) = \sigma(n) - 2\sigma\left(\frac{n}{2^{\nu_2(n)}}\right).\]
And since $\sigma$ is multiplicative, we can factorize as follows:
\[f(n) = \left (2^{\nu_2(n) + 1} - 3 \right)\sigma\left(\frac{n}{2^{\nu_2(n)}}\right).\]
This gives us firstly that $\nu_2(n) = 1$. But also we have that:
\[\text{ For every odd prime } p \text{ dividing } n, \ \frac{p^{\nu_p(n) + 1} - 1}{p - 1} = 2^r \text{ for some natural } r. \]
And here's where I realized that codyj's solution and mine where the same, I also thought about $\textbf{Zsigmondy}$ tho I was afraid if it was okay to use it at the OMM, so I figured something like his alternate finish haha, basically $\nu_p(n)$ can't be even because the LHS would be odd. And if $\nu_p(n)$ is and odd number bigger than 1, then $p^{\frac{\nu_p(n) + 1}{2}} + 1$ can't be a power of $2$ due to $\textbf{catalan's conjecture}$ ??? Mhmmmmm Anyways haha either sol works.
(of course if $\nu_p(n) = 1$ we have that $p + 1$ is a power of $2$ which implies $p$ is a mersenne prime, that yields $2^{51} - 1$ solutions! But there might be even more! Who knows lol )
AlanLG
29.01.2024 21:57
Basically same as jampm, Let $n=2^\alpha\cdot r$, then \begin{align*} f(n) &= \sigma(2^\alpha \cdot r)-2\sigma(r) \\ &= \sigma(r)\cdot \bigl[\sigma(2^\alpha)-2\bigr] \\ &=\sigma(r)\cdot \bigl[2^{\alpha+1}-3\bigr] \end{align*}so $\alpha=1$ and $2^\gamma=\sigma(r)$ so for every prime $p$ dividing $r$ we have $\frac{p^{\beta_i+1}-1}{p-1}=2^\theta$, and by Zsigmondy $\beta_i=1$, so $n$ is square free