# Thread: Mods help

1. ## Mods help

Hey guys, jsut wondering how to figure out this question: Find an integer $z$ so that $34z \equiv 3$ mod 173.

2. Suppose you have $z \in \mathbb{Z}$ such that $34 z \equiv 3 \pmod{173}$. Then $\exists n \in \mathbb{Z}$ such that $34z - 3 = 173n$, so $34z + 173n = 3$. Now apply the extended Euclidean algorithm to $34$ and $173$:

$173 = 5 \cdot 34 + 3$
$34 = 11 \cdot 3 + 1$
$\Rightarrow 1 = 34 - 11 \cdot 3 = 34 - 11 \cdot (173 - 5 \cdot 34) = 56 \cdot 34 - 11 \cdot 173$
$\Rightarrow 3 = (3 \cdot 56) \cdot 34 - 33 \cdot 173 \equiv -5 \cdot 34 \pmod{173}$.

Hence $x = -5$ is a solution.

This method holds more generally. If $a, b \in \mathbb{Z}, n \in \mathbb{N}^+$, then $\exists x \in \mathbb{Z}$ such that $ax \equiv b \pmod{n}$ if and only if $\text{hcf}(a,n) \mid b$. If this is the case, then the same method works.

3. Originally Posted by Giraffro
$173 = 5 \cdot 34 + 3$
$34 = 11 \cdot 3 + 1$
$\Rightarrow 1 = 34 - 11 \cdot 3 = 34 - 11 \cdot (173 - 5 \cdot 34) = 56 \cdot 34 - 11 \cdot 173$
$\Rightarrow 3 = (3 \cdot 56) \cdot 34 - 33 \cdot 173 \equiv -5 \cdot 34 \pmod{173}$. <---- I DONT KNOW HOW YOU GOT THIS LINE....

Hence $x = -5$ is a solution.
Hey my writting in blue explains what my problem is.. I understand how you got the line 1 = ...... but dont know how you got the 3 = .....

4. Anyone can explain? thank you

5. Originally Posted by jvignacio
Hey my writting in blue explains what my problem is.. I understand how you got the line 1 = ...... but dont know how you got the 3 = .....
Just multiply the '1=...' line by 3 to get the '3=...' line and $3 \cdot 56 =168 \equiv -5 \pmod{173}$.