Несколько задач по теории чисел.

[Imperator]

1. Доказать, что среди чисел бесконечной последовательности
$1, 31,331,3331,...$
существует бесконечно много составных чисел, и найти наименьшее из них.
2. Доказать, что среди каждых трех последовательных натуральных чисел >7 по крайней мере одно имеет хотя бы два различных простых делителя.
3. Доказать, что каждое четное число $2k$ для каждого натурального числа $m$ является разностью двух натуральных чисел, взаимно простых с $m$.
4. Доказать, что для нечетных $n$ имеем $n|2^{n!}-1$.
5. Доказать, что для каждого натурального числа $m$ существует натуральное число $n$ с суммой цифр $m$ (в десятичной системе счисления), делящееся на $m$.

[Kid Kool]

4. n! делится на \phi(n)
5. Пусть $m = n{2}^k{5}^l, где (n,10) = 1. Пусть A = \left(\sum\limits_{j=0}^{m-1} 10^{j\phi(n)}\right)10^{k+l}$. Нетрудно видеть, что A - искомое число.

[maxal]

1. Это числа $\frac{10^n-7}{3}$. Зафиксируем простое число $p>7$, для которого $10$ является первообразным корнем. Пусть это будет $p=17$. Тогда $10^n\equiv 7\pmod{17}$ имеет решение $n\equiv 9\pmod{16}$. Поэтому для таких $n$ число $\frac{10^n-7}{3}$ будет делиться на 17.
Чтобы найти наименьшее составное число достаточно рассмотреть лишь $n\leq 9$ и убедиться, что наименьшее составное число будет при $n=9$.

2. Прямое следствие теоремы Каталана.

[Kid Kool]

2. Предположим противное, тогда найдется тройка последовательных натуральных чисел, каждое из которых - степень простого. Хотя бы одно из чисел делится на 3, значит, равно 3^k и нечетно. Если 3^k в центре, то по бокам - степени двойки, различающиеся на два, что неверно для чисел > 7. Иначе в центре - степень двойки 2^n.
Если 3^k слева, т.е 3^k = 2^n-1, то n четно, а тогда 3^{k-1} = 1 + 4 + 4^2 + ... + 4^{\frac {n} {2} - 1}, что дает остаток $\frac {n} {2}$ при делении на 3. Т.к. n не делится на 3 (иначе 3^k делится на 7), то k = 1, что невозможно, т.к. числа больше 7.
Если 3^k справа, т.е 3^k = 2^n+1, то k четно, а тогда 2^{n-3} = 1 + 9 + 9^2 + ... + 9^{\frac {k} {2} - 1}, что дает остаток $\frac {k} {2}$ при делении на 2. Т.к. k не делится на 4 (иначе 2^n делится на 80), то n = 3 и левое число равно 7, что, опять-таки, невозможно.

Добавлено спустя 45 минут 43 секунды:

3. Пусть d - произведение всех простых, общих для m и 2k, а n - произведение всех простых, делящих m, но не делящих d. Будем искать числа в виде dx+1 и dx+2k+1. Понятно, что числа взаимно просты с d. Для каждого p_j, входящего в n, выберем x_j так, чтобы d{x_j}+1 и d{x_j} + 2k + 1 не делились на p_j, т.е. так чтоб x_j не давал остатки $\frac {-1} {d}$ и $\frac {-1} {d} + \frac {-2k} {d} $ при делении на p_j. Если p_j > 2, то это можно сделать, а если p_j = 2, то тоже, поскольку в этом случае оба остатка совпадают (равны 1). Тогда по китайской теореме об остатках найдется x, дающий остаток x_j при делении на p_j, x будет искомым.