Докажите, что при любом нечетном положительном n число 2^(n!) - 1 делится на n.

задан 20 Ноя '17 3:42

У меня свелось к утверждению: $% \exists k \in \mathbb{N} : \phi(n) = \frac{n!}{k} $%

(20 Ноя '17 5:46) Williams Wol...

Пусть n=...p(i)^{k(i)}... -- каноническое разложение. Достаточно доказать делимость на p(i)^{k(i)}, где p(i) нечётно. Ввиду теоремы Эйлера, 2^{ф(p(i)^{k(i)})}-1 делится на p(i)^{k(i)}, поэтому достаточно проверить, что n! делится на ф(p(i)^{k(i)}). Но это очевидно, так как ф(p(i)^{k(i)}) < p(i)^{k(i)}<=n. Поэтому n! можно даже заменить на (n-1)!.

(20 Ноя '17 10:18) falcao
10|600 символов нужно символов осталось
0

$%2^{n!} - 1 \ \equiv \ 0 \ (mod \ n) \ \Longleftrightarrow 2^{n!} \ \equiv \ 1 \ (mod \ n)$%, если это так (1).

Ясно, что $%n! \ \vdots \ \varphi(n)$%, так как $%\varphi(n) < n$%. Отсюда $%2^{n!} = 2 ^ {k \times \varphi(n)}$%, $%k \in \mathbb{Z}$%. По теореме Эйлера, $%2 ^ {k \times \varphi(n)} = (2 ^ k) ^ {\varphi(n)} \ \equiv \ 1 \ (mod \ n)$%. Это верно, так как соблюдается условие НОД($%2^k$%, n) = 1, так как n - нечетно. Применяем (1) и доказываем.

ссылка

отвечен 29 Июл 19:08

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×206
×77

задан
20 Ноя '17 3:42

показан
1577 раз

обновлен
29 Июл 19:08

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru