# Homework Help: Number theory find two smallest integers with same remainders

1. Jun 11, 2012

### Wildcat

1. The problem statement, all variables and given/known data
Find the two smallest positive integers(different) having the remainders 2,3, and 2 when divided by 3,5, and 7 respectively.

2. Relevant equations

3. The attempt at a solution I got 23 and 128 as my answer. I tried using number theory where I started with 7x +2 as the number, then if divided by 5 the remainder would be 3 so subtract 3 from 7x+2 to get 7x-1 when I use this method and stop there by having x=0,1,2,3,... 3 works 7(3)-1 is divisible by 5 so put 3 in the original 7(3) +2 =23 Then I just used a trial and error method to find 128. Is my answer correct?? I know my procedure is sketchy because I have never been exposed to number theory.

2. Jun 11, 2012

### Fightfish

Your answers are correct. There are of course, more formal methods of solving it.
In number theory, we usually use the method of taking modulos. Let me illustrate this for the question below:

From the remainders, we have:
a == 2 (mod 3) - (1)
a == 3 (mod 5) - (2)
a == 2 (mod 7) - (3)

From (3), the numbers must have the form a = 7k+2, where k is any positive integer.

Using (1): 7k + 2 == 2 (mod 3)
This implies that 7k == 0 (mod 3), quite a useful result! Thus k = 3n, where n is any positive integer, and so our numbers a = 21n + 2.

Using (2): 21n + 2 == 3 (mod 5)
This implies that 21 n == 1 (mod 5). Since 21 == 1 (mod 5), n == 1 (mod 5) as well for the equation to hold.

Thus the numbers a that satisfy the conditions are of the form 21n + 2, n = 1,6,11,16,21...
The first two numbers are thus 21(1) + 2 = 23 and 21(6) + 2 = 128

3. Jun 18, 2012

### Wildcat

Thanks!! I need to take a class on number theory!