Bacteria wrote: Let $v(n)$ be the order of $2$ in $n!$. Prove that for any positive integers $a$ and $m$ there exists $n$ ($n>1$) such that $v(n) \equiv a (\mod m)$. I have a book with Mongolian problems from this year, and this problem appeared in it. Perhaps I am terribly misinterpreting this problem, but it seems like it is wrong. Any ideas? It is a problem from Komal.I posted in ML with no idea. You can see some idea to solve this problem http://forum.mathscope.org/showthread.php?t=19638 P/s can you post all problem from Mongolia TST 2011?

Ah, intetesting. Yep: I have all 4 TSTS plus some other ones (like the national olympiad), I'll try to have all of the TSTs posted this week.

Bacteria wrote: Ah, intetesting. Yep: I have all 4 TSTS plus some other ones (like the national olympiad), I'll try to have all of the TSTs posted this week. wow.It is a nice work.Why don't u post it !

Bacteria wrote: Let $v(n)$ be the order of $2$ in $n!$. Prove that for any positive integers $a$ and $m$ there exists $n$ ($n>1$) such that $v(n) \equiv a (\mod m)$. I have a book with Mongolian problems from this year, and this problem appeared in it. Perhaps I am terribly misinterpreting this problem, but it seems like it is wrong. Any ideas? What does $\text{order}$ stand for? Does it mean $\nu_2(n!)$? And for all $a, m\exists n$ such that $\nu_2(n) \equiv a (\mod m)$.

mathmdmb wrote: What does $\text{order}$ stand for? Does it mean $\nu_2(n!)$? And for all $a, m\exists n$ such that $\nu_2(n) \equiv a (\mod m)$. Yes, I believe that is what the problem is asking. Love_Math1994 wrote: wow.It is a nice work.Why don't u post it ! Done! Mongolia 2011 TST

I posted a solution here http://www.artofproblemsolving.com/Forum/viewtopic.php?f=57&t=311131&hilit=official+solution

lemma.$v(n)=n-q(n)$,where $q(n)$ denotes the number of the times '1' appears in binary of n. (it's a classical lemma;and we can find its proof in various books) thenlet $n=2^{r_1}+...+2^{r_k}$let $r_i=i\phi(m)+1,k=a$,then $v(n)\equiv a(modn)$.

@littletush Your construction fails when $2|m$ because Euler's Theorem will not hold. For instance, if you choose $a=1, m = 6$, your result will give $n = 2^3$, and clearly $v_2(2^3) \not \equiv 1 \pmod{6}$.

dinoboy wrote: @littletush Your construction fails when $2|m$ because Euler's Theorem will not hold. For instance, if you choose $a=1, m = 6$, your result will give $n = 2^3$, and clearly $v_2(2^3) \not \equiv 1 \pmod{6}$. oh gosh! I should have noticed this! but by the Lemma,one can construct any number he like.it suffices to discuss the power of 2 in m.