5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Pretty sure that it is. $\endgroup$ – d125q Dec 1 '14 at 17:25
9
$\begingroup$

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.

$\endgroup$
  • 9
    $\begingroup$ And the first implies $x$ is even, while the second implies it is odd ... $\endgroup$ – Mark Bennet Dec 1 '14 at 17:32
  • $\begingroup$ 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? $\endgroup$ – Jamgreen Dec 5 '14 at 12:32
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

As $(28,98)=14$

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

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.