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.
problem on congruences
Re: problem on congruences
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
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
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).brain wrote:I get x = 2(mod 4) for the given congruence.
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
Thank you people! Number theory is just not my cup of tea.