Разделы 
Дополнительно
Задача по математике - 2037
2019-01-23 
Найдите наименьшее натуральное число, не представимое в виде $ \frac {2^a-2^b}{2^c-2^d}$, где $a, b, c, d$ - натуральные числа.
Решение:
$1=\frac{4-2}{4-2}, 3=\frac{8-2}{4-2}, 5 = \frac{16-1}{4-1}=\frac{2^5 - 2}{2^3 - 2}, 7 = \frac{16-2}{4-2}, 9 = 2^3 + 1 = \frac{2^6 - 1}{2^3 - 1} = \frac{2^7 - 2}{2^4 - 2}. 2 = 2 \cdot 1 = \frac{2^3 - 2^2}{2^2 - 2}, \cdots, 10 = 2 \cdot 5 = \frac{2^6 - 2^2}{2^3 - 2}$
Предположим, что $11 = \frac{2^a - 2^b}{2^c - 2^d}$. Не уменьшая общности, положим $a > b, c > d$. Обозначим $m = a - b, n = c - d, k = b - d$. Получаем
$11(2^n - 1) = 2^k (2^m - 1)$.
Так как в левой части целое нечетное число, то $k = 0$. Заметим, что $n = 1$ не подходит. Если же $m > n > 1,$ то $2^m - 1$ и $2^n - 1$ дают остаток 3 при делении на 4. Значит, левая и правая части дают соответственно остатки 1 и 3 при делении на 4. Противоречие.
Замечание. Можно прийти к противоречию по другому. Из алгоритма Евклида следует, что $2^m - 1$ делится на $2^n - 1$ без остатка, тогда и только тогда, когда $m$ делится на $n$. Значит, надо доказать, что $11 \neq 1 + 2^n + 2^{2n} + \cdots $. Но последнее очевидно, поскольку 11 не равно ни одному из чисел $1 + 2, 1 + 2 + 4, 1 + 4, 1 + 8$.
Ответ. 11.
Найдите наименьшее натуральное число, не представимое в виде $ \frac {2^a-2^b}{2^c-2^d}$, где $a, b, c, d$ - натуральные числа.
Решение:
$1=\frac{4-2}{4-2}, 3=\frac{8-2}{4-2}, 5 = \frac{16-1}{4-1}=\frac{2^5 - 2}{2^3 - 2}, 7 = \frac{16-2}{4-2}, 9 = 2^3 + 1 = \frac{2^6 - 1}{2^3 - 1} = \frac{2^7 - 2}{2^4 - 2}. 2 = 2 \cdot 1 = \frac{2^3 - 2^2}{2^2 - 2}, \cdots, 10 = 2 \cdot 5 = \frac{2^6 - 2^2}{2^3 - 2}$
Предположим, что $11 = \frac{2^a - 2^b}{2^c - 2^d}$. Не уменьшая общности, положим $a > b, c > d$. Обозначим $m = a - b, n = c - d, k = b - d$. Получаем
$11(2^n - 1) = 2^k (2^m - 1)$.
Так как в левой части целое нечетное число, то $k = 0$. Заметим, что $n = 1$ не подходит. Если же $m > n > 1,$ то $2^m - 1$ и $2^n - 1$ дают остаток 3 при делении на 4. Значит, левая и правая части дают соответственно остатки 1 и 3 при делении на 4. Противоречие.
Замечание. Можно прийти к противоречию по другому. Из алгоритма Евклида следует, что $2^m - 1$ делится на $2^n - 1$ без остатка, тогда и только тогда, когда $m$ делится на $n$. Значит, надо доказать, что $11 \neq 1 + 2^n + 2^{2n} + \cdots $. Но последнее очевидно, поскольку 11 не равно ни одному из чисел $1 + 2, 1 + 2 + 4, 1 + 4, 1 + 8$.
Ответ. 11.
