- #1

- 1,085

- 6

- Thread starter mattmns
- Start date

- #1

- 1,085

- 6

- #2

- 1,356

- 2

- #3

- 1,085

- 6

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.

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:

- #4

AKG

Science Advisor

Homework Helper

- 2,565

- 4

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.

- #5

- 1,085

- 6

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!

[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:

- #6

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

It shouldn't affect anything: 0 is not a special case. You shouldn't need to invert it.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?

- Last Post

- Replies
- 1

- Views
- 1K

- Last Post

- Replies
- 24

- Views
- 2K

- Last Post

- Replies
- 1

- Views
- 3K

- Last Post

- Replies
- 1

- Views
- 2K

- Last Post

- Replies
- 9

- Views
- 3K

- Last Post

- Replies
- 1

- Views
- 619

- Last Post

- Replies
- 0

- Views
- 1K

- Replies
- 2

- Views
- 552

- Replies
- 0

- Views
- 2K

- Replies
- 1

- Views
- 2K