# Integers and Division, Modular Arithmetic…

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

• It's correct! Please do format your posts better though:) – AnotherJohnDoe Oct 11 '17 at 9:30
• 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. – Peter Melech Oct 11 '17 at 9:30
• Please read this tutorial on how to typeset mathematics on this site. – N. F. Taussig Oct 11 '17 at 10:43