1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – TonyK Dec 10 '18 at 10:53
1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

$$\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*}$$

$\endgroup$
0
$\begingroup$

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

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