# System of congruence equations

I have a system of congruence eqs

$$\begin{cases} x \equiv 14 \pmod{98} \\ x \equiv 1 \pmod{28} \end{cases}$$

I have calculated $\text{gcd}(98,28) = 14$.

I can from the congruence eqs get $x = 14+98k$ and $x = 1+28m$.

I equate these

$$14+98k = 1+28m \Leftrightarrow 28m - 98k = 13$$

I know that $\text{gcd}(98,28) = 14$ is not divisible by 13 and therefore the system has no solutions.. Is this correct?

• Pretty sure that it is. – d125q Dec 1 '14 at 17:25

You are right, but this is faster:

$x\equiv 14\pmod{98}$ implies that $x$ is a multiple of $7$, but $x\equiv 1\pmod{28}$ implies that it isn't.

• And the first implies $x$ is even, while the second implies it is odd ... – Mark Bennet Dec 1 '14 at 17:32
• I need to understand the intuition. Why is my example correct because 14 is not divisble by 13? Is it because I would normally find an $r$ and $s$ such that $98 r + 28 s = \text{gcd}(98,28)$ and because $\text{gcd}(98,28)$ equals 14 and not 13 the system has no solutions? I can see that $x \equiv 14 \pmod{98}$ implies that $x = 14 + 98k$ which means that $x$ is a multiple of $7$ and that $x \equiv 1 \pmod{28}$ implies that $x = 1+28 m$ which means that $x$ is a multiple of $3$ or $19$ and from that conclude that it has no solutions. But what if the numbers were much more difficult? – Jamgreen Dec 5 '14 at 12:32

It is correct. If you look at $28m-98k=2(14m-49k)=13$, you immediately have the left hand side being even whereas the right hand side is odd, contradiction.

we get by definition $$x=14+98k_1$$ and $$x=1+28k_2$$ with $k_1,k_2$ are integers, thus we get $$98k_1-28k_2=-13$$ this equation has no solutions, why?

As $(28,98)=14$

$$x\equiv14\pmod{98}\equiv14\pmod{14}\equiv0$$

and $$x\equiv1\pmod{28}\equiv1\pmod{14}$$ which is impossible

Hint: you have $x= 14= 0 \mod(\gcd(98,28)) \neq 1 \mod(\gcd(98,28))$ which means the system hasn't a solution