Задачи на делимость

[a239]

Помогите, пожалуйста, разобраться с методами решения задач:

1) найти остаток от деления $ 59^{73^{79^{37}}}$ на 198
2) делитя ли $2^{1093}-2$ на 1093^2 ?

Спасибо.

[Руст]

1) разлагайте 198=2*3*3*11. И найдите по каждому множителю остатки (по 2 - 1, для вычисления по модулю 9 степень надо вычислить по модулю 6, для вычисления по модулю 11 степень достаточно вычислить по модулю 5, так как остаток 4 является квадратичным вычетом).
2) Да, так как 1093 - первое простое число Вивериха.

[a239]

С первой понятно, спасибо.

А вот вторая... Эта задача из "Виноградов. Основы теории чисел.", причем дается даже без решения в куче с остальными весьма несложными задачами. Поэтому и решение хотелось бы по понятнее(на запрос "Виверих" гугл ответил нулем информации).

Очевидно, что оно делится на 1093, вопрос в том, добавление второй степени переводит задачу в раздел олимиадных, или просто требуется более глубокое владение методом(каким?) ?

[maxal]

a239 писал(а):

(на запрос "Виверих" гугл ответил нулем информации).

См. http://primes.utm.edu/glossary/page.php ... erichPrime

[a239]

Понятно, только про доказательство там ничего нет...

[Macavity]

a239 писал(а):

Понятно, только про доказательство там ничего нет...

Доказательство тривиально следует из определения...

[RIP]

А есть ли способ док-ва, который бы легко было проделать ручками, без нудных длинных вычислений?

[a239]

Macavity, видмо, вы не совсем правильно поняли мой вопрос, он звучит так:
Как доказать, что $2^{1093}-2$ делитя на 1093^2 ?
Явно для этого не надо возводить 2 в 1093 степень...

RIP, это риторический вопрос? Пусть нудные и длинные, просто возведение 2 в 1093 степень явно не попадает даже под такое определение - это нереальные вычисления.

[RIP]

Возвести 2 в степень 1093 в кольце $\mathbb{Z}_{1093^2}$ по алгоритму быстрого возведения в степень реально проделать вручную, если запастись терпением(или калькулятором)...

[Руст]

a239 писал(а):

Macavity, видмо, вы не совсем правильно поняли мой вопрос, он звучит так:
Как доказать, что $2^{1093}-2$ делитя на 1093^2 ?
Явно для этого не надо возводить 2 в 1093 степень...

RIP, это риторический вопрос? Пусть нудные и длинные, просто возведение 2 в 1093 степень явно не попадает даже под такое определение - это нереальные вычисления.

Самый быстрый способ проверки (можно даже вручную бе компьютера воспользовавшись калькулятором). 1093-1=2*2*3*7*13. 2 не является квадратичным вычетом по модулю 1093 (так как последнее имеет вид 5(mod 8)). Поэтому минимальная степень (период) должен делиться на 4 проверяем, что 12, 28, и 52 ые степени не дают остаток 1 при делении на 1093. При этом $2^{12}=4096(mod 1194649),$ $2^{28}=834080(mod 1194649),$ $2^{52}=145396(mod 1194649).$
Соответственно
$2^{52*3}=145396^3=165052(mod 1194649),$ $2^{28*4}=834080^3=230431(mod 1194649),$ $ 2^{52*7}=145396^7=1(mod 1194649).$

[a239]

Со второй, вроде как, понял идею. Спасибо.

Теперь возвращаясь к первой. У меня получился ответ 5, как его можно проверить? Если ли программа, которая может это посчитать? Или хотя бы алгоритм, чтобы его закодить, сам не могу придумать...

[Руст]

Пусть ваше число Х=59^Y. Очевидно Х=1(mod 2) и X=5(mod 9) (последнее от того, что У=1(mod 6)). 59=4(mod 11), 4^1=4,4^2=5(mod 11), 4^3=9(mod 11),4^4=3(mod 11),4^5=1(mod 11). Поэтому, надо вычислить У=73^Z=3^Z(mod 5). 3^1=3,3^2=4(mod 5),3^3=2(mod 5),3^4=1(mod 4). Поэтому надо вычислить Z=79^{37} (mod 4). Так как число вида -1(mod 4) и возводится в нечётную степень, то Z=3(mod 4), следовательно У=2(mod 5), следовательно X=5(mod 11), т.е Х-5 делится на 11 и на 9 и на 2, т.е. на 198. Это означает Х=5(mod 198).

[a239]

Да, я так и делал, спасибо.

[a239]

Ну и еще одна задача:

Определить, есть ли решения у системы:

$\left\{ \begin{array}{l} x+a\equiv 0 (mod 21) \\ 3x\equiv 5a (mod 56) \\ 4x\equiv 7a (mod 24) \end{array} \right.$

Переписывая:

$\left\{ \begin{array}{l} x+a=21k \\ 3x-5a=56p\\ 4x-7a=24q \end{array} \right.$

Складывая 1 с 2 и 2 с 3

$\left\{ \begin{array}{l} 8x=105k+56p \\ a=224p-72q \end{array} \right.$

и подставляя в первое равенство 105k+56p+8*224p-8*72q=21t, а это имеет решения в целых числах.

Правильно, или надо по-другому?

[maxal]

a239 писал(а):

Правильно, или надо по-другому?

Можно было изначально разбить систему на подсистемы с попарно-взаимно простыми модулями (т.е. 3, 7, 8), решать каждую из подсистем средствами линейной алгебры (над соответствующим кольцов вычетов), а затем скомбинировать решения по китайской теореме об остатках.