Let $m$ be a positive integer greater than $1$, and suppose that $n$ is a positive integer which satisfies $n\vert a^m-1$ for all integers $a$ coprime to n.
Prove that $n\leq4m(2^m-1)$. Find all cases of equality.
My initial approach was that since $a^m\equiv1$ mod $n$ for all such $a$, you have $m\geq \lambda(n)$ where $\lambda(n)$ the Carmichael function gives the least value for which such a congruence holds for all coprime integers.
Using the known formula $\lambda(n)=$ lcm$(\lambda(p_1^{r_1}),\lambda(p_2^{r_2}),…,\lambda(p_t^{r_t}))$ where $n=p_1^{r_1}…p_t^{r_t}$ doesn't seem to yield any reasonable bound.
I also tried to consider the LTE lemma as you further have $\lambda(n)\vert m$ so $m=l\cdot\lambda(n)$ for some integer $l$. Then you have for a prime $p\vert n$ $$v_p(n)\leq v_p(a^{l\cdot\lambda(n)}-1)= v_p(l)+v_p(a^{\lambda(n)}-1)$$ but I am unsure of where to go from here.
Another approach was to split $a^m-1$ using $m=2^\gamma s$ with $s$ odd, however, that too got me nowhere. I wanted to see if I was on the right track or if the solution involves a completely different approach.
Best Answer
Ok after looking at the thread I think I know how to solve it.
There are two cases:
$1.$ $n$ is odd, which means that $n\vert 2^m-1$ $\Rightarrow$ $n\leq 4m(2^m-1)$ as needed.
$2.$ Write $n=2^{\alpha}M$ where $M$ is odd. Then gcd$(n,M+2)=1$ and thus $M\vert(M+2)^m-1$ $\Rightarrow M\vert 2^m-1$ giving the bound $M\leq 2^m-1$.
Furthermore, you have $m\geq\lambda(n)\geq\frac{1}{2}\phi(2^\alpha)$ using the formula for $\lambda(n)$. This yields $2^\alpha\leq4m$ which gives the desired result after taking the product of the two inequalities.
For the cases of equality, you have $2^\alpha M=4m(2^m-1)$.
Using the inequality from $(2.)$ combined with the fact that $M$ must equal the product of the odd part of $m$ and $2^m-1$ you have $M=2^m-1$ and $m=2^{\alpha-2}$.
Using the Fermat numbers gives a nice form for $n=2^\alpha F_{\alpha-3}F_{\alpha-4}...F_0$. However, the condition of the statement also implies that $m=\lambda(n)=2^\alpha$. So if $n=2^\alpha p_1^{r_1}p_2^{r_2}...p_t^{r_t}$, you need $\lambda(p_i^{r_i})=2^{c_i}$ which means $r_i=1$.
Each of the Fermat numbers is therefore prime and so for a solution to exist, you need $\phi(F_{\alpha-3})\leq \lambda(2^\alpha)$ giving $\alpha=3,4$ and the solutions $(m,n)=(2,24),(4,240)$.