0
$\begingroup$

Origin - p5 - Example 5

I'm querying a possible error, thence I show the pdf as is. Is the 3 underlined in red supposed to be 2? scilicet, the last line should be $n = 2 \times 5 \times 7 $? Notation hails from here.

enter image description here

$\endgroup$
3
  • $\begingroup$ Solution is $x\equiv 23 \pmod{70}$, so I'd say you're right. $\endgroup$ May 6 '14 at 11:54
  • $\begingroup$ @DanielFischer thanks. my answer still doesn't match. i showed more work. $\endgroup$ May 6 '14 at 14:02
  • $\begingroup$ $3\cdot 14\cdot 4 + 1\cdot 35\cdot 1 + 2\cdot 10 \cdot 5 = 168 + 35 + 100 = 303 = 4\cdot 70 + 23$, that last seems to be an arithmetical mistake. $\endgroup$ May 6 '14 at 14:06
2
$\begingroup$

The error is in your last line. The addition is wrong

$$3\cdot14\cdot4+1\cdot35\cdot1+2\cdot10\cdot5=168+35+100=\color{red}{303}=23\pmod{70}$$

Some ideas:

$$\begin{align*}2x=1\pmod5&\iff x=2^{-1}\pmod5&\iff& x=3\pmod 5\\{}\\ 3x=9\pmod 6&\iff x=3\pmod 2&\iff&x=1\pmod 2\\{}\\ 4x=1\pmod7&\iff x=4^{-1}\pmod7&\iff&x=2\pmod7\end{align*}$$

Observe that equations (1)-(2) above already show the number must end in $\;3\;$, and together with equation (3) we get the solution $\;23\;$ (modulo $\;5\cdot2\cdot7=70\;$, of course)

If you want to apply the CRT (in fact, one of its proofs), then as follows is one way:

$$\begin{align*}14^{-1}\pmod 5&=4\\{}\\ 35^{-1}\pmod2&=1\\{}\\ 10^{-1}\pmod7&=5\end{align*}$$

Thus, a solution modulo $\;7\cdot2\cdot5=70\;$ is

$$3\cdot14\cdot4+1\cdot35\cdot1+2\cdot10\cdot5=168+35+100=303=23\pmod{70}$$

$\endgroup$
1
  • $\begingroup$ Can you please just write in your answer that the error was in my last line? I foozled the addition in the last line. thanks for another solution though. $\endgroup$ May 9 '14 at 14:52

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.