1

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

Watson
  • 23,793
learning
  • 1,749
  • 1
    Bother! There are dozens of past questions about this but I cannot find a clearcut duplicate! – almagest Jun 17 '16 at 20:18
  • 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. https://en.wikipedia.org/wiki/Chinese_remainder_theorem – Ziad Fakhoury Jun 17 '16 at 21:19

4 Answers4

4

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.

André Nicolas
  • 507,029
2

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

lhf
  • 216,483
2

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.

John
  • 26,319
1

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.

Doug M
  • 57,877
  • 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. – N. F. Taussig Jun 17 '16 at 21:09
  • 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. – Doug M Jun 17 '16 at 21:13