Делимость на 11.

[Marina]

Помогите , пожалуйста, доказать, что при любом натуральном $n$: $5^{5n+1}+4^{5n+2}+3^5n$ делится на 11.
Пока мои мысли такие: $n$: $5^{5n+1}+4^{5n+2}+3^{5n}=5(5^{5n}+4^{5n})+3^{5n}+11\cdot 4^{5n}$???

[maxmatem]

Лучше по индукции.

[ИСН]

Сейчас опять найдётся какой-нибудь случайный трюк, а слон (малая теорема Ферма) пройдёт мимо.

[Ales]

Нужно применить малую теорему Ферма, а также знать про вычеты.

[Бодигрим]

ИСН в сообщении #322469 писал(а):

Сейчас опять найдётся какой-нибудь случайный трюк, а слон (малая теорема Ферма) пройдёт мимо.

Ну, если знать малую теорему Ферма и проверить, что 3, 4 и 5 - квадратичный вычеты по модулю 11, то сразу получим $3^5\equiv 4^5\equiv 5^5\equiv 1\pmod{11}$. А можно просто решить задачу на уровне 6-го класса и вручную подсчитать эти степени. Я даже не знаю, какой из этих трюков "случайнее".

[Marina]

Бодигрим
Извините, пожалуйста, но я не поняла, что такое

Цитата:

...квадратичные вычеты по модулю 11...

[Бодигрим]

Это такие числа $k$, к которым можно прибавить кратное 11 и получить полный квадрат. Вот, скажем, 3 - вычет, потому что $3+33=6^2$. А вот 2 - невычет, не существует полных квадратов вида $11n+2$.

Если $k$ - вычет, то мы можем найти такое $m$, что $k\equiv m^2\pmod{11}$. Тогда $k^{5n}\equiv m^{10n}\equiv1 \pmod {11}$. Здесь во втором переходе сработала малая теорема Ферма.

[Marina]

Помогите, пожалуйста, решить задачу с помощью малой теоремы Ферма (в школе мы её не проходили):
$5\cdot 5^{10}=1+11p$
$16\cdot 4^{10}=1+11s$
$3^{10}=1+11m$???
...

[Ales]

Marina в сообщении #322877 писал(а):

в школе мы её не проходили

Малая теорема Ферма: $n^{p-1}-1$ делится на $p$, если $p$ - простое, $n,p$ - взаимно просты.
Доказывается разными способами. Надо найти в интернете или книгах.

-- Сб май 22, 2010 23:02:08 --

Marina в сообщении #322877 писал(а):

Помогите, пожалуйста, решить задачу с помощью малой теоремы Ферма (в школе мы её не проходили):
$5\cdot 5^{10}=1+11p$
$16\cdot 4^{10}=1+11s$
$3^{10}=1+11m$???
...

$5\cdot 5^{10}=5+11p$

[Marina]

$5\cdot 5^{10}=5+11p$
$16\cdot 4^{10}=16+11s$
$3^{10}=1+11m$
?

[Marina]

$5^{10}+4^{10}+3^{10}=11(p+s+m)+22$
$5^{10} \equiv 5 (mod 11)$
$4^{10} \equiv 4 (mod 11)$
$3^{10} \equiv 1(mod 11)$

[Бодигрим]

Marina в сообщении #322969 писал(а):

$5^{10} \equiv 5 (mod 11)$
$4^{10} \equiv 4 (mod 11)$

Это неправда.

[Marina]

Бодигрим
$5^{10} \equiv 1 (mod 11)$?
$4^{10} \equiv 1 (mod 11)$?

[Бодигрим]

Да.

[Marina]

$5\cdot 5^{10}=5+11p=5\cdot (5^{10}-1)=11p$
$16\cdot 4^{10}=16+11s=16\cdot (4^{10}-1)=11s$
$3^{10}=1+11m=3^{10}-1=11m$
А как быть дальше?