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 $\displaystyle 2x\equiv 3(\bmod 5)$ you are asking to find all $\displaystyle x\in \mathbb{Z}$ so that $\displaystyle 5$ divides $\displaystyle 2x-3$.

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

3. Notice that $\displaystyle 2x\equiv 3(\bmod 5)$ if and only if $\displaystyle 2x\equiv 8(\bmod 5)$ if and only if $\displaystyle x\equiv 4(\bmod 5)$. That is it! We found the solution. When we write $\displaystyle x\equiv 4(\bmod 5)$ it means $\displaystyle x = 5k+4$ for some $\displaystyle k\in \mathbb{Z}$. Therefore, all solutions to $\displaystyle 2x\equiv 3(\bmod 5)$ have the form $\displaystyle 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 $\displaystyle a\equiv b(\bmod c)$ then $\displaystyle a\equiv b + c(\bmod c)$ and the other way around.

5. Notice that $\displaystyle 2x\equiv 3(\bmod 5)$ if and only if $\displaystyle 2x\equiv 8(\bmod 5)$ if and only if $\displaystyle x\equiv 4(\bmod 5)$. That is it! We found the solution. When we write $\displaystyle x\equiv 4(\bmod 5)$ it means $\displaystyle x = 5k+4$ for some $\displaystyle k\in \mathbb{Z}$. Therefore, all solutions to $\displaystyle 2x\equiv 3(\bmod 5)$ have the form $\displaystyle 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 $\displaystyle 6x\equiv 10(\bmod 15)$ never has a solution. So see this say there is such an $\displaystyle x$ then $\displaystyle 15 | (6x - 10)$ which means $\displaystyle 15k = 6x - 10$ for some $\displaystyle k\in \mathbb{Z}$. But then $\displaystyle 15k - 6x = 10 \implies 3(5k - 2x) = 10$. This is a problem because $\displaystyle 10$ has no factor of $\displaystyle 3$.

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