Question

Need the easier methode to find the smallest value of x that satisfies these equations :
x = 4 mod 5
x = 12 mod 13
x = 0 mod 31

Answer 1

What you need is called the Chinese Remainder theorem; this is the best video I've ever found on it https://www.youtube.com/watch?v=ru7mWZJlRQg check that out if you feel like you don't get what I'm saying.

So here's what I do, make x this,

\[x = a*13*31+b*5*31+c*5*13\]
So now notice, when you plug it into each of the congruences,
\[x \equiv a*13*31 \equiv 4 \mod 5\]\[x \equiv b*5*31 \equiv 12 \mod 13\]\[x \equiv c*5*13 \equiv 0 \mod 31\]

Now you can solve for each of a, b, and c. It usually turns out that there will be infinitely many solutions so you can find the smallest by playing with a,b, and c

Answer 2

Actually instead of "playing with a, b, and c" what you can do is when you find some x that works, to minimize it you can subtract off 5*13*31 until you get the smallest number you possibly can that's greater than 0.

Answer 3

thank you very much @Kinui. yeah, it is a CRT problem. thanks for the link of youtube. that's make me running that theorem. now i have the answer from my question, x = 1346. correct ?