Задача по алгебре

Genmaximus

как вычислить 3^560 (mod 561)

Big_Bob

=3*11*17.
560= -1 (mod 11)
560=-1 (mod17 )
3^560 = 0 (mod 3)
3^560 = 3^(-1)=4 (mod 11)
3^560 = 3^(-1)=6 (mod 17)
Пусть теперь 3^560=x (mod 561 0=<x<561, тогда
x=0 (mod 3)
x=4 (mod 11)
x=6 (mod 17)
По китайской теореме об остатках, у этого сравнения существует единственное решение по модулю 561.
x=x1+x2+x3 по модулю 561, где x1 x2 x3 решения систем
x1=0 (mod 3)
x1=0 (mod 11)
x1=0 (mod 17)
x2=0 (mod 3)
x2=4 (mod 11)
x2=0 (mod 17)
x3=0 (mod 3)
x3=0 (mod 11)
x3=6 (mod 17)
x1=0 x2=510 x3=363. Отсюда x=312

stm5345716

Неверное решение

stm5345716

x=0 (mod3)
x=1 (mod11)
x=1 (mod17)

Genmaximus

спасибо

griz_a

С 0 незачем гемориться. Можно искать остаток на 187, потом умножить на 3

stm5345716

Правильный ответ 375, если кому интересно...

Genmaximus

Правильный отв
напишите подробнее, если нетрудно....

griz_a

Ищем остаток 3^559 на 187.
559=-1 mod 10
559=-1 mod 16
(остатка 0 - не бывает )
3^559=4 mod 11
3^559=6 mod 17
Теперь уже по китайской теореме и итоговый результат умножаем на 3.

griz_a

справишься, или китайскую теорему написать?

serengeti

справится, он рюхастый парень

stm5345716

Решение то же с маленькой поправкой
560=0 (mod 10)
560=0 (mod16)
Поэтому
3^560=3^0=1(mod 11*17)

griz_a

можно даже без нее, через анонимусов труд =)
3^{560}=1 mod 187
187*2+1=375=125*3=>
3^559=125 mod 187
Значит 3^560=375 mod 561

Genmaximus

Типа up. Как представить -3/5 в виде целого 7-адического числа?

griz_a

что значит 7 адического?

Genmaximus

В виде бесконечного ряда типа a_{-k}*7^{-k}+...+a_{-2}*7^{-2}+a_{-1}*7^{-1}+a_1+a_2*7+a_3*7^2+...
все 0<=a_i<7

griz_a

Т.е. разложить в семеричную.
А что в нем тогда целого?

griz_a

Так, кстати, нельзя сделать - число отрицаельное, а ряд положительный

stm5345716

Как представить -3/5 в виде целого 7-адического числа?
Поскольку -3/5 целое в точке 7 и взаимно просто с 7, то ряд начнется с нулевой степени. Во-первых, находишь a_0 такое, что a_0=-3/5 (mod 7) <=> 5a_0=-3 (mod 7). a_0=5. Далее берешь (a_0+3/5)/7=4/5. Находишь аналогично a_1=4/5 (mod 7 a_1=5. Берешь (a_1-4/5)/7=3/5. По нему находишь a_2 и т.д. Поскольку -3/5 число рациональное, то последовательность a_j будет периодической. Надо только дойти до момента, когда появится период.
-3/5=a_0+a_1*7+a_2*7^2+...=5+5*7+... (мне лень считать)

stm5345716

Решение было неверное, сорри. Надо брать (-3/5-a_0)/7=-4/5. Далее находить a_1=-4/5(mod 7 a_1=2. Затем брать (-4/5-a_1)/7=-2/5, находить a_2 итд.

stm5345716

Соответственно -3/5=5+2*7+...

Genmaximus

Спасибо, очень помог.
Жесть, оказывается (-3/5)=(5+2*7+7^2+4*7^31+7^4+7^8+...).
Кто бы знал!

stm5345716

Правильно.

stm5345716

На самом деле можно и так. Найти минимальное k такое, что 7^k=1 (mod 5). Если 7^k-1=5A, то
-3/5=3A/(1-7^k)=3A*(1+7^k+7^{2k}+...). осталось расписать 3A в 7-ичной системе счисления.
Оставить комментарий
Имя или ник:
Комментарий: