Find a number that satisfies two congruences

Question

I have an exercise of finding a number that satisfies two congruences.

$$ \left\{ \begin{array}{cc} x &\equiv 10 \mod 30 \\ x &\equiv 5 \mod 101 \end{array} \right. $$

The exercise suggests 4 steps to solve:

Step 1: find integers $s$ and $t$ such as $30s + 101t = 1$

Step 2: use s and t to find a number satisfying:

$$ \left\{ \begin{array}{cc} a &\equiv 10 \mod 30 \\ a &\equiv 0 \mod 101 \end{array} \right. $$

Step 3: use s and t to find a number satisfying:

$$ \left\{ \begin{array}{ccc} b &\equiv& 0 \mod 30 \\ b &\equiv& 5 \mod 101 \end{array} \right. $$

Step 4: use the result from step 2 or 3 to find x. ($x \equiv 10 \mod 30 $,$x \equiv 5 \mod 101$)

I went through the first 3 steps without problems, but I dont't know how to do step 4 since I could also use s and t to find x (without going to step 2 or 3).

Thank you

Answer 1

writing $$x=10+30m$$ and $$x=5+101n$$ where $m,n$ are integers. From here we get $$5=101n-30m$$ this is an linear Diophantine equation in $m,n$.Solving this equation we get $$n=84+101C,n=25+30C$$ where $C$ is an integer

Answer 2

Since $\gcd(30,101)=1$ by CRT we know that an unique solution exists $\mod{30\cdot101}$, notably

• $x \equiv 10 \mod 30\implies x=10+30k$
• $x \equiv 5 \implies10+30k\equiv5\implies30k\equiv96\mod 101$

thus we need to find the inverse of $30 \mod 101$ by Euclidean algorithm that is $64$ indeed

$$64\cdot30-101\cdot19=1$$

then

• $30k\equiv96 \mod 101\implies64\cdot30k\equiv 64\cdot96\mod 101 \implies k\equiv 84 \mod 101$

and

• $x=10+30k=10+30\cdot(84+101s)=2530+30\cdot101s$

$$\implies x\equiv 2530 \mod 30\cdot 101$$

Answer 3

Well, I solved it using a logical approach.

We can see that

$x - 10 = 30a$

and

$x - 5 = 101b$

($a$ and $b$ are random whole numbers)

Now if we observe, it's very clear that $x$ is a multiple of $10$. Also $b$ in the second equation will have to be an odd multiple of $5$. So putting some values of $b$, we get,

$x = 510, 1520, 2530,...$ and so on. Out of these values only the ones who have $b$ of the format $5(6k - 1)$ fulfill both the conditions of equation $1$ and $2$. Putting $b = 5(6k - 1)$ in equation $2$ we get, the following,

$x = 10(303k - 50)$ where $k$ is any natural number.

Feel free to correct me if I am wrong anywhere and improve the answer.

Answer 4

The second congruence implies there exists $m$ such that $$x=101m+5.$$ Substituting this into the first congruence gives $$101m+5\equiv 10\bmod 30.$$ Now, reducing this gives $$11m+5\equiv 10\bmod 30.$$ This simplifies to $$11m\equiv 5\bmod 30,$$ $$m\equiv 25\bmod 30.$$ Then, this means there exists an $n$ such that $$m=30n+25.$$ Substituting this in the first equation involving $x$ gives $$x=101(30n+25)+5,$$ that is $$x=3030n+2530,$$ implying that $x\equiv 2530\bmod 3030.$