Helping solve mod problems

Question

I am having trouble solving the below problems. My teacher taught us to write out the solutions by hand.. but I really think there is an easier way to do the higher numbers. Thanks!

Answer 1

Hints: $$\text{(a) } 2 \cdot 5 \equiv -1 \text{ (mod 11)}$$ $$ \text{(b) } 5x=10+25k \Leftrightarrow x \equiv 2 \text{ (mod 5)} $$ $$ \text{(c) } 8x=6+16k \Leftrightarrow 4x \equiv 3 \text{ (mod 8) but what happens to numbers multiplied with 4 and then modded by 8?} $$ $$ \text{(d) Have you heard of the Chinese Remainder Theorem?}$$

For (d) you can proceed as follows. From the second equation you get $x=50 + 121k$ $(*)$, where $k$ is an integer. Now mod this equation by $49$, this gives you $x\equiv1+23k \text{ (mod 49)}$, and using the first equation you find $10\equiv1+23k \text{ (mod 49)}$, which means $9\equiv23k \text{ (mod 49)}$. Now (and this requires a bit of calculation (see also here)), the inverse mod $49$ of $23$ is $32$. This yields $k\equiv32\cdot9\equiv43 \text{ (mod 49)}$, write $k=43+49l$, where again $l$ is an integer. So plugging this in $(*)$ we get $x=50+121(43+49l)=5253 +121\cdot49l$ , in other words $x \equiv 5253 \text{ (mod 5929)}$.

This method works always thanks to the fact that gcd$(49,121)=1$ and in general for any pair of positive integers being relatively prime. I leave it to you to do it the other way around, that is, to start with the first equation and proceed in a similar way. Of course it should give you the same solution.