6 divisors, 6 remainders, 1 answer

Some integers when divided by:

  • 2 gives a remainder of 1
  • 3 gives a remainder of 1
  • 5 gives a remainder of 2
  • 7 gives a remainder of 4
  • 11 gives a remainder of 3

What is the smallest positive integer that satisfies these conditions?


The answer is 487.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Relevant wiki: Chinese Remainder Theorem

Let the required integer be N N . We can find N N using the Chinese remainder theorem as follows:

N 1 (mod 2) N 2 k + 1 , where k Z 2 k + 1 1 (mod 3) 2 k 0 (mod 3) k = 0 N 2 × 3 m + 2 k + 1 6 m + 1 2 (mod 5) m 1 (mod 5) m = 1 N 6 × 5 n + 6 m + 1 30 n + 7 4 (mod 7) 2 n 4 (mod 7) n = 2 N 30 × 7 p + 30 n + 7 210 p + 67 3 (mod 11) p + 1 3 (mod 11) p 2 (mod 11) p = 2 \begin{aligned} N & \equiv 1 \text{ (mod 2)} & \small \color{#3D99F6} \implies N \equiv 2k+1 \text{, where }k \in \mathbb Z \\ \implies 2k+1 & \equiv 1 \text{ (mod 3)} \\ 2k & \equiv 0 \text{ (mod 3)} & \small \color{#3D99F6} \implies k = 0 \implies N \equiv 2\times 3 m + 2k + 1 \\ \implies 6m+1 & \equiv 2 \text{ (mod 5)} \\ m & \equiv 1 \text{ (mod 5)} & \small \color{#3D99F6} \implies m = 1 \implies N \equiv 6\times 5 n + 6m+1 \\ \implies 30n+7 & \equiv 4 \text{ (mod 7)} \\ 2n & \equiv 4 \text{ (mod 7)} & \small \color{#3D99F6} \implies n = 2 \implies N \equiv 30\times 7 p + 30n+7 \\ \implies 210p + 67 & \equiv 3 \text{ (mod 11)} \\ p + 1 & \equiv 3 \text{ (mod 11)} \\ p & \equiv 2 \text{ (mod 11)} & \small \color{#3D99F6} \implies p = 2 \end{aligned}

Therefore, N 210 × 2 + 67 = 487 N \equiv 210 \times 2 + 67 = \boxed{487}

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...