# how to solve $min\{x \in \mathbb N_0 \quad |x \cdot 714\quad mod \quad 1972 \quad = \quad 1292 \quad mod \quad 1972 \}$ (modulo equation)

Question: How can I solve: $min\{x \in \mathbb N_0 \quad |x \cdot 714 \equiv 1292 \mod 1972 \}$ ?

$x \cdot a \equiv _m b \Rightarrow m|x \cdot a – b$

different way of notation:

$min\{x \in \mathbb N_0 \quad | x \cdot 714 \equiv_{1972} 1292\}$

How to go on?

I appreciate every hint.

#### Solutions Collecting From Web of "how to solve $min\{x \in \mathbb N_0 \quad |x \cdot 714\quad mod \quad 1972 \quad = \quad 1292 \quad mod \quad 1972 \}$ (modulo equation)"

As $714=34\cdot21$, $1292=34\cdot 38$, $1972=34\cdot 58$, this is equivalent to solving $21 x\equiv 38\mod 58$.

We have to find the inverse of $21$ modulo $58$. The tool for this is the Extended Euclidean algorithm:
$$\begin{array}{rrrl} \hline r_i&u_i&v_i&q_i\\ \hline 58&0&1\\ 21&1&0&2\\ \hline 16&-2&1&1\\ 5&3&-1&3\\1&-11&4\\ \hline \end{array}$$
Thus the inverse of $21$ mod $58$ is $-11\equiv47$. The solution is
$$x\equiv47\cdot 38\equiv (-11)(-20)\equiv 46\mod 58.$$

Let’s say you want to solve $ax \equiv b \mod{m}$. If $gcd(a,m)=1$, then there is a unique solution. (You should be able to get this solution)

Now if $gcd(a,m) = d$, then solution exists iff $b$ divides $d$. You should try to reduce this to a equation between $\frac{a}{d}, \frac{b}{d}$ and $\frac{m}{d}$. From this solution , you will get mutiple solutions for the initial equation. Can you easily find the min of that?

Further hint for the reduction – Solving $ax \equiv b \mod{m}$ is same as solving $ax = b + my$.