1
$\begingroup$

Using the facts that $1591=37.43$ and $51=3.17$ compute 1591 mod 51 using the Chinese Remainder Theorem.

I started off by letting $x \equiv 1591 \mod 51$ which I then wrote as $x \equiv 1591 \mod 17$ and $x \equiv 1591 \mod 3$ using the information I have been given and rules of modular arithmetic (??). From here I used $37.43$ to give $37 \equiv 3 \mod 17$ and $43 \equiv 9\mod 17$ but I do not know how to go from here.

$\endgroup$
1
  • 3
    $\begingroup$ Just saying, I would have just divided. $\frac{1591} {51}$ $\endgroup$
    – N.S.JOHN
    May 21 '16 at 13:04
1
$\begingroup$

Hint:

The Chinese remainder theorem says that the (well-defined) map \begin{align*} \mathbf Z/51\mathbf Z&\longrightarrow \mathbf Z/3\mathbf Z\times \mathbf Z/17\mathbf Z\\x\bmod51&\longmapsto (x\bmod3,x\bmod17) \end{align*} is a ring isomorphism. obtained through Bézout's relation between $3$ and $17$: $\;6\cdot 3- 17=1$, and it maps $(\alpha,\beta)$ to $\;(\beta\cdot6\cdot 3-\alpha\cdot 17)\bmod 51$.

Some details:

$37\bmod51$ maps to $(37\bmod3,37\bmod17)=(1,3)$ by the C.R.T.

Similarly, $43\bmod51$ maps to $(1,9)$. Hence $1591=37\cdot43$ maps to $\;(1,3)\cdot(1,9)=(1,10)$. Thus by the inverse isomorphism: $$1591\bmod 51=10\cdot 18-1\cdot17=163=10\bmod51.$$

$\endgroup$
3
  • 1
    $\begingroup$ In Patrick's voice uhhh could I get another hint....? $\endgroup$
    – Pstar007
    May 21 '16 at 13:12
  • 1
    $\begingroup$ @Pstar007: I've added some details. $\endgroup$
    – Bernard
    May 21 '16 at 13:35
  • $\begingroup$ Okay it was pretty clear that you have used the lemma to show that the gcd(3,17) = 1. Could you explain why you have used the alpha & beta part? That would help with the first and last line, everything else has been perfect Bernard. Cheers mate $\endgroup$
    – Pstar007
    May 21 '16 at 15:27
0
$\begingroup$

The fact that $51 = 3 \cdot 17$ (which are coprime) means that by the Chinese remainder theorem we can work separately mod 3 and mod 17, and then work backwards to find out what the answer is mod 51 at the end.

$1591 = 37 \cdot 43 \equiv 1 \cdot 1 = 1 \pmod 3$ and $1591 = 37 \cdot 43 \equiv 3 \cdot 9 = 27 \equiv 10 \pmod {17}$

We notice that 10 itself is $\equiv 10 \pmod {17}$ and $\equiv 1 \pmod 3$, so by the Chinese remainder theorem this is the only solution $\pmod {51}$.

Therefore $1591 \equiv 10 \pmod {51}$.

(We can be more formal about this - for example, we just guessed "10" as being the solution of $x \equiv 10 \pmod {17}$ and $x \equiv 1 \pmod 3$, which can be solved algorithmically.)

$\endgroup$
2
  • $\begingroup$ Thanks for the help Joshua. Could you please elaborate upon the part before you mentioned 10 being a solution. I can see why 10 is a solution since its congruent in mod 3 but getting to that point is confusing. Edit: I am referring to the second line you started after your initial statement if that clarifies things for you. $\endgroup$
    – Pstar007
    May 21 '16 at 13:30
  • $\begingroup$ Let me phrase it better: we know $1591 \equiv n \pmod {51}$ for some $n$, and we also know that $n \equiv 1 \pmod 3$ and $n \equiv 10 \pmod {17}$ (because $1591 \equiv \pmod 3$ and $1591 \equiv 10 \pmod {17}$, which is the content of the second paragraph). I observe that $n = 10$ works as a solution for this pair of equations. $\endgroup$
    – Josh Hunt
    May 21 '16 at 22:38

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.