сравнение по модул

[nadia]

може ли да ми помогнете за тази задача:

[tex]23^{74}[/tex]? x(mod 91)

[martosss]

23?=529 =74=-17(91)
(-17)?=289=16(91)
16?=256=74=-17(91)
=> ((23?)?)?=23?(91)
[tex]23^8=23^2[/tex]
[tex](23^8)^9=(23^2)^9=23^{18}=23^6=16*(-17)=-272=1(91)[/tex]
[tex]23^{72}=1(91)[/tex]
23?=74
Kato gi umnojim polu4avame [tex]23^{72}*23^2=23^{74}=1*74=74[/tex]
Taka krainiqt otgovor bi trqbvalo da e 74 ako ne burkam v smetkite.

[nikko]

91=7.13 е взаимно просто с 23. Имаме [tex]\varphi(91)=\varphi(7)\varphi(13)=6.12=72[/tex]. По Теоремата на Ойклер-Ферма [tex]\color{red}23^{72}\equiv 1(mod 91)[/tex] и [tex]\color{red}23^2=529\equiv 74(mod 91)[/tex]
Умножаваме двете червени сравнения и получаваме [tex]23^{74}\equiv 74(mod 91)[/tex]

[nadia]

благодаря много