Number theory find two smallest integers with same remainders

In summary, the conversation discussed finding the two smallest positive integers with remainders of 2,3, and 2 when divided by 3,5, and 7 respectively. The solution involved using number theory and the method of taking modulos to determine that the numbers are of the form 21n+2, with n being a positive integer. The first two numbers that satisfy the conditions are 23 and 128.
  • #1
Wildcat
116
0

Homework Statement


Find the two smallest positive integers(different) having the remainders 2,3, and 2 when divided by 3,5, and 7 respectively.


Homework Equations





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.
 
Physics news on Phys.org
  • #2
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
Fightfish said:
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

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

FAQ: Number theory find two smallest integers with same remainders

1. What is number theory?

Number theory is a branch of mathematics that deals with the properties and relationships of numbers, particularly integers.

2. What are remainders in number theory?

In number theory, remainders refer to the value left over after dividing one integer by another. For example, when dividing 11 by 3, the remainder would be 2.

3. How do you find two smallest integers with the same remainders?

To find two smallest integers with the same remainders, you can use the Chinese Remainder Theorem. This theorem states that if you have a set of congruences (expressions that are equal to the same value modulo a given integer), you can find a unique solution that satisfies all of them.

4. What is the significance of finding two smallest integers with the same remainders?

Finding two smallest integers with the same remainders has various applications in cryptography, coding theory, and computer science. It can also be used to solve problems related to modular arithmetic and polynomial congruences.

5. Are there any other methods for finding two smallest integers with the same remainders?

Yes, there are other methods for finding two smallest integers with the same remainders, such as the Euclidean algorithm and the Chinese remainder theorem. These methods involve using number theory concepts and algorithms to solve congruence equations.

Similar threads

Back
Top