Computing linear congruence

Question

I have the following linear congruence:

$$40x\equiv 28\pmod{73}$$

I have attempted to simplify the congruence by dividing both terms by 4,

$$10x \equiv 7\pmod{73}$$

but I can't figure out what to do next.

What would be the best method around solving this?

Use Euclid's Algorithm $10 \times A + 73 \times B=1$. Now multiply the equation by $10^{-1} = A$. — Donald Splutterwit, May 27 '18 at 17:04
$10$ and $73$ are the input values for Euclid's algorithm ... — Donald Splutterwit, May 27 '18 at 17:07
Euler's theorem says that $40^{72} \equiv 1 \mod 73.$ This does not provides the smallest solution, but always works. — Bumblebee, May 27 '18 at 19:27
@Fehniix Please recall that if the OP is solved you can evaluate to accept an answer among the given, more details here https://meta.stackexchange.com/questions/5234/how-does-accepting-an-answer-work — user, Jun 22 '18 at 20:56

score 0 · Answer 1 · answered May 27 '18 at 17:23

0

We get $$x\equiv \frac{7}{10}\equiv \frac{80}{10}\equiv 8 \mod 73$$

answered May 27 '18 at 17:23

score 0 · Accepted Answer · answered May 27 '18 at 17:24

Note that $10$ and $73$ are relatively primes thus by Bezout Identity we can find by Euclidean algorithm $a$ and $b$ such that

$$10a+73b=1\implies 10 a =1-73b$$

thus $a$ is the inverse of $10 \mod{73}$ and then

$$10x \equiv 7 \mod {73}\implies 10ax \equiv 7a \mod {73}\implies x \equiv 7a \mod {73}$$

2 Answers2