2014 dxdy logo

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

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


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


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

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

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

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

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



Начать новую тему Ответить на тему
 
 помогите решить сравнение
Сообщение13.01.2007, 09:47 


22/11/06
11
$2^7^0 + 3^7^0\equiv x (mod 13)$
Найти остаток от деления (т.е. х)

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


01/03/06
13626
Москва
Можно представить $2^{70}  = 1024^7  = (78 \cdot 13 + 10)^7  \equiv 10^7  = 769230 \cdot 13 + 10$ и аналогично поступить со вторым слагаемым. Тогда взятая по модулю 13 сумма остатков и даст ответ.

 Профиль  
                  
 
 
Сообщение13.01.2007, 10:28 


22/11/06
11
Спасибо большое! а можно еще вопрос: есть какйто то способ поиска остатков или это просто интуиция?

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


01/03/06
13626
Москва
Решение сравнений-это неплохо разработанная тема из элементарной теории чисел. См., например, соответствующую главу в книге http://lib.mexmat.ru/books/4639 , и ранее указанные Maxal-ом лекции http://www.allmath.ru/highermath/algebr ... hisel-ugu/

 Профиль  
                  
 
 
Сообщение13.01.2007, 11:09 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
А говоря проще

$[a\cdot b] \mod m = [(a \mod m)\cdot(b \mod m)] \mod m$

$[a+b] \mod m = [(a \mod m)+(b \mod m)] \mod m$

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

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


21/12/05
5904
Новосибирск
igrok15 писал(а):
есть какйто то способ поиска остатков или это просто интуиция?

А почему про малую теорему Ферма никто не сказал?
Хотя ссылку же дали, а там уж точно есть. Ну да сформулирую непосредственно:

Если $x$ не делится на простое число $p$, то $x^{p-1}\equiv 1 (mod p)$

Для данной задачи имеем:

$2^{70}+3^{70}=(2^{12})^5 \cdot 2^{10}+(3^{12})^5 \cdot 3^{10} \equiv 2^{10}+3^{10}=$

$16\cdot 16 \cdot 4 + 27\cdot 27 \cdot 27 \cdot 3 \equiv 3 \cdot (3 \cdot 4) + 1\cdot 1 \cdot 1\cdot 3 \equiv $

$3\cdot (-1) +3 \equiv 0 (mod 13)$

P.S. Даже я, слабый в арифметике, кажется не ошибся. Вернее, был сбой в пределах
таблицы умножения, но успел исправить до отправки. :D

 Профиль  
                  
 
 помогите решить сравнение
Сообщение24.01.2007, 21:29 


23/01/07
3415
Новосибирск
В данном примере можно представить 70 = 64 +6
(Извиняюсь, но я на этом форуме первый день и теги еще не освоил).
2^4=3 mod(13), 3^4 = 3 mod(13).
2^8=(3*3)mod(13), 3^8=(3*3) mod(13)
2^16=(3*3*3*3)mod(13)= 3 mod(13), , 3^64=(3*3*3*3) mod(13)=3 mod(13)
2^32=(3*3) mod(13), 3^32=(3*3) mod(13)
2^64=(3*3*3*3) mod(13)=3 mod(13), 3^64 = (3*3*3*3) mod(13) = 3 mod(13)
2^6 =(-1) mod(13), 3^6=1mod(13)
2^70=[(-1)*3]mod(13), 3^70=(1*3)mod(13)
2^70 + 3^70 = 0 mod(13)
Этот метод при небольших степенях проигрывает тем, что показали другие участники обсуждения, но на очень больших - будет иметь преимущество и его необходимо знать.

p.s. А для проверки своих решений рекомендую использовать кнопку "Mod" инженерного калькулятора Вашего компьютера :)

 Профиль  
                  
 
 Re: помогите решить сравнение
Сообщение25.01.2007, 09:15 
Заслуженный участник
Аватара пользователя


21/12/05
5904
Новосибирск
Батороев писал(а):
В данном примере можно представить 70 = 64 +6 ...


Не вижу здесь никакого метода - Вы последовательно вычисляете степени по модулю 13.
Чем это лучше теоремы Ферма, которая сразу сводит большую степень к меньшей? :roll:

Если уж на то пошло, то уж тогда скрытое прошлый раз:

$2^{70}+3^{70}=4^{35}+9^{35}=(4+9) \cdot ( 4^{34} - 4^{33}\cdot 9+4^{32}\cdot 9^2- ... +9^{34})$

В прошлый раз выбрал более универсальное средство, которое действительно надо знать.
А скрытое заставило искать случившийся арифметический сбой.

 Профиль  
                  
 
 Это - не мое "детище".
Сообщение25.01.2007, 16:19 


23/01/07
3415
Новосибирск
Г-н bot писал: Не вижу здесь никакого метода - Вы последовательно вычисляете степени по модулю 13.
Чем это лучше теоремы Ферма, которая сразу сводит большую степень к меньшей?


Такой метод мне показал один математик, котрый, по-видимому, занимается исследованием очень больших чисел (ОБЧ). Он уверял, что так эффективней.
Лично я, ОБЧ никогда не занимался, но по некоторым признакам, в частности, как составлен тест Миллера-Рабина, не поверить ему не могу.
Проверка производится все же не последовательно, а по степеням двойки, а это несколько другое.

Кроме того, предлагаемый Вами способ нельзя применить к расчету остатков степеней чисел по основанию, которое превосходит эти степени, а это используется кругом и рядом. Даже при тестировании чисел по самой Малой теореме Ферма.

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


18/05/06
13435
с Территории
Дело не в том, что так эффективнее (в приведённом примере с маленькими числами это, очевидно, не так); дело в том, что если вместо 13 стоит число, которое весьма велико и разложение его на простые неизвестно, то неизвестна и функция Эйлера от него, а значит, теорема Ферма не поможет, и извольте колупаться с прямым вычислением.
А так-то, конечно, легче через неё, родимую.

 Профиль  
                  
 
 Мы, каждый, правы по-своему.
Сообщение25.01.2007, 18:48 


23/01/07
3415
Новосибирск
Сам подумал, да и ИСН, спаcибо ему, надоумил.

Если заранее известно, что основание - простое число и рассматриваемые степени превосходят основание, особенно, если многократно, то эту "кратность" необходимо устранить, естественно, с применением Малой теоремы Ферма:
70 = 10mod(13-1)
2^10 = 10mod(13), 3^10 = 3 mod(13)
(10+3) = 0 mod(13)
В остальных случаях, напрашивается использование других способов, одним из которых является тот, о котором я упомянул.

Автор пилотного сообщения спрашивал: "...есть какой-то способ поиска остатков?"

Остатки никто и не терял. Чтобы понять это, необходимо знать то, что "остатки от деления", иначе, можно раасматривать, как, выраженные в десятичной форме,окончания чисел в той или иной системе счисления, (в Вашем примере - 13-чной СС), которые имеют строго определенный порядок (0,1,2,3,4...0,1,2).
Остатки рассчитывают, определяют, сравнивают и т.д., а поиском чаще занимаются чисел с заданными остатками.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

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



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

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


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

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