Solution of Congruence

42 Views Asked by At

So I understand that when you have $a \equiv b \bmod m$ that means that $(a-b)=qm$ for some integer $q$

But I find the topic really confusing. Below is a question I had recently, and I would appreciate some advice on how to answer it, so far all that I have read, been taught, has been quite confusing:

Find a solution of the congruence; $1990x \equiv 15 \bmod 2015$

1

There are 1 best solutions below

1
On BEST ANSWER

$x$ is a solution if and only if :

$$1990x-15 \text{ is divisible by } 2015 $$

if and only if we can find $m\in\mathbb{Z}$ such that :

$$1990x+2015m=15 $$

if and only if we can find $m\in\mathbb{Z}$ such that :

$$398x+403m=3 $$

Now justify that $398$ and $403$ are prime to each other by computing the Euclidean algorithm and find a Bezout identity (using the same Euclidean algorithm) :

$$398u+403v=1 $$

Deduce from this an $x$ that will do the job.