1. ## Mods help

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

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

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

Hence$\displaystyle x = -5$ is a solution.

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

3. Originally Posted by Giraffro
$\displaystyle 173 = 5 \cdot 34 + 3$
$\displaystyle 34 = 11 \cdot 3 + 1$
$\displaystyle \Rightarrow 1 = 34 - 11 \cdot 3 = 34 - 11 \cdot (173 - 5 \cdot 34) = 56 \cdot 34 - 11 \cdot 173$
$\displaystyle \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$\displaystyle 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 $\displaystyle 3 \cdot 56 =168 \equiv -5 \pmod{173}$.