1
$\begingroup$

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$?

$\endgroup$
8
  • $\begingroup$ 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$? $\endgroup$
    – lulu
    May 26 at 10:32
  • $\begingroup$ gcd(3,29)=1|17 mean that the result 1 divides the number 17, which is why the task can be solved at all. $\endgroup$
    – user1159827
    May 26 at 10:36
  • 1
    $\begingroup$ You meant to write $\implies 3x \equiv 17 \pmod{29}$ . $\endgroup$
    – N. F. Taussig
    May 26 at 10:38
  • $\begingroup$ 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$. $\endgroup$
    – lulu
    May 26 at 10:40
  • 1
    $\begingroup$ This MathJax tutorial explains how to typeset mathematics on this site. $\endgroup$
    – N. F. Taussig
    May 26 at 10:55

1 Answer 1

Reset to default
1
$\begingroup$

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}$.

$\endgroup$
3
  • $\begingroup$ Please strive not to post more (dupe) answers to dupes of FAQs, cf. recent site policy announcement here. $\endgroup$
    – Bill Dubuque
    May 27 at 1:58
  • $\begingroup$ @BillDubuque Do you consider all linear congruences with prime moduli to be duplicates? The reason I answered this question was to address the specific mistake the OP made. $\endgroup$
    – N. F. Taussig
    May 28 at 10:03
  • $\begingroup$ In fact even that mistake itself is a duplicate. $\endgroup$
    – Bill Dubuque
    May 28 at 13:18