2001 Balkan Mathematical Olympiad

For discussing Olympiad Level Number Theory problems
tanmoy
Posts:312
Joined:Fri Oct 18, 2013 11:56 pm
Location:Rangpur,Bangladesh
2001 Balkan Mathematical Olympiad

Unread post by tanmoy » Mon Dec 07, 2015 11:44 pm

Let $n$ be a positive integer.Show that if $a$ and $b$ are
integers greater than $1$ such that $2^{n}-1=ab$, then $ab − (a − b) − 1$ can be
written as $k·2^{2m}$ for some odd integer $k$ and some positive integer $m$
"Questions we can't answer are far better than answers we can't question"

rah4927
Posts:110
Joined:Sat Feb 07, 2015 9:47 pm

Re: 2001 Balkan Mathematical Olympiad

Unread post by rah4927 » Tue Dec 08, 2015 8:18 pm

Outline: For $n>1$, consider the residues of $a$ and $b$ modulo $4$.

tanmoy
Posts:312
Joined:Fri Oct 18, 2013 11:56 pm
Location:Rangpur,Bangladesh

Re: 2001 Balkan Mathematical Olympiad

Unread post by tanmoy » Wed Dec 09, 2015 10:48 am

$\text{My Solution}$:
Note that $ab−(a−b)−1 = (a+1)(b−1)$.We shall show that the highest powers of $2$ dividing $(a+1)$ and $(b−1)$ are the same. Let $2^{s}$ and $2^{t}$ be the highest powers of $2$ dividing $(a+1)$ and $(b−1)$,respectively.
Because $a + 1$, $b + 1$ $\leq$ $ab + 1$ = $2n$, we have $s, t \leq n$.Note that $2^{s}$ divides $2^{n} = ab + 1$ and $a + 1$,so that
$ab \equiv a \equiv −1 (mod 2^{s})$.
Hence, $b \equiv 1 (mod 2^{s})$, or $2s|b − 1$, so that $s \leq t$.
Similarly, $ab \equiv −b \equiv −1 (mod 2^{t})$, so $a \equiv −1 (mod 2^{t})$, and $2^{t}|a + 1$.
Thus, $t \leq s$.
Therefore,$s=t$,the highest power of two dividing $(a + 1)(b − 1)$ is $2^{2s}$,
and $ab − (a − b) − 1 = k · 2^{2s}$ for some odd $k$.
"Questions we can't answer are far better than answers we can't question"

Post Reply