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].