Алкосики 8

Задача 1

1495=5⋅13⋅23 1495 equals 5 times 13 times 23

3156=22⋅3⋅263 3156 equals 2 squared times 3 times 263

792=12⋅66=22⋅36 792 equals 12 times 66 equals 22 times 36

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

mod⁡(3156,5)=1 the mod of open paren 3156 comma 5 close paren equals 1, значит и в любой степени будет 1 1

mod⁡(3156,13)=10 the mod of open paren 3156 comma 13 close paren equals 10, mod⁡(1012⋅66,13)=1 the mod of open paren 10 raised to the 12 times 66 power comma 13 close paren equals 1, т.к. по МТФ mod⁡(1012,13)=1 the mod of open paren 10 to the 12th power comma 13 close paren equals 1

mod⁡(3156,23)=5 the mod of open paren 3156 comma 23 close paren equals 5, mod⁡(522⋅36,23)=1 the mod of open paren 5 raised to the 22 times 36 power comma 23 close paren equals 1, т.к. по МТФ mod⁡(522,23)=1 the mod of open paren 5 to the 22nd power comma 23 close paren equals 1

Задача 2

Пусть b=a⁢q b equals a q. Тогда 2b-1=2a⁢q-1=(2a-1)⁢(2a⁢(q-1)+2a⁢(q-2)+…+2a+1) 2 to the b-th power minus 1 equals 2 raised to the a q power minus 1 equals open paren 2 to the a-th power minus 1 close paren times open paren 2 raised to the a times open paren q minus 1 close paren power plus 2 raised to the a times open paren q minus 2 close paren power plus dot dot dot plus 2 to the a-th power plus 1 close paren, то есть 2b-1|2a-1 2 to the b-th power minus 1 divides 2 raised to the a minus 1 power

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

2n-1=k1⋅(2q-1), 2 to the n-th power minus 1 equals k sub 1 times open paren 2 to the q-th power minus 1 close paren comma

2m-1=k2⋅(2q-1) 2 to the m-th power minus 1 equals k sub 2 times open paren 2 to the q-th power minus 1 close paren

Получается, что (2m-1,2n-1)=2(n,m)-1 open paren 2 to the m-th power minus 1 comma 2 to the n-th power minus 1 close paren equals 2 raised to the open paren n comma m close paren power minus 1

Задача 3

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

aϕ⁡(b)+bϕ⁡(a)≡bϕ⁡(a)⁢mod⁡(a) a raised to the phi of b power plus b raised to the phi of a power is identical to b raised to the phi of a power mod a

По теореме эйлера bϕ⁡(a)≡1⁢mod⁡(a) b raised to the phi of a power is identical to 1 mod a, значит и aϕ⁡(b)+bϕ⁡(a)≡1⁢mod⁡(a) a raised to the phi of b power plus b raised to the phi of a power is identical to 1 mod a

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

Задача 4

1⋅2⋅3⋅…⋅(p-1) 1 times 2 times 3 times dot dot dot times open paren p minus 1 close paren для каждого числа x x есть такой y y из этой же последовательности, что x⁢y≡1. x y is identical to 1 period Если x≡y x is identical to y, то (т.к. p p простое) x2≡1⇒x2-1≡0⇒x≡p+1≡1∨x≡p-1 x squared is identical to 1 right double arrow x squared minus 1 is identical to 0 right double arrow x is identical to p plus 1 is identical to 1 or x is identical to p minus 1

Также, если x1⁢y≡1 x sub 1 y is identical to 1 и x2⁢y≡1 x sub 2 y is identical to 1, то (x1-x2)⁢y≡0⇒x1≡x2 open paren x sub 1 minus x sub 2 close paren times y is identical to 0 right double arrow x sub 1 is identical to x sub 2, то есть все пары уникальны. Получается, что всю последовательность можно разбить на пары, сравнимые по модулю p p с 1 1, значит, (p-1)!≡1 open paren p minus 1 close paren factorial is identical to 1. ЧТД

Задача 5

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

a={2,3,5,7} a equals the set 2 comma 3 comma 5 comma 7

r={1,2,4,6} r equals the set 1 comma 2 comma 4 comma 6

M=2⋅3⋅5⋅7=210 M equals 2 times 3 times 5 times 7 equals 210

Ii I sub i - обратные элементы к mod⁡(Mai,ai) the mod of open paren the fraction with numerator M and denominator a sub i comma a sub i close paren

I={1-1,1-1,2-1,2-1}={1,1,3,4} I equals the set 1 to the negative 1 power comma 1 to the negative 1 power comma 2 to the negative 1 power comma 2 to the negative 1 power equals the set 1 comma 1 comma 3 comma 4

X≡∑𝑖=14(ri⋅Mai⋅Ii)=1⋅105⋅1+2⋅70⋅1+4⋅42⋅3+6⋅30⋅4=1469 X is identical to the sum from i equals 1 to 4 of open paren r sub i times the fraction with numerator M and denominator a sub i times I sub i close paren equals 1 times 105 times 1 plus 2 times 70 times 1 plus 4 times 42 times 3 plus 6 times 30 times 4 equals 1469

Ответ: mod⁡(X,210)=209 the mod of open paren X comma 210 close paren equals 209