3
$\begingroup$

Solve simultaneous systems of congruences $x\equiv 10 \pmod{60}$ and $x\equiv 80 \pmod{350}$

How does one solve this using CRT? Because it has duplicate primes in its factorization? I got

$$350=5*5*2*7$$
$$60=2*2*3*5$$

So I tried CRT with

$x\equiv 1\pmod3, x\equiv0\pmod5, x\equiv0 \pmod2, x\equiv3 \pmod7$ and got the wrong answer.

or should it be
$x\equiv 1\pmod3, x\equiv5\pmod{25}, x\equiv2\pmod4, x\equiv3\pmod7$

$\endgroup$
1
  • $\begingroup$ it should be the latter $\endgroup$ Dec 1 '19 at 0:23
1
$\begingroup$

Your work will be greatly simplify using the formula for the solutions of a system of two simultaneous congruences with coprime moduli $a$ and $b$ based on Bézout's identity $$ua+vb=1,\qquad(u,v\in\mathbf Z):$$ $$\begin{cases} x\equiv \alpha\mod a\\x\equiv\beta\mod b \end{cases}\iff x\equiv\beta\,ua+\alpha\,vb\mod ab.$$ Now your congruences are equivalent to $\begin{cases}x'\equiv 1\mod 6\\x'\equiv8\mod 35 \end{cases}$ and $x\equiv 10x'\mod60\cdot 350$.

Added:

The given congruences mean there exist $k,l \in\mathbf Z$ such that $x=10+60k=80+350l$, i.e. $x=10(1+6k)=10(8+35l)$, so $1+6k=8+35l$, which I denote $x'$, whence the simplified system of congruences and the relation between $x$ and $x'$. congruences

$\endgroup$
3
  • 1
    $\begingroup$ Sorry could you show your steps I'm a bit confused $\endgroup$ Nov 30 '19 at 10:22
  • $\begingroup$ @user8714896, first you reduce your mods $60$ and $350$ by dividing them by their greatest common divisor $10$, getting relatively prime mods $6$ and $35$, and the induced congruences (divide by $\gcd$). THEN you solve the obtained reduced system. Then unreduce (multiply by $\gcd$). $\endgroup$
    – Wlod AA
    Nov 30 '19 at 10:44
  • $\begingroup$ @user8714896: I've added an explanation. Is that clearer? $\endgroup$
    – Bernard
    Nov 30 '19 at 11:00
0
$\begingroup$

When the moduli are not coprime there may not be a solution. With a small system, it's probably better to solve in the following fashion so that you can see when and why a contradiction arises:

From the first congruence you have $x=10+60y$. Plug that into the second congruence to get

$$10+60y \equiv 80 \pmod{350}$$

$$60y \equiv 70 \pmod{350}$$

$$6y \equiv 7 \pmod{35}$$

$6$ is its own inverse mod $35,$ so we have

$$y \equiv 42 \equiv 7 \pmod{35}$$ or $y=42+35k$.

Then $x = 10 + 60 (42 +35k) = 2530+2100 k$, or if you shift $k$ by one, $x = 430 +2100k$.

$\endgroup$
2
  • $\begingroup$ What do you mean by "$6$ is its own inverse $\pmod{35}$"? Do you mean $6\equiv6^{-1}\pmod{35}$? $\endgroup$
    – manooooh
    Dec 1 '19 at 1:00
  • 1
    $\begingroup$ @manooooh Yes. $6\cdot 6 \equiv 1 \pmod{35}.$ $\endgroup$
    – B. Goddard
    Dec 1 '19 at 2:23
0
$\begingroup$

It should be $\color{magenta}{x\equiv 1\pmod3}, \color{blue}{x\equiv5\pmod{25}}, \color{magenta}{x\equiv2\pmod4,} \color{brown}{x\equiv3\pmod7}$.

From $\color{magenta}{x\equiv-2\pmod{3,4}} $ we get $x\equiv-2\equiv10\mod12.$

From $x\equiv10\pmod{12}$ and $\color{blue}{x\equiv5\pmod{25}},$ we get $x\equiv130\pmod{300}$.

From $x\equiv130\pmod{300}$ and $\color{brown}{x\equiv3\pmod7}$, we get $x\equiv430\pmod{2100}$.

$\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.