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
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 )
25.11.2015 06:01
djmathman wrote:
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$
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 )
$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.
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?
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.
30.11.2015 04:32
Proposed by Irving Calderon
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
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$
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$.
01.12.2015 05:38
That is correct.
26.05.2021 05:57
This is a nice problem, here's my solution:
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