Алкосики 8

Задача 1

1495=5⋅13⋅23

3156=2^2⋅3⋅263

792=12⋅66=22⋅36

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

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

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

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

Задача 2

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

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

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

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

Получается, что (2^m-1,2^n-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 простое) x^2≡1⇒x^2-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