0
$\begingroup$

I am trying to find a way of solving congruence systems of the form:

$$ b*x = a \quad mod \quad y $$

Where $b$ and $y$ are not prime to each other.

My current way of solving congruence systems where $b$ and $y$ are prime to each other is to find the multiplicative inverse of $b$ in $y$ and multiply $b$ (which will make it 1) and $a$ with this value.

Example:

$$ 13 \ x = 3 \ mod \ 17$$

I calculate the mul. inverse of 13 and multiply 3 and 13 times that value and thus I have solved this equation.

But I dont know how I can do that where $b$ and $y$ are not prime to each other.

Example:

$$3 x = 3 \ mod \ 9$$

How would I solve this ?

$\endgroup$
1
  • $\begingroup$ thank you, sorry about the duplicate, didnt know how to search for my problem $\endgroup$ – zython Aug 29 '17 at 19:01
1
$\begingroup$

A congruence $$ax\equiv b\pmod{n}\tag{1}$$ is soluble iff $\gcd(a,n)\mid b$. In this case (1) is equivalent to $$\frac agx\equiv \frac bg\pmod{\frac ng}\tag{2}$$ where $g=\gcd(a,n)$. As $a/g$ is coprime to $n/g$ you may solve (2) by multiplicative inverses if you like.

$\endgroup$
1
  • $\begingroup$ makes sense, accepted $\endgroup$ – zython Aug 29 '17 at 19:01

Not the answer you're looking for? Browse other questions tagged or ask your own question.