Number Theory: Inverse of 0 mod n? Chinese Remainder Theorem

[mattmns]

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!

 

[neurocomp2003]

might help if you posted the remaining equations...the CRT is suppose ot have a couple more congruent relations.

 

[mattmns]

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.

 

[AKG]

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.

 

[mattmns]

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!

 

[Hurkyl]

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?

It shouldn't affect anything: 0 is not a special case. You shouldn't need to invert it.