Find the smallest positive integer?

Question

Find the smallest positive integer which, when divided in turn by 21, 23, and 25, leaves respective remainders of 8,1, and 11.

Answer 1

5636

I'm sure there's a clever mathematical way to do it but I just wrote a quick Java program and found it by brute force...

public class FindNumber{
 public static void main(String [] args){
  int n = 0;
  boolean test = true;
  while(true){
   test = (n%21==8 && n%23==1 && n%25==11);
   if (test) break;
   ++n;
  }
  System.out.println("The value is " + n);
 }
}

Answer 2

5636 matching the brute force... unsurprisingly

Assuming AndyJ is not right (it sounds too much like a tricky way to ask a simple question to me otherwise). Not sure I did it the most elegant way but here how you can solve the congruence system (and hence tautologically the problem) in reasonable time .. and even without a computer!

You first show that up to a multiple of 23 the number is 461.

This is because 23 is a prime number so Z/23Z is a field which means all first order equation can be solved. For example the equation as 21*q+8=1 (23) and 25 s+11=1 (23) [also written 21q=-7 and 2 s=-10 up to multiples of 23]. You then solve these 2 equations: they have a solution because non zero elements have an inverse in a field.

You obtain that up to multiple of 23: s=18 and q=15 [at worse you inspect 2 lines of the multiplication table in Z/23Z].

To conclude look at the possibilities looking at 25*18+11+25*23*k and looking for k such that the remainder dividing by 21*23 is equal to 21*15+8. One finds k=9.
[so this steps adds 10 multiplications and 10 divisions]

5636=25*18+11+25*23*9
5636=21*15+8+21*23*11

Answer 3

The key phrase here is "in turn". It means successively dividing by 21, 23, and 25. Two others got the correct answer to a different problem. To put it mathematically, find the smallest positive integer N such that:

N = 21n + 8 (for some integer n)
n = 23m + 1 (for some integer m)
m = 25p + 11 (for some integer p)

Solving for N in terms of p yields:

N = 12075p + 5342

Choosing p=0 we get N = 5342.

Answer 4

N=8mod21,N=1mod23,N=11mod25. Solving these congruences gives you N=5636 as smallest.