problem on congruences

Forum for the GRE subject test in mathematics.
Post Reply
brain
Posts: 28
Joined: Tue Aug 25, 2009 12:16 pm

problem on congruences

Post by brain » Wed Dec 08, 2010 6:54 pm

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.

prong
Posts: 24
Joined: Thu Sep 24, 2009 12:17 am

Re: problem on congruences

Post by prong » Wed Dec 08, 2010 11:16 pm

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

enork
Posts: 33
Joined: Fri Sep 18, 2009 3:16 am

Re: problem on congruences

Post by enork » Mon Dec 13, 2010 2:53 pm

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.

brain
Posts: 28
Joined: Tue Aug 25, 2009 12:16 pm

Re: problem on congruences

Post by brain » Mon Dec 13, 2010 8:39 pm

Thank you people! Number theory is just not my cup of tea.



Post Reply