3
$\begingroup$

I am stuck with one problem from my discrete math class and don't know how to solve it. I will be grateful for any help!

Find all $x \in \mathbb{Z}_{501}$ for which $51x \equiv 36$, where the multiplication is in $\mathbb{Z}_{501}$.

I started solving it like this:
\begin{align} 51x & \equiv 36 \pmod{501}\\ 51x & \equiv 36 + k501\\ 51x + 501y & = 36 \end{align}

After this, I found $\gcd(51,501)$, which is $3$:
\begin{align} 501 & = 9 \cdot 51 + 42\\ 51 & = 1 \cdot 42 + 9\\ 42 & = 4 \cdot 9 + 6\\ 9 & = 1 \cdot 6 + 3\\ 6 & = 2 \cdot 3 + 0 \end{align}

After this, using back-substitution:
\begin{align} 3 & = -6 \cdot 501 + 59 \cdot 51\\ 36 & = 708 \cdot 51 - 72 \cdot 501 \end{align}

Then I divided equation by the $\gcd$ and solved $17x+167y = 0$.

So my final answers are $x = 708 + 167k$ and $y= -72-17k$ (In our case we don't need $y$, though.)

Answers from my book are $x_1 = 40$, $x_2 = 207$ and $x_3 = 374$, and I don't know how can I get them.

$\endgroup$
0
$\begingroup$

What you have done thus far is correct. Observe that $$708 \equiv 40 \pmod{167}$$ since $$708 = 4 \cdot 167 + 40$$ The distinct solutions are all the integers in $\{0, 1, 2, 3, \ldots, 500\}$, the set of residues modulo $501$, that satisfy the congruence $x \equiv 40 \pmod{167}$. They are \begin{align*} x_1 & \equiv 40 + 0 \cdot 167 \equiv 40 \pmod{501}\\ x_2 & \equiv 40 + 1 \cdot 167 \equiv 207 \pmod{501}\\ x_3 & \equiv 40 + 2 \cdot 167 \equiv 374 \pmod{501} \end{align*}

$\endgroup$
0
$\begingroup$

There is an algorithm for this kind of equation. I usually reformulate: $$ 51 x \equiv 36 \pmod{501} \iff \\ (51 x) \bmod 501 = 36 \iff \\ 51 x = 501 q + 36 \iff \\ 51 x - 501 q = 36 \quad (*) $$ where $x\in \mathbb{Z}_{501}$ and $q \in \mathbb{Z}$.

The last equation $(*)$ can be interpreted as a linear Diophantine equation, where we limit the solutions for $x$ from $\mathbb{Z}$ to $\mathbb{Z}_{501}$.

Number of solutions:

If $g = \gcd(51, 501)$ divides $36$, we have infinite many solutions $(x,q) \in \mathbb{Z}^2$, otherwise none. We have $g=3 \mid 36$, so we got the first case.

Solution of the homogeneous equation:

The reduced equation (divided by $g$) is $$ 17 x - 167 q = 12 $$ The homogeneous equation is $$ 17 x - 167 q = 0 \quad (**) \iff \\ 17 x = 167 q $$ $\gcd(17,167)=1$ implies $17\mid q$ and $167\mid x$. So the homogeneous equation $(**)$ is solved by $$ \{ (167 t, 17 t) \mid t \in \mathbb{Z} \} $$

Finding a particular solution:

The extended Euclidean algorithm for $(51,-501)$ gives numbers $s=59, t=6$ (and $g=3$) such that $$ 51 s - 501 t = g = 3 \iff \\ 51 (12\cdot 59) - 501 (12\cdot 6) = 12\cdot 3 = 36 $$ so a particular solution of $(*)$ is $(x_p, q_p) = (708, 72)$.

The total solutions are $$ \{ (708 + 167 t, 72 + 51 t) \mid t \in \mathbb{Z} \} $$

Limiting to $\mathbb{Z}_{501}$:

We have $$ 708 + 167 t \ge 0 \iff t \ge -708/167 = -4.23\dotsb $$ and $$ 708 + 167 t \le 500 \iff t \le -208/167 = -1.24\dotsb $$ so $t\in \{ -2,-3,-4\}$ and $x \in \{ 40, 207, 374 \}$.

$\endgroup$
0
$\begingroup$

Note $\,708\bmod{\!167} = 40\ $ thus $\,708+167k = 40+167n.\ $ Next, to lift this solution from modulus $167$ to $\,\color{#c00}3\cdot 167 = 501$ we divide $n$ by $\color{#c00}3,\,$ so $\, n = i + \color{#c00}3j,\,$ which yields

$$\begin{align}{\rm mod}\,\ \color{#c00}3\!\cdot\! 167\!:\,\ 40 + 167n &\equiv 40+167(i+\color{#c00}3j), \ {\rm for} \ \,0\le i < 3\\ &\equiv 40+167\,i,\quad {\rm for}\ \ \ i=0,\,1\,,2\\ &\equiv 40,\ 40\!+\!167\!\cdot\! 1,\ 40\!+167\!\cdot\!2\\ &\equiv 40,\ 207,\ 374 \end{align}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.