помогите решить сравнение

[igrok15]

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

[Brukvalub]

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

[igrok15]

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

[Brukvalub]

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

[PAV]

А говоря проще

$[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$

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

[bot]

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. Даже я, слабый в арифметике, кажется не ошибся. Вернее, был сбой в пределах
таблицы умножения, но успел исправить до отправки.

[Батороев]

В данном примере можно представить 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" инженерного калькулятора Вашего компьютера

[bot]

Батороев писал(а):

В данном примере можно представить 70 = 64 +6 ...

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

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

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

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

[Батороев]

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


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

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

[ИСН]

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

[Батороев]

Сам подумал, да и ИСН, спа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).
Остатки рассчитывают, определяют, сравнивают и т.д., а поиском чаще занимаются чисел с заданными остатками.