Results 1 to 2 of 2

Math Help - Smallest positive integer

  1. #1
    Member
    Joined
    Sep 2006
    Posts
    75

    Smallest positive integer

    What is the smallest positive integer that when divide by 10, 9, 8, 7, and 6 leaves the reaminders 9, 8, 7, 6 , and 5, respectively?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by ceasar_19134 View Post
    What is the smallest positive integer that when divide by 10, 9, 8, 7, and 6 leaves the reaminders 9, 8, 7, 6 , and 5, respectively?
    I hope you are familiar with congruences and the chinese remainder theorem.
    ---
    The general theorem used here if,
    x=a(mod pq) where gcd(p,q)=1
    It is equivalent to (Euclid's Lemma),
    x=a(mod p) and x=a(mod q)
    Thus, by the terms of the problem,
    x=9(mod 10)
    x=8(mod 9)
    x=7(mod 8)
    x=6(mod 7)
    x=5(mod 6)
    Equivalently,
    x+1=0(mod 2*5)
    x+1=0(mod 3^2)
    x+1=0(mod 2^2)
    x+1=0(mod 7)
    x+1=0(mod 2*3)
    Equivalently,
    x+1=0(mod 2) (1)
    x+1=0(mod 5) (2)
    x+1=0(mod 3^2) (3)
    x+1=0(mod 2^2) (4)
    x+1=0(mod 7) (5)
    x+1=0(mod 2) (6)
    x+1=0(mod 3) (7)
    Equations:
    (4) implies (1) and (6)
    (3) implies (7)
    Thus, eliminating those,
    x+1=0(mod 5)
    x+1=0(mod 9)
    x+1=0(mod 7)
    x+1=0(mod 8)
    Equivalently,
    x=-1 (mod 5)
    x=-1 (mod 9)
    x=-1 (mod 7)
    x=-1 (mod 8)
    And, gcd between any two is one.
    Thus you can rely on Chinese Remainder Theorem
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Smallest Positive integer n
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 17th 2011, 07:15 AM
  2. Replies: 5
    Last Post: October 15th 2010, 11:08 PM
  3. Determine the smallest positive integer n
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: October 1st 2010, 07:24 AM
  4. Raise integer to positive integer power
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 21st 2009, 12:20 PM
  5. Smallest Integer
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: January 18th 2007, 05:59 PM

Search Tags


/mathhelpforum @mathhelpforum