Take the 2-minute tour ×
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.

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

1 Answer 1

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