Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Congruences / modulo

  1. Feb 7, 2010 #1
    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. jcsd
  3. Feb 7, 2010 #2
    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?
  4. Feb 7, 2010 #3
    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.
  5. Feb 8, 2010 #4
    400 is hardly a large number :smile:.

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook