1
$\begingroup$

$$\eqalign{ x &\equiv 5 \mod 15\cr x &\equiv 8 \mod 21\cr}$$

The extended Euclidean algorithm gives $x≡50 \bmod 105$.

I understand now that if we combine the two it implies $15a-21b = 3$ but I don't understand how to use the extended GCD to go from there to finding $x$ and the corresponding modulus.

This is what I am using for the extended gcd computations:

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

From https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm#Python

$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

Since the GCD of the moduli is $(15,21)=3$, it is necessary that $x$ be the same thing in both equations mod $3$. That is, $$ x\equiv5\pmod{15}\implies x\equiv2\pmod{3} $$ and $$ x\equiv8\pmod{21}\implies x\equiv2\pmod{3} $$ If we didn't get that $x\equiv2\pmod{3}$ from both equations, a solution would not be possible.

This prompts us to look at $\frac{x-2}3\pmod{\frac{15}3}$ and $\frac{x-2}3\pmod{\frac{21}3}$. That is, $$ \frac{x-2}3\equiv1\pmod{5}\tag{1} $$ and $$ \frac{x-2}3\equiv2\pmod{7}\tag{2} $$

Using the Extended Euclidean Algorithm as implemented in this answer, $$ \begin{array}{r} &&1&2&2\\\hline 1&0&1&-2&5\\ 0&1&-1&3&-7\\ 7&5&2&1&0 \end{array}\tag{3} $$ we get that $$ \underbrace{5(3)}_{\large\color{#C00000}{15}}+\underbrace{\!7(-2)\!}_{\large\color{#00A000}{-14}}=1\tag{4} $$ We can use $(4)$ to see that $$ \begin{align} \color{#00A000}{-14}&\equiv\color{#0000F0}{1}\pmod{5}\\ \color{#00A000}{-14}&\equiv\color{#0000F0}{0}\pmod{7} \end{align}\tag{5} $$ and that $$ \begin{align} \color{#C00000}{15}&\equiv\color{#0000F0}{0}\pmod{5}\\ \color{#C00000}{15}&\equiv\color{#0000F0}{1}\pmod{7} \end{align}\tag{6} $$ To solve $(1)$ and $(2)$ we can add $1$ times $(5)$ to $2$ times $(6)$ to get $$ \begin{align} 16&\equiv\color{#0000F0}{1}\pmod{5}\\ 16&\equiv\color{#0000F0}{2}\pmod{7} \end{align}\tag{7} $$ Equations $(7)$ tell us that $\frac{x-2}3\equiv16\pmod{35}$ or that $$ \bbox[5px,border:2px solid #C0A000]{x\equiv50\pmod{105}}\tag{8} $$

$\endgroup$
20
  • $\begingroup$ Replacing $x$ with $(x-2)/3$ is likely too clever and unmotivated for the OP's interests. The OP wants a systematic method. Also, the OP should have linked to their previous question. $\endgroup$
    – anon
    Jul 29, 2015 at 3:10
  • $\begingroup$ @anon: Actually, the process behind getting $(1)$ and $(2)$ is almost necessary in order to solve the problem. Perhaps what I need to do is to motivate what I did to get those lines. Editing... $\endgroup$
    – robjohn ♦
    Jul 29, 2015 at 3:17
  • $\begingroup$ How did you get the righthand 1 in (x-2)/3 = 1 mod 5, and how did you get the righthand 2 in (x-2)/3 = 2 mod 7? $\endgroup$
    – user2597879
    Jul 29, 2015 at 3:49
  • $\begingroup$ @user2597879: $\frac{5-2}3=1$ for the mod $5$ equation and $\frac{8-2}{3}=2$ for the mod $7$ equation. Note that if $x\equiv ab\pmod{am}$, then $a\mid x$ and $\frac xa\equiv b\pmod{m}$. $\endgroup$
    – robjohn ♦
    Jul 29, 2015 at 3:59
  • $\begingroup$ @user2597879: no. Take a look at the end of my last comment. Since $x-2\equiv 3\pmod{15}$, we know that $3\mid x-2$, so the division is actual division, not modular division. $\endgroup$
    – robjohn ♦
    Jul 29, 2015 at 4:06
0
$\begingroup$

It's a bit simpler if we proceed as follows

$\bmod 15\!:\,\ 5\equiv x\equiv 8\!+\!21\,\color{#c00}k\equiv 8\!+\!6k\ \ \overbrace{\!\!\iff 6k\equiv -3\iff\bmod\color{#c00} 5\!:\,\ 2k\equiv -1}^{\Large\! 15j\,+\,6k\ =\ -3\ \ \ \ \overset{\LARGE (\ \ )/3}\iff\ \ \ \ 5j\,+\,2k\ =\ -1 }\equiv 4\iff \color{#c00}{k\equiv 2}$

So we conclude $\, x = 8\!+\!21(\color{#c00}{2\!+\!5}n) = 50\! +\! 105n$

Remark $ $ See here for the general method of transforming the Bezout solution into a CRT solution.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .