Solutions in a congruence class

**Eagle3** · January 31st 2009, 01:41 PM

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?

**ThePerfectHacker** · January 31st 2009, 02:15 PM

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$ .

**Eagle3** · January 31st 2009, 02:26 PM

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.

**ThePerfectHacker** · January 31st 2009, 02:40 PM

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.

**Eagle3** · January 31st 2009, 04:42 PM

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.

**ThePerfectHacker** · January 31st 2009, 04:51 PM

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$ .

Thread: Solutions in a congruence class

LinkBack

Thread Tools

Display

Solutions in a congruence class

Similar Math Help Forum Discussions

Rewording of a congruence class problem

Congruence/Residue Class

conjugacy class and class equation

find all solutions to the congruence

The determinant of the solutions of a linear congruence

Search Tags