Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
2  
This is an application of the Chinese Remainder Theorem; most proofs of this theorem are constructive and provide a simple algorithm. – Johannes Kloos Apr 16 '12 at 11:19
1  
en.wikipedia.org/wiki/… – pedja Apr 16 '12 at 11:26
up vote 2 down vote accepted

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.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.