Для всех натуральных $%n$% показать, что $%n^{13}-n$% делится на 2730. Как здесь можно использовать функцию Эйлера?

задан 16 Дек '13 23:48

изменен 16 Дек '13 23:48

10|600 символов нужно символов осталось
1

Здесь достаточно малой теоремы Ферма. Поскольку $%2730=2\cdot3\cdot5\cdot7\cdot13$%, достаточно доказать делимость числа $%n^{13}-n$% на каждое простое число $%p$% из списка сомножителей. Если $%n$% само делится на $%p$%, то доказывать нечего. А если не делится, то по малой теореме Ферма, на $%p$% делится число $%n^{p-1}-1$%. При этом $%p-1$% принимает значения 1, 2, 4, 6, 12, и все они являются делителями 12. Следовательно, $%n^{12}-1$% делится на $%n^{p-1}-1$%, а потому и на $%p$%. При домножении на $%n$% всё сохраняется.

ссылка

отвечен 17 Дек '13 0:03

А как можно использовать функцию Эйлера?

(17 Дек '13 0:09) Танюша

Формула Эйлера приводит к намного более слабому результату. Там все числа вида $%p-1$% перемножаются, и получается 576. А реально здесь важно не произведение, а НОК этих чисел, то есть 12. Малая теорема Ферма есть частный случай теоремы Эйлера, и её здесь хватает. Тот показатель степени, который получается через $%\varphi(n)$%, как правило, не оптимален, и число $%n$% лучше разлагать на взаимно простые множители, анализируя по отдельности делимость на каждый из них.

(17 Дек '13 0:14) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×591

задан
16 Дек '13 23:48

показан
351 раз

обновлен
17 Дек '13 0:14

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

по почте:

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

по RSS:

Ответы

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

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