# Solving the congruence $3x \equiv 17 \pmod{29}$ [duplicate]

The given linear congruence is to be solved:

$$\gcd:(3;29)=1 |17$$ $$3x+29y=1 \iff 3x \equiv 1 \pmod{29} \iff y \equiv 3^{-1} \pmod{29}$$

With the extended Euclidean algorithm one obtains: \begin{align*} 29 & = 3 \cdot 9+2\\ 3 & = 2 \cdot 1+1\\ 2 & = 2 \cdot 1 \end{align*}

By means of backward resolution: \begin{align*} 1 & = 3-2 \cdot 1\\ & = -29+10 \cdot 3\\ & = -29+10(3-29)\\ & = 10 \cdot 3-1 \cdot 29 \end{align*}

$$-1 \equiv 3^{-1} \pmod{29}$$

$$\implies 3x \equiv 17 \pmod{27} \iff x \equiv -1 \cdot 3x \pmod{29} \equiv -1 \cdot 17 \pmod{29}$$

Are my considerations correct so far and how do I arrive at the solution $$x$$?

• This is hard to follow. What does "$gcd:(3;29)=1|17$" mean? And $29$ is not equal to either $3\times9 +23$ nor $2\times 1$. In any case, isn't the inverse of $3\pmod {29}$ obviously $10$?
– lulu
May 26 at 10:32
• gcd(3,29)=1|17 mean that the result 1 divides the number 17, which is why the task can be solved at all.
– user1159827
May 26 at 10:36
• You meant to write $\implies 3x \equiv 17 \pmod{29}$ . May 26 at 10:38
• Writing run on equations is always confusing. $(3,29)$ is not equal to $1|17$ in any sense so don't write an equality between them. In any case, as I mentioned, the inverse of $3\pmod {29}$ is $10$ by inspection, no Euclidean algorithm needed. But your application of that algorithm does confirm $10$ as the inverse, not $-1$.
– lulu
May 26 at 10:40
• This MathJax tutorial explains how to typeset mathematics on this site. May 26 at 10:55

You correctly applied the extended Euclidean algorithm to show that $$1 = 10 \cdot 3 - 1 \cdot 29$$. However, this does not imply that $$-1$$ is the multiplicative inverse of $$3$$ modulo $$29$$. Observe that $$1 \equiv 10 \cdot 3 - 1 \cdot 29 \equiv 10 \cdot 3 \pmod{29}$$ since $$1$$ and $$10 \cdot 3$$ differ by a multiple of $$29$$. Hence, $$3^{-1} \equiv 10 \pmod{29}$$.
Therefore, \begin{align*} 3x & \equiv 17 \pmod{29}\\ 10 \cdot 3x & \equiv 10 \cdot 17 \pmod{29}\\ x & \equiv 170 \pmod{29}\\ x & \equiv 5 \cdot 29 + 25 \pmod{29}\\ x & \equiv 25 \pmod{29} \end{align*}
Check: If $$x \equiv 25 \pmod{29}$$, then $$3x \equiv 3 \cdot 25 \equiv 75 \equiv 2 \cdot 29 + 17 \equiv 17 \pmod{29}$$.