Extended Euclidean Algorithim - Arithmetic Modulo 60

Question

I get the Extended Euclidean Algorithm but I don't understand what this question is asking me:

In this question we consider arithmetic modulo 60 ("clock arithmetic" on the clock with numbers {0,1,2,3,...,58,59}). Which of the following statements apply?

a. 50 X 50 = 40 modulo 60

b. 17 + 50 = 3 modulo 60

c. 4100 x 10 = 0 modulo 60

d. 1/17 = 53 modulo 60

e. 37 + 50 = modulo 60

f. 1/10 is undefined modulo 60

g. 17 - 35 = 42 modulo 60

h. 17 - 25 = 18 modulo 60

I have to pick the right ones but I'm not sure how to work it out? Like if they gave something like

17x = 1 mod(43) I could solve it but I'm not sure how you would solve the other question

P.S I have the answers I just dont want to look at them as I'd rather try to understand first as this is revision for my exam. thanks

Answer 1

Except for (d) and (f), these are all basically of the same form: they are all asking if the expressions on the left and right sides are equivalent mod $60$; that is, if they both leave the same remainder when divided by $60$.

(d) and (f) both ask about the multiplicative inverse of $x$ mod $60$; that is, they ask if $x^{-1}\equiv y\mod{60}$, or in other words if $xy\equiv 1\mod{60}$ (or, if $xy$ leaves a remainder of $1$ when divided by $60$).

Answer 2

It is a simple multiple choice question.

Hints:

$a), b), e) $ : You just have to compute and reduce to check if true ot not.

$c)$ means: ‘Is 4100\times 10 divisible by 60?’. You may have good reasons to answer without having to perform a division.

$d)$ $\iff $ 17 × 53 =1 modulo 60. Check if true.

$f)$ means ‘Is 10 a unit or not modulo 60’

$g), h)\iff $ 17 = 35 + 42, resp. 17 = 25 +18, modulo 60.