# Solve the congruence $9x \equiv −3 \pmod{24}$. Give your answer as a congruence to the smallest possible modulus, and as a congruence modulo 24.

I've been able to find the answer as a congruence to the smallest possible modulus (i.e. mod 8) but unsure how to find answer as congruence to mod 24. Also, is everything I've done below correct?:

gcd(9,24) = 3

Therefore, our congruence becomes 3x ≡ -1 (mod 8)

So, 3x ≡ 7 (mod 8)

We must find inverse 'c' of 3 (mod 8), i.e. 3c ≡ 1(mod 8)

gcd(3,8) = 1

let 3c + 8y = 1

Using extended Euclidean Algorithm, we get c = 1

Therefore, solution of 3x ≡ 7 (mod 8) (i.e. smallest possible modulus) is:

x ≡ 7 (mod 8)

Now, how to find solution as a congruence to modulus 24? Assuming everything I've done above is correct.

• $9\times 7\equiv 63\equiv 15\not \equiv -3 \pmod {24}$. – lulu Mar 31 '17 at 12:38
• @lulu Hi lulu, what is this referring to? – Programmer Mar 31 '17 at 12:40
• I am pointing out that your solution is not correct. Even $\pmod 8$ it is not correct...$3\times 7=21\equiv 5\not \equiv 7\pmod 8$. – lulu Mar 31 '17 at 12:42
• we get $$5;13;21$$ – Dr. Sonnhard Graubner Mar 31 '17 at 12:54

How do you get $c=1$. The inverse of $3c \equiv 1 \pmod{8}$ is $c=3$ (since $3\times 3=9$). In this way, you obtain $x \equiv 5 \pmod{8}$.
Observe that $9 \times 5=45$ and $24 \times 2=48$, so $x \equiv 5 \pmod{24}$.
• Just to say: this is not the $\pmod {24}$ answer. $x\equiv 5 \pmod 8$ is correct, $\pmod 8$. but then you get $x\equiv 5,13,21\pmod {24}$ – lulu Mar 31 '17 at 13:40