|
Для всех натуральных $%n$% показать, что $%n^{13}-n$% делится на 2730. Как здесь можно использовать функцию Эйлера? задан 16 Дек '13 23:48 
Танюша |
|
Здесь достаточно малой теоремы Ферма. Поскольку $%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 
falcao А как можно использовать функцию Эйлера?
(17 Дек '13 0:09)
Танюша
Формула Эйлера приводит к намного более слабому результату. Там все числа вида $%p-1$% перемножаются, и получается 576. А реально здесь важно не произведение, а НОК этих чисел, то есть 12. Малая теорема Ферма есть частный случай теоремы Эйлера, и её здесь хватает. Тот показатель степени, который получается через $%\varphi(n)$%, как правило, не оптимален, и число $%n$% лучше разлагать на взаимно простые множители, анализируя по отдельности делимость на каждый из них.
(17 Дек '13 0:14)
falcao
|