2

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.

The Pointer
  • 4,182
Programmer
  • 755

1 Answers1

1

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

TheWanderer
  • 5,126
  • Thanks very much :) I realised my mistake. And also thanks for helping me find mod 24 answer. Appreciate it. – Programmer Mar 31 '17 at 13:10
  • 1
    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