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: Number Theory: Inverse of 0 mod n? Chinese Remainder Theorem

  1. Feb 22, 2007 #1
    I am doing a Chinese remainder theorem question and one of the equations is [itex]x \equiv 0[/itex] (mod 7). This would mean that x is a multiple of 7, but how do I use it in conjunction with the Chinese remainder theorem? Do I just ignore that equation, use the CRT on the rest of the system, and then once I get an answer, make sure it is also a multiple of 7? (this is my guess, but I am not 100% sure). Thanks!
     
  2. jcsd
  3. Feb 22, 2007 #2
    might help if you posted the remaining equations...the CRT is suppose ot have a couple more congruent relations.
     
  4. Feb 22, 2007 #3
    Sure.

    Here is the system:

    [tex]
    \begin{align*}
    & x \equiv 1 \ \text{(mod 2)} \\
    & x \equiv 2 \ \text{(mod 3)} \\
    & x \equiv 4 \ \text{(mod 5)} \\
    & x \equiv 0 \ \text{(mod 7)}
    \end{align*}[/tex]


    edit... In fact, here is the original question, if that may be of help too:

    --------
    There are n eggs in a basket. If eggs are removed from the basket 2,3,4,5, and 6 at a time, there remain 1,2,3,4, and 5 eggs in the basket respectively. If eggs are removed from the basket 7 at a time, no eggs remain in the basket. What is the smallest possible number of eggs the basket could have contained?
    ---------

    I got to the system I have above by breaking down the mod 4 and mod 6 equations into their primes, and deleting the duplicates.
     
    Last edited: Feb 22, 2007
  5. Feb 23, 2007 #4

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    How exactly did you decide to eliminate the mod 4 and mod 6 equations? The mod 4 equation implies the mod 2 equation, and the mod 6 equation implies the mod 3 equation, so you can eliminate the mod 2 and mod 3 equation. The problem starts off telling you that x = n (mod n+1) for n = 1, 2, 3, 4, 5. This is equivalent to saying that x = n (mod n+1) for n = 3, 4, 5 [i.e. you can get rid of the mod 2 and mod 3 equations, like I've already said]. But this isn't equivalent to x = n (mod n+1) for n = 1, 2, 4. For example, x=29 satisfies these three equations, but doesn't satisfy the original equations you were given.

    Now it turns out that when you include the equation x = 0 (mod 7), THEN

    x = n (mod n+1) for n = 1, 2, 3, 4, 5; x = 0 (mod 7)

    x = n (mod n+1) for n = 3, 4, 5; x = 0 (mod 7)

    x = n (mod n+1) for n = 1, 2, 4; x = 0 (mod 7)

    become equivalent. Did you take the mod 7 equation into account when coming up with your system, or was it just luck?

    Anyways, the CRT doesn't tell you how to find x (the proof does), it just tells you x exists and is unique (modulo something) if the system satisfies certain conditions. Don't worry about the CRT, just think of how you might find a number which satisfies

    x = n (mod n+1) for n = 3, 4, 5; x = 0 (mod 7)

    or, if you have a good reason for why

    x = n (mod n+1) for n = 1, 2, 4; x = 0 (mod 7)

    is equivalent to

    x = n (mod n+1) for n = 1, 2, 3, 4, 5; x = 0 (mod 7)

    then think about how you'd find a number satisfying:

    x = n (mod n+1) for n = 1, 2, 4; x = 0 (mod 7)

    It's a lot easier, actually, when you think of the congruence x = n (mod n+1) to be x = -1 (mod n+1). First, find a number x' satisfying the congruences other than x = 0 (mod 7). If this number itself is not a multiple of 7, you need to keep adding multiples of a certain number N to x' until you have x' + kN is a multiple of 7. That sounds a little vague, hope it was clear enough though.
     
  6. Feb 23, 2007 #5
    What I did with the mod 4 and mod 6 equations was incorrect. I had not realized it until I re-read one of the propositions:
    [tex](x,y)=1, a \equiv b \ \text{(mod x) and} \ a \equiv b \ \text{(mod y)} \Leftrightarrow a \equiv b \ \text{(mod xy)}[/tex]

    (well the mod 6 was OK since (2,3) = 1, but the mod 4 was not OK since (2,2) = 1).

    Thanks for the clarity!
     
    Last edited: Feb 23, 2007
  7. Feb 23, 2007 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    It shouldn't affect anything: 0 is not a special case. You shouldn't need to invert it.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook