# Congruency

• Mar 5th 2009, 07:27 PM
Bagoro
Congruency
I'm having trouble solving this problem.

Solve the congruence 2x is equivalent to 7 (mod 17)

Can someone work it out for me in step by step form with some explinations
• Mar 5th 2009, 07:43 PM
o_O
Add the modulus to $\displaystyle 7$ :

$\displaystyle \begin{array}{rcll} 2x & \equiv & 7 & \left(\text{mod } 17\right) \\ 2x & \equiv & 7 {\color{red}\ + \ 17} & \left(\text{mod } 17\right) \\ 2x & \equiv & 24 & \left(\text{mod } 17\right) \\ 2x & \equiv & 2 \cdot 12 & \left(\text{mod } 17\right) \end{array}$

Since $\displaystyle \gcd (2,17) = 1$, we can cancel both sides by 2 without worrying about the modulus.
• Mar 7th 2009, 11:29 AM
siegfried
Quote:

Originally Posted by o_O
$\displaystyle \begin{array}{rcll}2x & \equiv & 24 & \left(\text{mod } 17\right) \\ 2x & \equiv & 2 \cdot 17 & \left(\text{mod } 17\right) \end{array}$

how does this follow
• Mar 7th 2009, 11:51 AM
o_O
Sorry that was a typo. Fixed it now.
• Mar 7th 2009, 01:14 PM
john_n82
Congruence ax = b (mod c) for some a, b, c in Z can be written as a linear diophantine equation ax - cy = b. And that is easy to solve using the box method.

For this problem, 2x = 7 (mod 17) can be written as 2x - 17y = 7.
Using the box method, we found the Bezout relation: -56.2 + 7.17 = 7
Therefore, x = -56 = 12 (mod 17).