Question

If the multiplicative inverse of “53 modulo 21” exists, then which of the following is true?

(a) GCD(53,21) = 1

(b) GCD(53,21) = 29

(c) GCD(53,21) = 53

(d) GCD(53,21) = 12

This question was posed to me by my school principal while I was bunking the class.

My query is from Number Theory in chapter Number Theory and Cryptography of Discrete Mathematics

Answer 1

The correct choice is (a) GCD(53,21) = 1

Easy explanation: The multiplicative inverse of “a modulo m” can be found out by extended Euler’s GCD algorithm, and the time complexity of this method is O(logm). We know that the multiplicative inverse of “x modulo n” exists if and only if x and n are relatively prime (i.e., if gcd(a, m) = 1). So, in this case GCD(53,21) = 1.