Solve ## 25x\equiv 15\pmod {29} ##.

[Math100]

Homework Statement

Solve the following linear congruence:
$25x\equiv 15\pmod {29}$.

Relevant Equations

None.

Consider the linear congruence $25x\equiv 15\pmod {29}$.
By corollary, if $gcd(a, n)=1$, then the linear congruence $ax\equiv b\pmod {n}$ has
a unique solution modulo $n$.
Observe that $gcd(25, 29)=1$.
This means that the linear congruence $25x\equiv 15\pmod {29}$ has a
unique solution modulo $n$.
Thus
\begin{align*}
&25x\equiv 15\pmod {29}\\
&-4x\equiv 15\pmod {29}\\
&-28x\equiv 105\equiv 18\pmod {29}.\\
\end{align*}
Therefore, $x\equiv 18\pmod {29}$.

 

[fresh_42]

Homework Statement:: Solve the following linear congruence:
$25x\equiv 15\pmod {29}$.
Relevant Equations:: None.

Consider the linear congruence $25x\equiv 15\pmod {29}$.
By corollary, if $gcd(a, n)=1$, then the linear congruence $ax\equiv b\pmod {n}$ has
a unique solution modulo $n$.
Observe that $gcd(25, 29)=1$.
This means that the linear congruence $25x\equiv 15\pmod {29}$ has a
unique solution modulo $n$.
Thus
\begin{align*}
&25x\equiv 15\pmod {29}\\
&-4x\equiv 15\pmod {29}\\
&-28x\equiv 105\equiv 18\pmod {29}.\\
\end{align*}
Therefore, $x\equiv 18\pmod {29}$.

Right.

The standard procedure uses the Euclidean division. Given any two numbers $a,b$ there are numbers $x,y$ such that $\operatorname{gcd}(a,b)=xa+yb.$ (Bézout's Identity)

\begin{align*}
29 &= 1\cdot 25 +4\\
25&= 6\cdot 4 +1\\
4&= 4\cdot 1 + 0
\end{align*}
So $1=25 -6\cdot 4=25-6\cdot (29-1\cdot 25)= 25- 6\cdot 29 +6\cdot 25=-6\cdot 29 + 7\cdot 25.$ This means modulo $29$ that $1 \equiv 7\cdot 25 \pmod {29}$ or $25^{-1}\equiv 7\pmod {29}.$

Therefore $x\equiv 25^{-1} \cdot 15 \equiv7\cdot 15 \equiv 105 \equiv 18 \pmod{29}.$

This may look longer than what you did, however, it can be programmed and works always. At least for coprime numbers $a,b.$ Otherwise, we do not have an inverse.