Explore BrainMass

# Congruence with Incongruent Solutions

Not what you're looking for? Search our solutions OR ask your own Custom question.

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

Let n be an integer greater than 2. For which values of n (if any) does the congruence 12x ≡ 8 (mod n) have exactly two incongruent solutions (mod n)? Justify your answer.

https://brainmass.com/math/linear-algebra/congruence-incongruent-solutions-534882

## SOLUTION This solution is FREE courtesy of BrainMass!

We need to consider the congruence classes of n modulo 12.

First, consider the cases in which n is coprime to 12, i.e., n ≡ 1, 5, 7, or 11 (mod 12). In these cases, 12 has a unique multiplicative inverse modulo n, call it k, whence 12x ≡ 8 (mod n) has the unique solution x ≡ 8k (mod n).

Next, consider the cases in which gcd (n, 12) = 2, i.e., n ≡ 2 or 10 (mod 12). Let m = n/2. Then m is coprime to 6, whence 6 has a unique multiplicative inverse modulo m, call it k. Now we have 6x ≡ 4 (mod m), whence x ≡ 4k (mod m), and hence x ≡ 4k or 4k + m (mod n), so here we have exactly two incongruent solutions modulo n.

Next, consider the cases in which gcd(n, 12) = 3, i.e., n ≡ 3 or 9 (mod 12). In these cases, n is coprime to 8, whence 12x ≡ 8 (mod n) has no solutions.

Next, consider the cases in which gcd(n, 12) = 4, i.e., n ≡ 4 or 8 (mod 12). Let m = n/4. Then m is coprime to 3, whence 3 has a unique multiplicative inverse modulo m, call it k. Now we have 3x ≡ 2 (mod m), whence x ≡ 2k (mod m), and hence x ≡ 8k, 8k + m, 8k + 2m, or 8k + 3m (mod n), so here we have exactly four incongruent solutions modulo n.

Next, consider the case in which gcd(n, 12) = 6, i.e., n ≡ 6 (mod 12). In this case, we have gcd(n, 8) = 2, whence 12x ≡ 8 (mod n) has no solutions.

Finally, we consider the case in which n ≡ 0 (mod 12). In this case, we have gcd(n, 8) = 4 or 8, whence 12x ≡ 8 (mod n) has no solutions.

Thus we see that the congruence 12x ≡ 8 (mod n) has exactly two incongruent solutions modulo n, if and only if, n ≡ 2 or 10 (mod 12).

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!