[deprosun]

• x = 3 (mod 9), x = 7 (mod 11), x = 9 (mod 15)
  
• x ≡ 7 (mod 9), x = 4 (mod 11), x = 13 (mod 15)
  
• x ≡ 2 (mod 9), x = 0 (mod 11), x = 8 (mod 15)
  
• x ≡ 4 (mod 9), x = 10 (mod 11), x = 10 (mod 15)

I am to see if any of these have a solution.
I was going to use Chinese Remainder Theorem, however the moduli aren't
pairwise relatively prime. I am not sure how else to check if it has a solution..

So now, For example, in 1:
9 divides x-3, 11 divides x-7, and 15 divides x-9

Does this mean I have to get a common x such that all three equations above satisfy?

[macosxnerd101]

If two moduli are not coprime, you have to find their GCD and factor each congruence into two congruences. The remainder doesn't change (though it may be reduced). Check out my tutorial on the Chinese Remainder Theorem for some examples.

[deprosun]

So if two systems dont have a solution, there will be no solution for any number more than 2 systems? Also in your example, what does contradictory mean?
x = 0 (mod 3) and x = 7 (mod 27)
How are these contradictory?

Also, In my problem 1: x = 3 (mod 9) and x = 9 (mod 15), 9 = 3 x 3 and 15 = 3 x 5. Common factor = 3. More, 9 has 3² and 15 has 3¹ as highest power of 3. So will I write:

x = 3 (mod 1)?? because there are no other factors of 9.
x = 9 (mod 5)?

This post has been edited by deprosun: 09 October 2013 - 05:17 PM

[macosxnerd101]

Consider x = 7 (mod 27). Take that and plug 7 = 0 (mod 3). Is that correct? Remember that since 3 and 27 are not coprime (27 = 3³), these congruences must agree.

For your first problem:

Quote

x = 3 (mod 9), x = 7 (mod 11), x = 9 (mod 15)

I would say factor:
x = 3 (mod 9) to x = 0 (mod 3) (factoring 9 into 3 * 3 produces two identical congruences, so we just use one of them).

Then factor:
x = 9 (mod 15) to:
x = 0 (mod 3)
x = 4 (mod 5)

Again, you already have x = 0 (mod 3) though, so just keep one of them.

It should be fairly straight-forward from here.

[deprosun]

macosxnerd101, on 09 October 2013 - 07:34 PM, said:

Consider x = 7 (mod 27). Take that and plug 7 = 0 (mod 3). Is that correct? Remember that since 3 and 27 are not coprime (27 = 3³), these congruences must agree.

.. And therefore there is no solution? 3 and 27 are not coprime, therefore these congruences must agree and there is no solution?

This post has been edited by deprosun: 10 October 2013 - 06:48 AM

[macosxnerd101]

How could there be a solution?

[deprosun]

3 doesn't divide 7-0. So 7 = 0 (mod 3) isn't true.
I think I don't understand, when you say to plug 7 = 0 (mod 3)..


Sorry for a such a hiatus!

[macosxnerd101]

Quote

I think I don't understand, when you say to plug 7 = 0 (mod 3)..

Your argument was correct. That's what I meant by plugging 7 = 0 (mod 3). It was to test if the congruence was valid.

When you ask if something is correct, you should have a proof or some sort of argument to go along with it. You're in a lot of theoretical CS type classes, so rigorous argument and critical thinking is important. Try and work on that as you ask questions here. It will help you in class as well.

[deprosun]

Thank you!
I will provide more reasoning to see my answer to a question is valid.
My professor never had us practice on such question. He only had us learn on Chinese remainder theorem method.
However, by looking at your method if I had looked more into the problem, I should have been able to
figure out.
Also, sometimes I feel these theoretical classes are very language dependent. I have had professors where
they teach the material using their book or terms that aren't well known out in the internet. So this restricts me a little to research
questions using their ideas.

Btw: I am only 9617 reps away from you. Watch out!!

This post has been edited by deprosun: 12 October 2013 - 02:06 PM

[macosxnerd101]

Quote

Also, sometimes I feel these theoretical classes are very language dependent. I have had professors where
they teach the material using their book or terms that aren't well known out in the internet. So this restricts me a little to research

Sometimes they are. If you're in a given class though, you should at least be able to poke around a bit, or use the language you've been taught to really articulate your ideas. If you're using non-standard language, we can always ask you what you mean and help you fill in the gaps with standard language. The idea is to learn how to think, though.

[deprosun]

I completely agree.
And that's what everyone needs, learn how to think.