Page 1 of 1

problem on congruences

Posted: Wed Dec 08, 2010 6:54 pm
by brain
How many different solutions, modulo 24, does the congruence 18x = 12(mod 24) have?

A None B One C Three D Six E Twelve

I get x = 2(mod 4) for the given congruence.

Re: problem on congruences

Posted: Wed Dec 08, 2010 11:16 pm
by prong
One way to approach this is by the Chinese Remainder Theorem.

By the CRT 18x = 12 mod 24 iff 18x = 12 mod 8 and 18x = 12 mod 3.

18x = 12 mod 3 is always true since 18 = 12 = 0 mod 3, so x can be 0, 1, or 2 mod 3. 18x = 12 mod 8 iff 2x = 4 mod 8. But this equation clearly has only the solutions x = 2, x = 6 mod 8.

So there are 3 * 2 = 6 possible solutions, for each distinct, independent choice mod 24 of x mod 3, x mod 8.

In fact It's easy now to write them down explicitly by iterating through all the pairs (x mod 3, x mod 8 ).

0 mod 3, 2 mod 8: 18 mod 24

0 mod 3, 6 mod 8: 6 mod 24

1 mod 3, 2 mod 8: 10 mod 24

1 mod 3, 6 mod 8: 22 mod 24

2 mod 3, 2 mod 8: 2 mod 24

2 mod 3, 6 mod 8: 14 mod 24

Re: problem on congruences

Posted: Mon Dec 13, 2010 2:53 pm
by enork
brain wrote:I get x = 2(mod 4) for the given congruence.
Once you've gotten to here, you're pretty much done. If x = 2(mod 4), then x has 6 possible values mod 24 (which is everything of the form 2 + 4n).

Another way to do the problem is that since the gcd of 18 and 24 is 6, every value of 18x (mod 24) will be a multiple of 6, of which there are 4 choices (and 12 is one of them). The residues will be evenly distributed among those 4 so that's 6 values of x for each one.

Re: problem on congruences

Posted: Mon Dec 13, 2010 8:39 pm
by brain
Thank you people! Number theory is just not my cup of tea.