# Dividing the linear congruence equations

$$42x \equiv 12 \pmod {90}$$

This is a pretty simple congruence equation. $\gcd(42,90)=6$; $6|12 \implies$ a solutions exists.

I’ve always been solving congruence equations with that scheme:

$$\gcd(42,90)=1*90-2*42$$

$$90k + \frac{-2*12}{6}=90k-4$$

This should be the solution. It satisfies the equation too, so everything is ok.

However, according to this pdf, the soulutions are also $11$, $26$, $41$,… They divided the equation by $6$. I however don’t like the way they did it. I’ve always seen people doing this with the following results:

$$7x \equiv 2 \pmod {90}$$

without dividing the $\pmod {90}$ part. So should I divide it as well, or not? That’s pretty confusing.

If the answer is positive, and the simplified equation is correct, then are all its solutions correct for the top equation in this thread? I mean, this equation has $\pmod {90}$, the other $\pmod {15}$, I don’t see how they can be equal.

#### Solutions Collecting From Web of "Dividing the linear congruence equations"

Consider the congruence
$$ax\equiv ay \pmod{n}.\tag{1}$$

If $a$ and $n$ are relatively prime, then the congruence (1) is equivalent to the congruence $x\equiv y\pmod{n}$.

More generally, if $\gcd(a,n)=d$, then the congruence (1) is equivalent to the congruence $x\equiv y \pmod{\frac{n}{d}}$. If we put $d=1$, we arrive at the special case dealt with in the preceding paragraph.

For your particular numbers, the original congruence is equivalent to $7x\equiv 2\pmod{15}$. This has the solution $x\equiv 11\pmod{15}$. This solution is unique modulo $15$.

If we want to express the answers modulo the original $90$, there are several solutions. For $x\equiv 11\pmod{15}$ if and only if $x$ is congruent to one of $11,26,41,56,71,86$ modulo $90$. (We keep adding $15$’s.)