0
$\begingroup$

enter image description here

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!

$\endgroup$
  • $\begingroup$ The last one you can do it using Chinese Remainder Theorem. $\endgroup$ – Alexei0709 Jun 3 '14 at 20:46
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I have not heard of that $\endgroup$ – user02398409 Jun 3 '14 at 20:51
  • $\begingroup$ OK will supply a method that works irrespective of knowing the CRT. $\endgroup$ – Nicky Hekster Jun 3 '14 at 21:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.