m and n

For discussing Olympiad Level Number Theory problems
User avatar
SANZEED
Posts: 550
Joined: Wed Dec 28, 2011 6:45 pm
Location: Mymensingh, Bangladesh

m and n

Unread post by SANZEED » Wed Apr 10, 2013 11:49 pm

Let $m,n$ be positive integers. Prove that $(2^m-1)^2|(2^n-1)$ if and only if $m(2^m-1)|n$.

Source:Russia 1997
$\color{blue}{\textit{To}} \color{red}{\textit{ problems }} \color{blue}{\textit{I am encountering with-}} \color{green}{\textit{AVADA KEDAVRA!}}$

User avatar
Phlembac Adib Hasan
Posts: 1016
Joined: Tue Nov 22, 2011 7:49 pm
Location: 127.0.0.1
Contact:

Re: m and n

Unread post by Phlembac Adib Hasan » Thu Apr 11, 2013 9:11 am

Hint:
$\gcd (a^m-1,a^n-1)=a^{\gcd (m,n)}-1$

User avatar
zadid xcalibured
Posts: 217
Joined: Thu Oct 27, 2011 11:04 am
Location: mymensingh

Re: m and n

Unread post by zadid xcalibured » Thu Apr 11, 2013 3:48 pm

$2^m-1|2^n-1 \longleftrightarrow m|n$.Let $n=km$. As $2^m-1|\frac{2^n-1}{2^m-1}$
and $2^{m(k-1)}+2^{m(k-2)}+.............+1 \equiv k \equiv 0 (mod 2^m-1)$
\[\Longleftrightarrow 2^m-1|k\]
\[\Longleftrightarrow m(2^m-1)|n\]

User avatar
Masum
Posts: 592
Joined: Tue Dec 07, 2010 1:12 pm
Location: Dhaka,Bangladesh

Re: m and n

Unread post by Masum » Sun Apr 14, 2013 7:37 pm

https://www.awesomemath.org/assets/PDFs ... _Lemma.pdf
A general version, and applicable in many criteria. Particularly, this problem becomes one liner
One one thing is neutral in the universe, that is $0$.

User avatar
Fm Jakaria
Posts: 79
Joined: Thu Feb 28, 2013 11:49 pm

Re: m and n

Unread post by Fm Jakaria » Sat Dec 14, 2013 8:00 pm

Masum wrote:https://www.awesomemath.org/assets/PDFs ... _Lemma.pdf
A general version, and applicable in many criteria. Particularly, this problem becomes one liner
Ithink problem 3 has a crack in the solution. How can we assume a and d relatively prime?
You cannot say if I fail to recite-
the umpteenth digit of PI,
Whether I'll live - or
whether I may, drown in tub and die.

Post Reply