Respuesta :
Since [tex]527=17\times31[/tex], we have that
[tex]x^{37}\equiv3\mod{527}\implies\begin{cases}x^{37}\equiv3\mod{17}\\x^{37}\equiv3\mod{31}\end{cases}[/tex]
By Fermat's little theorem, and the fact that [tex]37=2(17)+3=1(31)+6[/tex], we know that
[tex]x^{37}\equiv(x^2)^{17}x^3\equiv x^5\mod{17}[/tex]
[tex]x^{37}\equiv(x^1)^{31}x^6\equiv x^7\mod{31}[/tex]
so we have
[tex]\begin{cases}x^5\equiv3\mod{17}\\x^7\equiv3\mod{31}\end{cases}[/tex]
Consider the first case. By Fermat's little theorem, we know that
[tex]x^{17}\equiv x^{16}x\equiv x\mod{17}[/tex]
so if we were to raise [tex]x^5[/tex] to the [tex]n[/tex]th power such that
[tex](x^5)^n\equiv x^{5n}\equiv x\mod{17}[/tex]
we would need to choose [tex]n[/tex] such that [tex]5n\equiv1\mod{16}[/tex] (because [tex]16+1\equiv1\mod{16}[/tex]). We can find such an [tex]n[/tex] by applying the Euclidean algorithm:
[tex]16=3(5)+1[/tex]
[tex]\implies1=16-3(5)[/tex]
[tex]\implies16-3(5)\equiv-3(5)\equiv1\mod{16}[/tex]
which makes [tex]-3\equiv13\mod{16}[/tex] the inverse of 5 modulo 16, and so [tex]n=13[/tex].
Now,
[tex]x^5\equiv3\mod{17}[/tex]
[tex]\implies (x^5)^{13}\equiv x^{65}\equiv x\equiv3^{13}\equiv(3^4)^2\times3^4\times3^1\mod{17}[/tex]
[tex]3^1\equiv3\mod{17}[/tex]
[tex]3^4\equiv81\equiv4(17)+13\equiv13\equiv-4\mod{17}[/tex]
[tex]3^8\equiv(3^4)^2\equiv(-4)^2\mod{17}[/tex]
[tex]\implies3^{13}\equiv(-4)^2\times(-4)\times3\equiv(-1)\times(-4)\times3\equiv12\mod{17}[/tex]
Similarly, we can look for [tex]m[/tex] such that [tex]7m\equiv1\mod{30}[/tex]. Apply the Euclidean algorithm:
[tex]30=4(7)+2[/tex]
[tex]7=3(2)+1[/tex]
[tex]\implies1=7-3(2)=7-3(30-4(7))=13(7)-3(30)[/tex]
[tex]\implies13(7)-3(30)\equiv13(7)equiv1\mod{30}[/tex]
so that [tex]m=13[/tex] is also the inverse of 7 modulo 30.
And similarly,
[tex]x^7\equiv3\mod{31}[/ex]
[tex]\implies (x^7)^{13}\equiv3^{13}\mod{31}[/tex]
Decomposing the power of 3 in a similar fashion, we have
[tex]3^{13}\equiv(3^3)^4\times3\mod{31}[/tex]
[tex]3\equiv3\mod{31}[/tex]
[tex]3^3\equiv27\equiv-4\mod{31}[/tex]
[tex]\implies3^{13}\equiv(-4)^4\times3\equiv256\times3\equiv(8(31)+8)\times3\equiv24\mod{31}[/tex]
So we have two linear congruences,
[tex]\begin{cases}x\equiv12\mod{17}\\x\equiv24\mod{31}\end{cases}[/tex]
and because [tex]\mathrm{gcd}\,(17,31)=1[/tex], we can use the Chinese remainder theorem to solve for [tex]x[/tex].
Suppose [tex]x=31+17[/tex]. Then modulo 17, we have
[tex]x\equiv31\equiv14\mod{17}[/tex]
but we want to obtain [tex]x\equiv12\mod{17}[/tex]. So let's assume [tex]x=31y+17[/tex], so that modulo 17 this reduces to
[tex]x\equiv31y+17\equiv14y\equiv1\mod{17}[/tex]
Using the Euclidean algorithm:
[tex]17=1(14)+3[/tex]
[tex]14=4(3)+2[/tex]
[tex]3=1(2)+1[/tex]
[tex]\implies1=3-2=5(3)-14=5(17)-6(14)[/tex]
[tex]\implies-6(14)\equiv11(14)\equiv1\mod{17}[/tex]
we find that [tex]y=11[/tex] is the inverse of 14 modulo 17, and so multiplying by 12, we guarantee that we are left with 12 modulo 17:
[tex]x\equiv31(11)(12)+17\equiv12\mod{17}[/tex]
To satisfy the second condition that [tex]x\equiv24\mod{31}[/tex], taking [tex]x[/tex] modulo 31 gives
[tex]x\equiv31(11)(12)+17\equiv17\mod{31}[/tex]
To get this remainder to be 24, we first multiply by the inverse of 17 modulo 31, then multiply by 24. So let's find [tex]z[/tex] such that [tex]17z\equiv1\mod{31}[/tex]. Euclidean algorithm:
[tex]31=1(17)+14[/tex]
[tex]17=1(14)+3[/tex]
and so on - we've already done this. So [tex]z=11[/tex] is the inverse of 17 modulo 31. Now, we take
[tex]x\equiv31(11)(12)+17(11)(24)\equiv24\mod{31}[/tex]
as required. This means the congruence [tex]x^{37}\equiv3\mod{527}[/tex] is satisfied by
[tex]x=31(11)(12)+17(11)(24)=8580[/tex]
We want [tex]0\le x<527[/tex], so just subtract as many multples of 527 from 8580 until this occurs.
[tex]8580=16(527)+148\implies x=148[/tex]
[tex]x^{37}\equiv3\mod{527}\implies\begin{cases}x^{37}\equiv3\mod{17}\\x^{37}\equiv3\mod{31}\end{cases}[/tex]
By Fermat's little theorem, and the fact that [tex]37=2(17)+3=1(31)+6[/tex], we know that
[tex]x^{37}\equiv(x^2)^{17}x^3\equiv x^5\mod{17}[/tex]
[tex]x^{37}\equiv(x^1)^{31}x^6\equiv x^7\mod{31}[/tex]
so we have
[tex]\begin{cases}x^5\equiv3\mod{17}\\x^7\equiv3\mod{31}\end{cases}[/tex]
Consider the first case. By Fermat's little theorem, we know that
[tex]x^{17}\equiv x^{16}x\equiv x\mod{17}[/tex]
so if we were to raise [tex]x^5[/tex] to the [tex]n[/tex]th power such that
[tex](x^5)^n\equiv x^{5n}\equiv x\mod{17}[/tex]
we would need to choose [tex]n[/tex] such that [tex]5n\equiv1\mod{16}[/tex] (because [tex]16+1\equiv1\mod{16}[/tex]). We can find such an [tex]n[/tex] by applying the Euclidean algorithm:
[tex]16=3(5)+1[/tex]
[tex]\implies1=16-3(5)[/tex]
[tex]\implies16-3(5)\equiv-3(5)\equiv1\mod{16}[/tex]
which makes [tex]-3\equiv13\mod{16}[/tex] the inverse of 5 modulo 16, and so [tex]n=13[/tex].
Now,
[tex]x^5\equiv3\mod{17}[/tex]
[tex]\implies (x^5)^{13}\equiv x^{65}\equiv x\equiv3^{13}\equiv(3^4)^2\times3^4\times3^1\mod{17}[/tex]
[tex]3^1\equiv3\mod{17}[/tex]
[tex]3^4\equiv81\equiv4(17)+13\equiv13\equiv-4\mod{17}[/tex]
[tex]3^8\equiv(3^4)^2\equiv(-4)^2\mod{17}[/tex]
[tex]\implies3^{13}\equiv(-4)^2\times(-4)\times3\equiv(-1)\times(-4)\times3\equiv12\mod{17}[/tex]
Similarly, we can look for [tex]m[/tex] such that [tex]7m\equiv1\mod{30}[/tex]. Apply the Euclidean algorithm:
[tex]30=4(7)+2[/tex]
[tex]7=3(2)+1[/tex]
[tex]\implies1=7-3(2)=7-3(30-4(7))=13(7)-3(30)[/tex]
[tex]\implies13(7)-3(30)\equiv13(7)equiv1\mod{30}[/tex]
so that [tex]m=13[/tex] is also the inverse of 7 modulo 30.
And similarly,
[tex]x^7\equiv3\mod{31}[/ex]
[tex]\implies (x^7)^{13}\equiv3^{13}\mod{31}[/tex]
Decomposing the power of 3 in a similar fashion, we have
[tex]3^{13}\equiv(3^3)^4\times3\mod{31}[/tex]
[tex]3\equiv3\mod{31}[/tex]
[tex]3^3\equiv27\equiv-4\mod{31}[/tex]
[tex]\implies3^{13}\equiv(-4)^4\times3\equiv256\times3\equiv(8(31)+8)\times3\equiv24\mod{31}[/tex]
So we have two linear congruences,
[tex]\begin{cases}x\equiv12\mod{17}\\x\equiv24\mod{31}\end{cases}[/tex]
and because [tex]\mathrm{gcd}\,(17,31)=1[/tex], we can use the Chinese remainder theorem to solve for [tex]x[/tex].
Suppose [tex]x=31+17[/tex]. Then modulo 17, we have
[tex]x\equiv31\equiv14\mod{17}[/tex]
but we want to obtain [tex]x\equiv12\mod{17}[/tex]. So let's assume [tex]x=31y+17[/tex], so that modulo 17 this reduces to
[tex]x\equiv31y+17\equiv14y\equiv1\mod{17}[/tex]
Using the Euclidean algorithm:
[tex]17=1(14)+3[/tex]
[tex]14=4(3)+2[/tex]
[tex]3=1(2)+1[/tex]
[tex]\implies1=3-2=5(3)-14=5(17)-6(14)[/tex]
[tex]\implies-6(14)\equiv11(14)\equiv1\mod{17}[/tex]
we find that [tex]y=11[/tex] is the inverse of 14 modulo 17, and so multiplying by 12, we guarantee that we are left with 12 modulo 17:
[tex]x\equiv31(11)(12)+17\equiv12\mod{17}[/tex]
To satisfy the second condition that [tex]x\equiv24\mod{31}[/tex], taking [tex]x[/tex] modulo 31 gives
[tex]x\equiv31(11)(12)+17\equiv17\mod{31}[/tex]
To get this remainder to be 24, we first multiply by the inverse of 17 modulo 31, then multiply by 24. So let's find [tex]z[/tex] such that [tex]17z\equiv1\mod{31}[/tex]. Euclidean algorithm:
[tex]31=1(17)+14[/tex]
[tex]17=1(14)+3[/tex]
and so on - we've already done this. So [tex]z=11[/tex] is the inverse of 17 modulo 31. Now, we take
[tex]x\equiv31(11)(12)+17(11)(24)\equiv24\mod{31}[/tex]
as required. This means the congruence [tex]x^{37}\equiv3\mod{527}[/tex] is satisfied by
[tex]x=31(11)(12)+17(11)(24)=8580[/tex]
We want [tex]0\le x<527[/tex], so just subtract as many multples of 527 from 8580 until this occurs.
[tex]8580=16(527)+148\implies x=148[/tex]
