# Homework Help: Congruences / modulo

1. Feb 7, 2010

### shizukusan

1. The problem statement, all variables and given/known data

Find, with proof, the smallest positive integer n that satisfy all the congruences.

n = 1 (mod 2)
n = 2 (mod 3)
n = 3 (mod 4)
n = 4 (mod 5)
n = 5 (mod 6)
n = 6 (mod 7)
n = 7 (mod 8)
n = 8 (mod 9)
n = 9 (mod 10)

2. Relevant equations

Let a,b,m within Z with m > 0. Then, a = b mod m is m|a-b.
(not sure if relevant or not)

3. The attempt at a solution

I tried to figure out what some of the ristriction on n
(ie - has to be odd since n = 1 (mod 2))
but didn't get too far.

2. Feb 7, 2010

### JSuarez

The first congruence tells you that n must be odd. If you try odd numbers, starting from 3, on the other congruences, what do you get?

3. Feb 7, 2010

### shizukusan

I sort of tried that approach using the other ristrictions but started to get into the 400s. (with only considering 3 of the 9 ristrictions).

plus, I need to provide a proof and this way is probably not going to work as a proof.

4. Feb 8, 2010

### JSuarez

400 is hardly a large number .

Look, if you want strictly positive integers, the smallest that satisfy the first congruence is 3. Now, the smallest that satisfies the first two is 5. Now, what is the smallest that satisfies the first three?

When you get to the last one, you will have the smallest that satisfies all; the steps are a valid proof.