1
$\begingroup$

$$560x \equiv 1 \pmod{3, 11, 13}$$

I found a few (by trial and error)

$560x \equiv 1 \pmod{13} \implies x = 1 + 13k$.

$560x \equiv 1 \pmod{3} \implies x = 2 + 3k$.

$560x \equiv 1 \pmod{11}$ Is the hard congruence.

I am trying to use Euclid;s algorithm,

$560 = 50(11) + 10$ and $11 = 1(10) + 1 \implies 1 = 11 - 10$

$$\implies 1 = 11 - (560 - 50(11))$$

But how do I proceed with Euclid's algorithm? the actual answer is: $x = 10 + 11k$ (wolframalpha) so

$x \equiv 1 \pmod{13}$

$x \equiv 2 \pmod{3}$

$x \equiv 10 \pmod{11}$.

then by the chinese remainder theorem there is one solution $\pmod{429}$. But how should I solve it?

$\endgroup$
  • $\begingroup$ Hint: the last two congruences can be rewritten as $x\equiv-1$ modulo both 3 and 11. Hence they are both solved when $x\equiv-1\;mod(33)$. $\endgroup$ – lulu Aug 8 '15 at 16:00
0
$\begingroup$

The general strategy for any system of congruence equations

$x \equiv r_1 \pmod{n_1}$

$\vdots$

$x \equiv r_k \pmod{n_k}$

where $n_1, \cdots n_k$ are pairwise coprime, is to first find a $k$-tuple $(a_1, \cdots , a_k)$ such that

$a_1 \equiv 1 \pmod{n_1}, \quad a_1 \equiv 0 \pmod{n_1^{\prime}}$

$\vdots$

$a_k \equiv 1 \pmod{n_k}, \quad a_k \equiv 0 \pmod{n_k^{\prime}}$

where $n_i^{\prime} = \prod_{j \neq i} n_j$. This is easy to do. Since $n_i$ and $n_i^{\prime}$ are coprime, we can use the extended Euclid's algorithm to find $p$ and $q$ such that $1 = pn_i + qn_i^{\prime}$. Now set $a_i = 1 - pn_i = qn_i^{\prime}$. The required solution is $x=r_1a_1 + \cdots + r_ka_k$.

In this case, using the hint in the comments, the system becomes

$x \equiv 1 \pmod{13}$

$x \equiv -1 \pmod{33}$

Now, $1 = - 65 + 66$, and therefore our $a_1 =66$ and $a_2 = -65$. The final answer is $1\cdot 66 + -1 \cdot -65 = 131$.

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