Congruency to two distinct primes implies congruency to their product?

[ksdhart2]

Hi all. I'm having a bit of difficulty with a modular arithmetic proof problem. I think I know the answer, but it feels so simple so I want to solicit some opinions on if my proof is fine, or if I need to justify it more (and if so, how can I do so?). The full problem text is:

Let \(p_1\) and \(p_2\) be any two distinct primes, and let \(a\) and \(b\) be any two (not necessarily distinct) integers. Prove \(\displaystyle \left[ a \equiv b \: \: (mod \: p_1) \wedge a \equiv b \: \: (mod \: p_2) \right] \iff a \equiv b \: \: (mod \: p_1 \: p_2)\)

Going one way is easy enough. I started by assuming that \(\displaystyle a \equiv b \: \: (mod \: p_1 \: p_2)\). Then:

• \(\displaystyle a - b = p_1 \: p_2 \: k_3 \text{ where } k_3 \in \mathbb{Z}\).
• Let \(\displaystyle k_1 = p_2 \: k_3\) and \(\displaystyle k_2 = p_1 \: k_3\)
• \(\displaystyle a - b = p_1 \: k_1 \text{ where } k_1 \in \mathbb{Z}\)
• \(\displaystyle a - b = p_2 \: k_2 \text{ where } k_2 \in \mathbb{Z}\)
• \(\displaystyle a \equiv b \: \: (mod \: p_1) \wedge a \equiv b \: \: (mod \: p_2)\)

Going the other way seemed a bit harder, and so this is the part I'm less sure about. I started this part by assuming that \(\displaystyle a \equiv b \: \: (mod \: p_1) \wedge a \equiv b \: \: (mod \: p_2)\). Then:

• \(\displaystyle a - b = p_1 \: k_1 \text{ where } k_1 \in \mathbb{Z}\)
• \(\displaystyle a - b = p_2 \: k_2 \text{ where } k_2 \in \mathbb{Z}\)
• \(\displaystyle a - b = LCM(p_1, \: p_2) \: k_3 \text{ where } k_3 \in \mathbb{Z}\)
• Since \(p_1\) and \(p_2\) are both prime and therefore coprime to each other, \(\displaystyle LCM(p_1, \: p_2) = p_1 \: p_2\)
• \(\displaystyle a - b = p_1 \: p_2 \: k_3 \text{ where } k_3 \in \mathbb{Z}\)
• \(\displaystyle a \equiv b \: \: (mod \: p_1 \: p_2)\)

Is it okay to just say that since \(a - b\) is a multiple of \(p_1\) and a multiple of \(p_2\), it must be a multiple of their LCM? Isn't that exactly what I'm trying to prove? So that would make it a big no-no? Or maybe it really is okay and I'm just overthinking it...

Any help would be appreciated. Thanks!

 

[Steven G]

If two distinct primes go into a-b, doesn't that mean that the product of the two primes go into a-b. The only way that r| x and s|x but rs does not divide x is if r and s have common factors. Do you see this? Consider 6|18 and 9| 18, so why is 6*9 not dividing 18?

So yes your proof looks good.

 

[ksdhart2]

I think I just had a major shift in the way I think about things. I became so obsessed with writing equations and formulas and "proving" stuff that I forgot to think about what these equations/formulas/statements actually mean. Before, I used to always be confused when people would present valid proofs, but with concerns along the lines of "But, that's it? I didn't do anything! I didn't say anything meaningful!" But now I get it, because that's exactly where I was.

Of course it must be true that \(\displaystyle a - b = LCM(p_1, \: p_2) \: k_3\). That's literally the definition of Least Common Multiple. Any number that's a multiple of both two other numbers is either the LCM itself or some multiple thereof. And that's equivalent to saying the number divides the LCM.

Thanks a lot. It really helped

 

[Steven G]

I think I just had a major shift in the way I think about things.

Did my comment have anything to do with that. If yes, that is so cool!

And yes, THINK. I may not be the best at math or the best thinker but I always try to think about things until I have the best understanding that I can achieve. This is why, as I said in the past, I wish that I could have taken all my exams while in college a year after the course ended as I would have done better.

 

[ksdhart2]

Did my comment have anything to do with that. If yes, that is so cool!

In part, yes. But it's also probably the culmination of a general shift away from strict numerical and "equational" thinking towards a more flexible understanding of math. This also explains why I struggled so much with abstract algebra and other upper division math courses, because they shifted from formulas and numbers towards ideas.

This is why, as I said in the past, I wish that I could have taken all my exams while in college a year after the course ended as I would have done better.

I absolutely agree with this! In addition to my on-going shift towards idea-based thinking, I feel like I've been able to "digest" the idea I learned in abstract algebra and ring theory more. I feel like I have a much better grasp of the ideas now than I ever did during the course, and I've barely done any further studying on the topic - just let it "settle" in my brain some.

 

[Steven G]

I have been looking into the beauty of infinity and can across a video that (at the end) I think nails down the question you asked (as long as you view the video thinking about your question) .
I was able to answer the 1st 2 situations but I thought about the 3rd case for a good 20 minutes without getting anywhere. I then continued the video and as soon as I heard the phrase prime numbers I had the solution and thought about this thread.
The video is just excellent and you will enjoy it!