6

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

gebruiker
  • 6,154
khernik
  • 1,369
  • 1
    If you divide a congruence $a \equiv b \pmod{m}$ by $k$, where $k$ divides $a$ and $b$, you must divide the modulus $m$ by $\gcd(m,k)$. Here, you get $7x\equiv 2 \pmod{15}$. – Daniel Fischer Aug 22 '13 at 19:32
  • So if I have $17x \equiv 1 (mod 5)$, and I want to get rid of the variable coefficient, I get $x \equiv 17^{-1} (mod \frac{5}{17})$? – khernik Aug 22 '13 at 19:42
  • No. Since $\gcd(17,5) = 1$, you divide the modulus by $1$, that is, leave it unchanged. If you divide $12x \equiv 8 \pmod{30}$ by $4$, for example, you must divide the modulus $30$ by $\gcd(30,4) = 2$. – Daniel Fischer Aug 22 '13 at 19:46
  • Oh, right, ok, I get it, thanks! – khernik Aug 22 '13 at 19:48

1 Answers1

14

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.)

André Nicolas
  • 507,029