# Thread: Solutions in a congruence class

1. ## Solutions in a congruence class

How do you find one and what is it exactly? For example, 2x is congruent to 3 (mod 5), what is a solution, what would it look like, how would you write it?

2. Originally Posted by Eagle3
How do you find one and what is it exactly? For example, 2x is congruent to 3 (mod 5), what is a solution, what would it look like, how would you write it?
When you write $2x\equiv 3(\bmod 5)$ you are asking to find all $x\in \mathbb{Z}$ so that $5$ divides $2x-3$.

Notice that $2x\equiv 3(\bmod 5)$ if and only if $2x\equiv 8(\bmod 5)$ if and only if $x\equiv 4(\bmod 5)$. That is it! We found the solution. When we write $x\equiv 4(\bmod 5)$ it means $x = 5k+4$ for some $k\in \mathbb{Z}$. Therefore, all solutions to $2x\equiv 3(\bmod 5)$ have the form $x=5k+4$.

3. Notice that $2x\equiv 3(\bmod 5)$ if and only if $2x\equiv 8(\bmod 5)$ if and only if $x\equiv 4(\bmod 5)$. That is it! We found the solution. When we write $x\equiv 4(\bmod 5)$ it means $x = 5k+4$ for some $k\in \mathbb{Z}$. Therefore, all solutions to $2x\equiv 3(\bmod 5)$ have the form $x=5k+4$.[/quote]

I guess my problem is that I do not see why 2x must equal 8.

4. Originally Posted by Eagle3
I guess my problem is that I do not see why 2x must equal 8.
If $a\equiv b(\bmod c)$ then $a\equiv b + c(\bmod c)$ and the other way around.

5. Notice that $2x\equiv 3(\bmod 5)$ if and only if $2x\equiv 8(\bmod 5)$ if and only if $x\equiv 4(\bmod 5)$. That is it! We found the solution. When we write $x\equiv 4(\bmod 5)$ it means $x = 5k+4$ for some $k\in \mathbb{Z}$. Therefore, all solutions to $2x\equiv 3(\bmod 5)$ have the form $x=5k+4$.[/quote]

So if I understand this correctly, in the case 6x is congruent to 10 (mod 15), then there is no solution since 6 never divides evenly into 10+15k, where k is an integer.

6. Originally Posted by Eagle3
So if I understand this correctly, in the case 6x is congruent to 10 (mod 15), then there is no solution since 6 never divides evenly into 10+15k, where k is an integer.
The congruence $6x\equiv 10(\bmod 15)$ never has a solution. So see this say there is such an $x$ then $15 | (6x - 10)$ which means $15k = 6x - 10$ for some $k\in \mathbb{Z}$. But then $15k - 6x = 10 \implies 3(5k - 2x) = 10$. This is a problem because $10$ has no factor of $3$.

Once you understood what I wrote above try generalizing the result. Let $a,n$ be positive integers and consider $ax \equiv b(\bmod n)$. Let $d=\gcd(a,n)$. Prove that if the congruence is solvable then $d$ divides $b$.