0
$\begingroup$

I've used the Euclidean Algorithm to solve congruences of the form $$ax \equiv b \pmod n$$ where $n >a$, for example: $16x \equiv 5 \pmod{29}$. When $n <a$, for example, $$31x \equiv 5 \pmod{23}$$ I don't know how to apply the Euclidean Algorithm. Please help me and please include some explanation with it.

$\endgroup$
2
$\begingroup$

[For the following paragraphs, please refer to the figure at the end of the last paragraph (the figure is also available in PDF).]

The manipulations performed from steps (0) to (17) were designed to create the linear system of equations (2a), (7a), (12a) and (17a). The manipulations end when the absolute value of a coefficient of the latest equation added is 1 (see (17a)).

It is possible to infer equations (7a), (12a) and (17a) from (0), (7) and (12) respectively without performing manipulations (0) to (17) directly. In every case, select the smallest absolute value coefficient, generate the next equation by replacing every coefficient with the remainder of the coefficient divided by the selected coefficient (smallest absolute value coefficient) – do the same with the right-hand constant – and add the new variable whose coefficient is the smallest absolute value coefficient. If the new equation has a greatest common divisor greater than one, divide the equation by the greatest common divisor. Stop when the absolute value of a coefficient of the latest equation added is 1.

enter image description here

$\endgroup$
1
$\begingroup$

Although the answer of mahdokht is absolutely correct, I think it is not helpful in understanding how to solve such problems in general (since it makes use of guessing which may work here but can be tedious if 23 and 31 are replaced by larger numbers. So here's my way to do it:

Since $\gcd(31,23)=1$ it is well-known (Bezout's lemma) that we can find integers $a,b$ such that $31a+23b=1$. Euclid's Algorithm tells us how to find $a,b$. The usual way is this:

$31=1*23+8$

$23=2*8+7$

$8=1*7+1$

Hence $$1=1*8-1*7=1*8-1*(23-2*8)$$$$=3*8-1*23=3*(31-1*23)-1*23=3*31-4*23$$

Hence $3*31-4*23=1$ i.e. $31*3 \equiv 1 \mod 23$.

Hence $31*15 \equiv (31*3)*5 \equiv 5 \mod 23$.

$\endgroup$
0
$\begingroup$

$31 x \equiv 23x + 8x$

$\therefore 31 x \equiv 5 \pmod{23}\\\implies 8 x \equiv 5 \pmod{23}\\ \implies 8 x \equiv 120 \pmod{23}\\ \implies 8(x - 15) \equiv 0 \pmod{23}\\\implies x - 15 \equiv 0 \pmod{23}\\\implies x \equiv 15 \pmod{23} $

$\endgroup$
  • $\begingroup$ Why has it become 120 (mod 23)? $\endgroup$ – katrina13 Aug 27 '15 at 8:52
0
$\begingroup$

$\gcd (31,23) = 1$. Hence the congruence has unique solution.
Since $\gcd (31,23) = 1$, there exist integers u and v such that $31u+23v=1$. Here $u=3$, $v=-4$.
Therefore, $31.3+23.(-4)=1$ and this implies $31.3 \equiv 1 \pmod{23}$. Therefore, $31.15 \equiv 5 \pmod{23}$.
Hence $x=15$ is a solution.
All solutions are $x \equiv 15 \pmod{23}$, i.e., $x \equiv 31 \pmod{23}$. All the solutions are congruent to $31\pmod{23}$ and therefore the given congruence has a unique solution.

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