# Solve linear congruence for $x$ : $34x ≡ 51( \text{mod}\; 85)$

Solve the linear congruence for $$x$$ : $$34x ≡ 51( \text{mod}\; 85)$$

I found using the Euclidean Algorithm that the GCD is $$17$$. Because the GCD evenly divides $$51$$, there equivalence should be solvable. I made a Diophantine equation to solve: $$34p - 85q = 17$$

From using the Euclidean Algorithm I have:

$$85 = 2 \cdot34+17$$

$$34=2 \cdot 17+0$$

$$17=85-2 \cdot34$$

I do not know where to go from here in order to make this model the Diophantine equation in order to solve for $$p$$, and I'm not entirely sure what to do with the solution when I get it, because I am solving for $$x$$.

• Note that once you have one solution, $x$ say, then $x+5m$ are solutions for all integers $m$, because $34\cdot 5\equiv 0$ mod $85$. – TonyK Dec 10 '18 at 10:53

In this case, it may be easier to reduce by dividing by $$17$$. You know that $$34x\equiv51\pmod{85}.$$ This equivalence is the same as $$34x-51=85k$$ for some integer $$k$$. Since all of $$34$$, $$51$$, and $$85$$ are divisible by $$17$$, we may divide through by $$17$$ to get $$2x-3=5k.$$ In other words, the original equivalence has the same solutions as $$2x\equiv3\pmod{5}.$$ Can you finish it from here?

$$\implies34x=51+85y$$ where $$y$$ is an arbitrary integer

$$\iff2x=3+5y$$

$$\iff2(x+1)=5(y+1)$$

$$\implies\dfrac{2(x+1)}5= y+1$$ which is an integer

$$\implies5|2(x+1)\iff5|(x+1)$$ as $$(2,5)=1$$

We want to solve for $$x$$ where $$34x-51=85q$$ for some $$q \in \mathbb{Z}$$.

$$17(2x-3)=17(5q)$$

$$2x \equiv 3 \pmod{5}$$

Multiply both sides by $$3$$,

$$x \equiv 9 \equiv -1 \equiv 4 \pmod{5}$$

$$\begin{eqnarray*} 34x & \equiv & 51 \mod 85 \stackrel{34 = 85-51}{\Leftrightarrow}\\ -51x & \equiv & 51 \mod 85 \stackrel{:17}{\Leftrightarrow}\\ -3x & \equiv & 3 \mod 5 \stackrel{:(-3)}{\Leftrightarrow}\\ x &\equiv &-1 \equiv 4 \mod 5 \end{eqnarray*}$$

Theorem: If $$\gcd\{a,m\}=d$$ and suppose $$d \vert b$$, then the linear congruence $$ax \equiv b \;(\text{mod}\;m)$$ has exactly $$d$$ solutions modulo $$m$$. These are given by $$t,t+\frac{m}{d},t+\frac{2m}{d},\cdots,t+\frac{m(d-1)}{d}$$ where $$t$$ is the solution , unique modulo $$\frac{m}{d}$$, of the linear congruence $$\frac{a}{d}x \equiv \frac{b}{d}\;(\text{mod}\;\frac{m}{d})$$

In your case, $$a=34$$, $$b=51,m=85$$ and $$\gcd\{34,85\}=17$$. so $$t$$ is the solution of $$2x \equiv 3\;(\text{mod 5})$$ Now since $$\gcd\{2,5\}=1$$, we have $$t \equiv3\cdot2^{\phi(5)-1}(\text{mod}\;5)$$That is $$t \equiv 24\;(\text{mod}\;5) \equiv 4$$

So the $$17$$ solutions are $$4, 4+\frac{85}{17},4+\frac{2 \cdot 85}{17}, \cdots,4+\frac{16\cdot 85}{17}$$

Reference : Tom M. Apostol : Introduction to Analytic number theory