1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number theory find two smallest integers with same remainders

  1. Jun 11, 2012 #1
    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. jcsd
  3. Jun 11, 2012 #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
     
  4. Jun 18, 2012 #3
    Thanks!! I need to take a class on number theory!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Number theory find two smallest integers with same remainders
  1. Remainder of a number (Replies: 2)

  2. Finding remainder (Replies: 35)

Loading...