0
$\begingroup$

Given functions of the form:

$n \bmod a = b$

In general, What is the easiest way to calculate the minimum positive $n$?

For example:

$n \bmod 2 = 1$

$n \bmod 3 = 2$

$n \bmod 5 = 2$

The calculated n should equal $17$.

  • 1
    http://en.wikipedia.org/wiki/Chinese_remainder_theorem#Finding_the_solution_with_basic_algebra_and_modular_arithmetic2012-04-16

1 Answers 1

2

In general one can employ the Chinese Remainder Theorem or Easy CRT. However, as is often true for small cases, this system of congruences admits a constant case optimization: here since $\rm\:n\equiv 2\:$ both mod $3$ and $5,\!\:$ we deduce $\rm\:n\equiv 2\pmod{15},\:$ so $\rm\:n\equiv 2\:$ or $\rm\:\!17\pmod{30},\:$ necessarily the latter, since $\rm\:n\:$ is odd by the first congruence.