1
$\begingroup$

Is a simple way to solve the problem? The method I used is to list all numbers from equation (1) and then see which one give remainder $1$ when divided by $7$. This doesn't seems a very smart way.

Problem: Find smallest $x$ that satisfies $$x=59 \pmod {60} \tag 1$$ $$x=1 \pmod 7 \tag 2$$

$\endgroup$
  • 1
    $\begingroup$ Bother! There are dozens of past questions about this but I cannot find a clearcut duplicate! $\endgroup$ – almagest Jun 17 '16 at 20:18
  • $\begingroup$ I think what you are looking for is the Chinese remainder theorem. It can be used to solve a question like yours with multiple congruences. en.wikipedia.org/wiki/Chinese_remainder_theorem $\endgroup$ – Ziad Fakhoury Jun 17 '16 at 21:19
4
$\begingroup$

We can look at $59$, $59+60$, $59+120$, and so on until we bump into something congruent to $1$ modulo $7$. Doesn't take long!

For a more "general" approach, we want to find $k$ so that $59+60k\equiv 1\pmod{7}$. Reducing mod $7$ we find that we want $$4k\equiv -58\equiv -2\pmod{7}.$$

Multiply through by the inverse of $4$ modulo $7$, which is $2$. We get $k\equiv -4\equiv 3\pmod{7}$. So $59+(3)(60)$ is a solution.

$\endgroup$
  • $\begingroup$ You have a typographical error in your last line. You meant $59 + (3)(60)$ is a solution. $\endgroup$ – N. F. Taussig Jun 17 '16 at 21:02
  • $\begingroup$ @N.F.Taussig: Many thanks. $\endgroup$ – André Nicolas Jun 17 '16 at 21:21
2
$\begingroup$

Find $a,b$ such that $60a+7b=1$. Use the extended Euclidean algorithm if necessary.

Then $x = 1\cdot60a + 59\cdot7b$ is a solution. All solutions are congruent to this one mod $60\cdot 7$.

$\endgroup$
2
$\begingroup$

In this case you can use some heuristics. Solutions to (1) are of the form $59 + 60n$, $n \in \mathbb{Z}$, so all the positive ones end in $9$.

The first solution to (2) that ends in $9$ is $29$, and every tenth solution thereafter also ends in $9$ (the next one being $99$).

Pretty quickly you can arrive at $239$ as the smallest positive answer.

$\endgroup$
1
$\begingroup$

The the technique of "noodling around."

$7*8 = 56 \equiv -4(\mod 60)\\ 7*9 = 63 \equiv 3(\mod 60)\\ 1 + -2 \equiv 59(\mod 60)\\ 1 + 7*(9+9+8+8)\equiv 1 - 2 \equiv 59(\mod 60)\\ 239$

Now this is one solution. Since 7 and 60 are co-prime, $\text{lcm(7,60)} = 420$

$239+420k$

and 239 is the smallest positive solution.

$\endgroup$
  • $\begingroup$ You meant $7 \cdot 9 = 63 \equiv 3 \pmod{60}$. Also, you can obtain what I just wrote by writing 7 \cdot 9 = 63 \equiv 3 \pmod{60} when you are in math mode. $\endgroup$ – N. F. Taussig Jun 17 '16 at 21:09
  • $\begingroup$ Thanks for pointing out my error, I was a bit carried away copying from the line above. On the formatting, there is something I find comforting about the asterisk for multiplication. $\endgroup$ – Doug M Jun 17 '16 at 21:13

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.