# Solving a congruence equation.

• Dec 30th 2009, 10:46 AM
arun
Solving a congruence equation.
i have an equation say 22=(5x+8)mod26.how do i find x from this??please help me...
• Dec 30th 2009, 11:19 AM
tonio
Quote:

Originally Posted by arun
i have an equation say 22=(5x+8)mod26.how do i find x from this??please help me...

You can solve this since $\displaystyle 5$ is invertible $\displaystyle \pmod {26}$ . The following is done using arithmetic $\displaystyle \pmod {26}$ :

$\displaystyle 5x+8=22\Longrightarrow 5x=14\Longrightarrow x=\frac{14}{5}=14\cdot 21=294=8$

Tonio
• Dec 31st 2009, 05:22 AM
HallsofIvy
A slight variation on that: we want to solve 5x= 14 (mod 26). That is, 5x= 14+ 26y for some integer y. That is the same as the Diophantine equation 5x- 26y= 14. 5 divides into 26 5 times with remainder 1. That is, 26= 5(5)+ 1 so 5(-5)- 26(-1)= 1. Multiply that by 14: 5(-70)- 26(-14)= 14. That tells us that x= -70 is a solution. Since we want a number between 0 and 25 that is equivalent to -70, add 3(26)= 78: x= 78- 70= 8 (mod 26).