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: 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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Number Theory: Inverse of 0 mod n? Chinese Remainder Theorem
Loading...