Find all positive integers $n$ such that the following holds. $$\tau(n)|2^{\sigma(n)}-1$$
Problem
Source: Iranian Third Round 2020 Number Theory exam Problem1
Tags: number theory, Divisibility, totient function
21.11.2020 15:33
Consider $L(n)=$the smallest prime divisor of $n$ for $n>1$ We use the lemma $L(\frac{x^n -1}{x-1})\geq L(n)$ (proof is easy using order and note that there is no equality case for x=2) Now consider $n= \prod p_i ^{a_i}$ $$L(2^{\sigma(n)} -1) >L(\sigma(n))= L(\prod{\frac{p_i ^{a_i +1}-1}{p_i -1}}) = min(L(\frac{p_i ^{a_i +1}-1}{p_i -1}))\geq min(L(a_i +1)) = L(\tau(n))$$So if $n \neq 1$ We cant have divisibilty and $n=1$ works
09.09.2021 10:50
........
28.02.2022 03:22
TheBarioBario wrote: Consider $L(n)=$the smallest prime divisor of $n$ for $n>1$ We use the lemma $L(\frac{x^n -1}{x-1})\geq L(n)$ (proof is easy using order and note that there is no equality case for x=2) Now consider $n= \prod p_i ^{a_i}$ $$L(2^{\sigma(n)} -1) >L(\sigma(n))= L(\prod{\frac{p_i ^{a_i +1}-1}{p_i -1}}) = min(L(\frac{p_i ^{a_i +1}-1}{p_i -1}))\geq min(L(a_i +1)) = L(\tau(n))$$So if $n \neq 1$ We cant have divisibilty and $n=1$ works how you prove the lemma?
28.02.2022 16:01
ILOVEMYFAMILY wrote: how you prove the lemma? OK so let $p$ be the smallest prime divisor of $\frac{x^n - 1}{x - 1}$ then $p \mid x^n - 1$. Let $r = \text{ord}_p(x)$ then $r \mid n$ and $r \mid p - 1$ (by Fermat). If $r = 1$ then $p \mid x - 1$ and hence by LTE \[ 0 < \nu_p \left( \frac{x^n - 1}{x - 1} \right) = \nu_p(n) \]In other words $p \mid n$ and therefore $p$ is at least the smallest prime divisor of $n$. If $r \geq 2$ then since $r \mid n$, $r \geq L(n)$. By noting that $p - 1 \geq r$, we arrive at $p > r \geq L(n)$.