Question

So here's the other problem I promised you.

Answer 1

setting up

Answer 2

How many positive integers less than or equal to \[6\cdot7\cdot8\cdot9 \] solve the system of congruences
\[m \equiv 5 \pmod{6} \]
\[m \equiv 4 \pmod{7} \]
\[m \equiv 3 \pmod{8} \]
\[m \equiv 3 \pmod{9}\]

Answer 3

oops. the question is supposed to ask

How many positive integers less than or equal to 6⋅7⋅8⋅9 solve the system of congruences?

Answer 4

This question feels to be a slightly different flavour than the previous one... it looks more like a counting problem to me. At first glance, there are 7*8*9 numbers which satisfy the first, 6*8*9 that satisfy the second, 6*7*9 which satisfy the third and 6*7*8 which satisfy the last.

I guess the number theory bit comes in determining which numbers we've counted more than once...

Answer 5

i see what you mean. so we have to find a way to count all the numbers we over counted or something along the lines of eliminating that factor... i don't see how we can use complementary counting but i also don't see any other ways...

Answer 6

sorry for leaving you. XD

Answer 7

Neither do I. The first pair of equations will give you something like m is congruent to something mod (6*7). And there will be 8*9 of those.
But the first and third equation aren't se easily dealt with, since 6 and 8 are not coprime...

Answer 8

hmmm...i guess I'll save this one for later (maybe in the morning where I'm not so tired i can barely keep my eyes open lol)

Answer 9

thanks for sticking with me though! I still have a couple more questions that might be a bit easier...

Answer 10

Let's have a go at them then! ;)

Answer 11

Sorry this is such a late reply, but the problem looked interesting and I couldn't help myself.

Hopefully, you've learned by now that if \(m,n\) are coprime, then the system of equations\[x\equiv a\pmod{m}\]\[x\equiv b\pmod{n}\]has a unique solution in \(1\le x\le m\cdot n\). The other solutions (not in the interval) are obtained by adding multiples of \(m\cdot n\). In the case where \(m,n\) are not coprime, you get more solutions. But once you find one, it's easy to find the others. You just add multiples of the least common multiple of \(m,n\). So the total number of solutions would be\[\frac{m\cdot n}{\text{lcm}(m,n)}\]

Applying this is this problem, we get that the lcm of \(6,7,8,9\) is 504, and their product is 3024. So there should be \[\frac{3024}{504}=6\] solutions in the given interval.

Answer 12

Wow. Another very well said solution. I applaud you. I'll never be as smart as some of you people but I can try :)

Answer 13

To be fair, I did brush over some of the details (such as showing that this still works for more than 2 moduli).

Answer 14

Very nice!

@orple This bit of KingGeorge's reply: "Hopefully, you've learned by now that if m,n are coprime, then the system of equations
\[x≡a \pmod m, \\
x≡b \pmod n\] has a unique solution in \(1≤x≤m⋅n\). The other solutions (not in the interval) are obtained by adding multiples of \(m⋅n\)"
is the Chinese remainder theorem. I guess it's one of those things we tend to use intuitively.

I did say in one of your later questions that my brain somehow interpreted this question completely incorrectly to mean: How many numbers are there which satisfy one of the equations...