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$
2001 Balkan Mathematical Olympiad
"Questions we can't answer are far better than answers we can't question"
Re: 2001 Balkan Mathematical Olympiad
$\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$.
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"