1
$\begingroup$

Hi is there anything wrong with the following?

Q1: Express gcd(2,17) as a linear combination of 2 and 17

gcd(2,17)
17 = 8 * 2 + 1
2 = 2 * 1 
gcd(2,17) = 1
1 = -8 * 2 + 17
∴ gcd(2,17) = 1 = (-8) 2 + (1) 17

Q2: Find an inverse of 2 modulo 17

2(mod 17)
gcd(2,17) = 1
17 = 8 * 2 + 1
1 = (-8) 2 + (1) 17
Inverse of 2(mod 17) = -8(mod 17) = 9(mod 17)
∴ 9 is the inverse.

Q3: 2x ≡7(mod 17)

Inverse is 9
9*2x ≡9*7(mod 17)
18x ≡63(mod 17)
x ≡12(mod 17)=12 

This is the mark distribution Q1 - 3marks, Q2 - 2 marks, Q3 - 4marks. I'm not really sure if what I've done is right but for Q3, if you were marking it for 4 marks, does the working seem sufficient to get the full mark? I feel like it's too short and I'm missing something.

Thanks

$\endgroup$
  • 2
    $\begingroup$ It's correct! Please do format your posts better though:) $\endgroup$ – AnotherJohnDoe Oct 11 '17 at 9:30
  • 1
    $\begingroup$ It´s all correct, by applying the extended euclidean algorithm You can find the inverse of $2(\mod 17)$ and thus You can solve equations like in Q3. $\endgroup$ – Peter Melech Oct 11 '17 at 9:30
  • 1
    $\begingroup$ Please read this tutorial on how to typeset mathematics on this site. $\endgroup$ – N. F. Taussig Oct 11 '17 at 10:43

Your Answer

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

Browse other questions tagged or ask your own question.