2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ $9\times 7\equiv 63\equiv 15\not \equiv -3 \pmod {24}$. $\endgroup$ – lulu Mar 31 '17 at 12:38
  • $\begingroup$ @lulu Hi lulu, what is this referring to? $\endgroup$ – Programmer Mar 31 '17 at 12:40
  • 1
    $\begingroup$ 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$. $\endgroup$ – lulu Mar 31 '17 at 12:42
  • $\begingroup$ we get $$5;13;21$$ $\endgroup$ – Dr. Sonnhard Graubner Mar 31 '17 at 12:54
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks very much :) I realised my mistake. And also thanks for helping me find mod 24 answer. Appreciate it. $\endgroup$ – Programmer Mar 31 '17 at 13:10
  • 1
    $\begingroup$ 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}$ $\endgroup$ – lulu Mar 31 '17 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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