Алкосики 8

Задача 1

1495=5⋅13⋅23

3156=22⋅3⋅263

792=12⋅66=22⋅36

Все три множителя модуля взаимно просты, так что попробуем воспользоваться КТО:

mod(3156,5)=1, значит и в любой степени будет 1

mod(3156,13)=10, mod(10(12⋅66),13)=1, т.к. по МТФ mod(1012,13)=1

mod(3156,23)=5, mod(5(22⋅36),23)=1, т.к. по МТФ mod(522,23)=1

Задача 2

Пусть b=a*q. Тогда 2b-1=2(a*q)-1=(2a-1)*(2(a*(q-1))+2(a*(q-2))+…+2a+1), то есть 2b-1|2(a-1)

Тогда, пусть n=q*x,m=q*y.

2n-1=(k_1)⋅(2q-1),

2m-1=(k_2)⋅(2q-1)

Получается, что (2m-1,2n-1)=2(n,m)-1

Задача 3

Так как (a,b)=1, достаточно сравнить по модулям a и b отдельно:

aϕ(b)+bϕ(a)≡bϕ(a)*mod(a)

По теореме эйлера bϕ(a)≡1*mod(a), значит и aϕ(b)+bϕ(a)≡1*mod(a)

Аналогично, выражение сравнимо с 1 по модулю b. Тогда, по КТО все это выражение сравнимо с 1 по модулю a*b. ЧТД

Задача 4

1⋅2⋅3⋅…⋅(p-1) для каждого числа x есть такой y из этой же последовательности, что x*y≡1. Если x≡y, то (т.к. p простое) x2≡1⇒x2-1≡0⇒x≡p+1≡1∨x≡p-1

Также, если (x_1)*y≡1 и (x_2)*y≡1, то ((x_1)-(x_2))*y≡0⇒(x_1)≡(x_2), то есть все пары уникальны. Получается, что всю последовательность можно разбить на пары, сравнимые по модулю p с 1, значит, (p-1)!≡1. ЧТД

Задача 5

Используем КТО:

a={2,3,5,7}

r={1,2,4,6}

M=2⋅3⋅5⋅7=210

(I_i) - обратные элементы к mod(M/(a_i),(a_i))

I={1(-1),1(-1),2(-1),2(-1)}={1,1,3,4}

X≡(∑_𝑖=1^4)((r_i)⋅M/(a_i)⋅(I_i))=1⋅105⋅1+2⋅70⋅1+4⋅42⋅3+6⋅30⋅4=1469

Ответ: mod(X,210)=209