Respuesta :
First, note that [tex]93=3\times31[/tex], which gives
[tex]70x\equiv3\pmod{93}\implies\begin{cases}70x\equiv3\equiv0\pmod3\\70x\equiv3\pmod{31}\end{cases}[/tex]
so in fact we're dealing with the system
[tex]\begin{cases}x\equiv17\pmod{23}\\70x\equiv0\pmod3\\70x\equiv3\pmod{31}\end{cases}[/tex]
Now, 3, 23, and 31 are relatively prime, so we can use the Chinese remainder theorem. But before we do that, we need to rework and ultimately eliminate the coefficients of [tex]x[/tex].
From the second equivalence, it follows immediately [tex]x[/tex] is some multiple of 3; this is because [tex]70x[/tex] is divisible by 3, but 3 doesn't divide 70, so it must divide [tex]x[/tex].
For the third equivalence, we can write [tex]70x=62x+8[/tex]. Then modulo 31, we have that [tex]62x\equiv0[/tex], which leaves us with [tex]8x\equiv3\pmod{31}[/tex]. We want a congruence of the form [tex]x\equiv\cdots[/tex], and to get that we can multiply [tex]8x[/tex] and 3 by the inverse of 8 modulo 31.
To find this inverse, we solve for [tex]y[/tex] in the relation
[tex]8y\equiv1\pmod{31}[/tex]
by using the Euclidean algorithm, or making just making the observation that [tex]8\times4\equiv32\equiv1\pmod{31}[/tex], so [tex]8^{-1}\equiv4\pmod{31}[/tex]. Distributing 4 across the third equivalence in our system gives [tex]x\equiv4\pmod{31}[/tex].
So to recap, we now have
[tex]\begin{cases}x\equiv17\pmod{23}\\x\equiv0\pmod3\\x\equiv12\pmod{31}\end{cases}[/tex]
and we're ready to use the CRT.
As a starting point, let's take
[tex]x=(17)+(23)+(23)=63[/tex]
It's clear that taken modulo 23, the latter two terms vanish and we have a remainder of 17, as desired. 63 is already a multiple of 3, but just to avoid doing more work later, let's multiply each term by 3 anyway to keep getting a remainder of 0:
[tex]x=(17\times3)+(23\times3)+(23\times3)=146[/tex]
Now multiply the first two terms by 31 to make sure they vanish when taken modulo 31. Meanwhile, [tex]23\times3\equiv69\equiv7\pmod{31}[/tex], but we want to get 12, so we would multiply this term by the inverse of 7 mod 31, and again by 12.
We can make a quick observation that [tex]7\times9=63=31\times2+1[/tex], so [tex]7^{-1}\equiv9\pmod{31}[/tex]. Alternatively, you can use the Euclidean algorithm to find this inverse. Either way, we get
[tex]x=(17\times3\times31)+(23\times3\times31)+(23\times3\times9\times12)=11,172[/tex]
So we're told that
[tex]x=11,172+(23\times3\times31)k=11,172+2139k[/tex]
is our solution set, where [tex]k\in\mathbb Z[/tex]. We can "simplify" this slightly by finding the least positive residue modulo the product of our moduli, which would be
[tex]11,172\equiv477\pmod{2139}[/tex]
so we end up with
[tex]x=477+2139k[/tex]
for integers [tex]k[/tex].
[tex]70x\equiv3\pmod{93}\implies\begin{cases}70x\equiv3\equiv0\pmod3\\70x\equiv3\pmod{31}\end{cases}[/tex]
so in fact we're dealing with the system
[tex]\begin{cases}x\equiv17\pmod{23}\\70x\equiv0\pmod3\\70x\equiv3\pmod{31}\end{cases}[/tex]
Now, 3, 23, and 31 are relatively prime, so we can use the Chinese remainder theorem. But before we do that, we need to rework and ultimately eliminate the coefficients of [tex]x[/tex].
From the second equivalence, it follows immediately [tex]x[/tex] is some multiple of 3; this is because [tex]70x[/tex] is divisible by 3, but 3 doesn't divide 70, so it must divide [tex]x[/tex].
For the third equivalence, we can write [tex]70x=62x+8[/tex]. Then modulo 31, we have that [tex]62x\equiv0[/tex], which leaves us with [tex]8x\equiv3\pmod{31}[/tex]. We want a congruence of the form [tex]x\equiv\cdots[/tex], and to get that we can multiply [tex]8x[/tex] and 3 by the inverse of 8 modulo 31.
To find this inverse, we solve for [tex]y[/tex] in the relation
[tex]8y\equiv1\pmod{31}[/tex]
by using the Euclidean algorithm, or making just making the observation that [tex]8\times4\equiv32\equiv1\pmod{31}[/tex], so [tex]8^{-1}\equiv4\pmod{31}[/tex]. Distributing 4 across the third equivalence in our system gives [tex]x\equiv4\pmod{31}[/tex].
So to recap, we now have
[tex]\begin{cases}x\equiv17\pmod{23}\\x\equiv0\pmod3\\x\equiv12\pmod{31}\end{cases}[/tex]
and we're ready to use the CRT.
As a starting point, let's take
[tex]x=(17)+(23)+(23)=63[/tex]
It's clear that taken modulo 23, the latter two terms vanish and we have a remainder of 17, as desired. 63 is already a multiple of 3, but just to avoid doing more work later, let's multiply each term by 3 anyway to keep getting a remainder of 0:
[tex]x=(17\times3)+(23\times3)+(23\times3)=146[/tex]
Now multiply the first two terms by 31 to make sure they vanish when taken modulo 31. Meanwhile, [tex]23\times3\equiv69\equiv7\pmod{31}[/tex], but we want to get 12, so we would multiply this term by the inverse of 7 mod 31, and again by 12.
We can make a quick observation that [tex]7\times9=63=31\times2+1[/tex], so [tex]7^{-1}\equiv9\pmod{31}[/tex]. Alternatively, you can use the Euclidean algorithm to find this inverse. Either way, we get
[tex]x=(17\times3\times31)+(23\times3\times31)+(23\times3\times9\times12)=11,172[/tex]
So we're told that
[tex]x=11,172+(23\times3\times31)k=11,172+2139k[/tex]
is our solution set, where [tex]k\in\mathbb Z[/tex]. We can "simplify" this slightly by finding the least positive residue modulo the product of our moduli, which would be
[tex]11,172\equiv477\pmod{2139}[/tex]
so we end up with
[tex]x=477+2139k[/tex]
for integers [tex]k[/tex].