I think it can be shown that the condition in the hypothesis is equivalent to $\phi(n)|m$, so the inequality we have to prove is $n\leq 4\phi(n)(2^{\phi(n)}-1)$.

grobber wrote: I think it can be shown that the condition in the hypothesis is equivalent to $\phi(n)|m$ Now I think I was wrong about this. This: http://www.mathlinks.ro/viewtopic.php?p=19619#19619 inspired me to think that. If $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ then there must be an $a$ which is a primitive root of $p_i^{a_i}\ \forall i\in \overline{1,k}$. This means that $(p_i-1)p_i^{a_i-1}|m,\ \forall i\in \overline{1,k}$, but that doesn't necessarily mean that $\phi(n)|m$. However, it still means that $p_i^{a_i-1}|m\ \forall i\in \overline {1,k}$. Maybe this helps.

Some comments: The initial problem was intended for the juniors and was to prove that any good number is at most $ 5^m-1$. Of course, in my solution there was also this bound, but I just didn't noticed that with some very small things added the bound can be substantially improved and so was the problem given. It's not very hard and it's solution is more than elementary. I like it since for p=2 and p=4 the bounds are sharp. But I really think the bounds are far more small than $ 4m(2^m-1) $. Unfortunately, I don't know any asimptotyc formula for the largest good number.

Grobber, I don't think it is true what you have said. Just take m=4 and n=240.

Grobber, primitive root exists for all p^n, where p>2, so for pi=2 it doesn't work. Here's my solution (I hope it's correct). If n is odd then n|(2^m-1) so n<=(2^m-1). If n=2^b.k (k odd, a>0) then gcd(n,k+2)=1, so k|(k+2)^m-1 and k|2^m-1. It means that k<=2^m-1. We must prove that 2^(b-2)<=m. Assume that b>2. Let l>0 be minimal such that 2^b|a^l-1 for all odd a. Then l|2^(b-1) (Euler's function of 2^b) and l=2^i. Assume that i<b-2. Than 2^b | a^(2^(b-3))-1=(a-1)(a+1)...(a^(2^(b-4))+1). If we take a=5 it is wrong. It means that 2^(b-2)<=m.

Right! I forgot about $p=2$..

Anyway, this problem is so easy that it is allmost impossible not to solve it. Of course, in a contest with two other problems, the situation changes. But it's still an easy problem.

Yes,Harazi's right.It is very easy.I think harazi generalized from a IMO shortlist problem N1/2000 .And this ineq in your problem maybe not very good!

Good or not, this is the problem. And yes, it's a little generalization of a shortlist problem. But very easy as it may seem, it wasn't solved by lots of contestants in the TST. So, you know, 3 lines solutions are not necesarrily trivial. But I'm waiting for the very strong inequality you announced! Enlight us, please!!!

another solution let $n=\prod p_{i}^{a_{i}}$ and $g_{i}$ be primitive root of $p_{i}$. by china remaining theorem there are some $a$ such that $a\equiv g_{i}mod(p_{i})$ and $(a,p_{j})=1$($i\neq j$)we know $\varnothing (n)$ is smallest number of $x$ such that $p_{i}\mid a^x-1$. So $\varnothing (n)\mid m$. let $n=2^tr$ and $r$ be a odd number.we must prove $ 2^tr\leq 4.2^{t-1}r(2^{2^{t-1}\varnothing (r)}-1)$ and we know that $r\mid (2^{2^{t-1}\varnothing (r)}-1)$ so we are done easily.

A solution with no Primitive roots or whatever:

If m is odd then n|(n − 1)m − 1 implies n|2, hence n ≤ 2. Take now m = 2tq, t ≥ 1, q odd, If n = 2u(2v + 1) is m-good, then (2v + 1)|(2v − 1)m − 1, hence (2v + 1)|2m − 1. Also, if a = 8v + 5 then (a, n) = 1, so 2u|(aq)2t − 1 = (aq − 1)(aq + 1)(a2q + 1) . . . (a2t−1q + 1). But aq ≡ 5 (mod 8) implies that the exponent of the factor 2 in the last product is t+2, therefore u ≤ t+2, whence n ≤ 4·2t(2v+ 1) ≤ 4m(2m−1)

