2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Задачи на делимость
Сообщение23.10.2006, 05:10 
Аватара пользователя


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

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

Спасибо.

 Профиль  
                  
 
 
Сообщение23.10.2006, 07:23 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение23.10.2006, 14:37 
Аватара пользователя


23/10/06
42
С первой понятно, спасибо.

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

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

 Профиль  
                  
 
 
Сообщение23.10.2006, 14:52 
Модератор
Аватара пользователя


11/01/06
5660
a239 писал(а):
(на запрос "Виверих" гугл ответил нулем информации).


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

 Профиль  
                  
 
 
Сообщение23.10.2006, 15:18 
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение23.10.2006, 17:01 
Заслуженный участник


05/09/05
515
Украина, Киев
a239 писал(а):
Понятно, только про доказательство там ничего нет...


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

 Профиль  
                  
 
 
Сообщение23.10.2006, 17:30 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение23.10.2006, 17:38 
Аватара пользователя


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

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

 Профиль  
                  
 
 
Сообщение23.10.2006, 18:06 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение23.10.2006, 18:15 
Заслуженный участник


09/02/06
4382
Москва
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).$

 Профиль  
                  
 
 
Сообщение23.10.2006, 22:20 
Аватара пользователя


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

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

 Профиль  
                  
 
 
Сообщение23.10.2006, 22:44 
Заслуженный участник


09/02/06
4382
Москва
Пусть ваше число Х=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).

 Профиль  
                  
 
 
Сообщение24.10.2006, 06:36 
Аватара пользователя


23/10/06
42
Да, я так и делал, спасибо.

 Профиль  
                  
 
 
Сообщение24.10.2006, 11:15 
Аватара пользователя


23/10/06
42
Ну и еще одна задача:

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

$\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, а это имеет решения в целых числах.

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

 Профиль  
                  
 
 
Сообщение24.10.2006, 11:23 
Модератор
Аватара пользователя


11/01/06
5660
a239 писал(а):
Правильно, или надо по-другому?

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 23 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group