AndrewKwon97 wrote: Furthermore, $a$ must be odd, and it only a matter of some computation with binomial expansion to verify that there is some odd $a$ such that $\text{ord}_{2^e}(a) = e-2$. [/hide] How does this statement follow? I am not sure how to use binomial expansion to imply the existence of an a that has order e-2 modulo $2^e$.

vsathiam wrote: AndrewKwon97 wrote: Furthermore, $a$ must be odd, and it only a matter of some computation with binomial expansion to verify that there is some odd $a$ such that $\text{ord}_{2^e}(a) = e-2$. [/hide] How does this statement follow? I am not sure how to use binomial expansion to imply the existence of an a that has order e-2 modulo $2^e$. I don't think that statement holds as demonstrated by the counter example e=5.

I think this is a hybrid of va2010's and AndrewKwon97's solutions, but I'm not sure. Write $n = 2^\ell n_0$ for $n_0$ a positive odd integer. We will show that \[ 2^\ell \leq 4m\quad\text{and}\quad n_0\leq 2^m - 1; \]this completes the proof. First observe that, for any odd integer $a$, Lifting the Exponent tells us \[ \ell \leq \nu_2(a^m - 1) = \nu_2(a-1) + \nu_2(a+1) + \nu_2(m) - 1. \]By the Chinese Remainder Theorem, we may choose a value of $a$ satisfying the system of congruences \begin{align*} a&\equiv 1\pmod{n_0},\\ a&\equiv 3\pmod{8}. \end{align*}Then $\gcd(a,n) = 1$, and furthermore \[ \ell \leq \nu_2(a-1) + \nu_2(a+1) + \nu_2(m) - 1 = 2 + \nu_2(m) = \nu_2(4m). \]Thus $2^\ell\leq 2^{\nu_2(4m)} \leq 4m$. Now we turn our attention to $n_0$. Observe that, again by the Chinese Remainder Theorem, there exists an integer $a$ such that \begin{align*} a&\equiv 1\pmod{2^\ell},\\a&\equiv 2\pmod{n_0}; \end{align*}Then again $\gcd(a,n) = 1$, and for this value of $a$ we have \[ 0 \equiv a^m - 1 \equiv 2^m - 1\pmod{n_0}. \]Thus $n_0$ divides $2^m - 1$. We are done. I believe equality holds whenever $2^{\nu_2(4m)} = 4m$ -- that is, $m$ is a power of $2$ -- but I'm not 100% confident in this.

Let $n=2^ax$. We must have $a^m-1\equiv 0$ (mod $x$) for all $a$ relatively prime to $x$ and $a^m-1\equiv 0$ (mod $2^l$) for all odd $a$. Let $m=2^pq$. Claim: $x\leq 2^m-1$ This follows by plugging in $a=2$. Claim: $a^{2^p}-1\equiv 0$ (mod $2^l$) for all odd a This follows because else it contradicts Euler's Totient Theorem. Claim: $v_2(3^{2^p}-1)=p+2$ This follows by LTE. So we have $n\leq 4m(2^m-1)$. It is not hard to show that equality holds iff $m$ is a power of $2$.

Here's my solution (Doesn't state LTE though ): Call the property to be $m$-nice. If $m$ is odd, then: $$n|(n-1)^m-1 \implies n|2 \implies n \le 2.$$ Let $m = 2^t (2r+1)$ and $n=2^u (2s+1)$. Notice that: $2s+1|2^m-1\implies 2s+1 \le 2^m-1$. Choose $a$ such that: $a=8r+5$ for some integer $r$ and let $q=2u+1$. Then: $$n|(a^q)^{2^t}-1 = (a^q-1)(a^q+1)(a^{2q}+1) \cdots (a^{2^{t-1} q}+1)$$Note that: $a^q = 8R+5$ for some integer $R$. Then, in the product: $a^q-1$ is divisible by $4$ (but not $8$) and rest of the terms of the form $a^{2^r q}+1$ is divisible by $2$ but not by $4$. Thus comparing the powers of $2$: $u \le t+2.$ Combining $2s+1 \le 2^m-1$ with $u \le t+2$, we have: $n = 2^u (2s+1) \le 4 \cdot 2^t (2^m-1) \le 4 \cdot 2^t (2u+1) (2^m-1) = 4m (2^m-1)$. Note: Equality holds for $m=2, 4$.