Question

The greatest common divisor c, of a and b, denoted as c = gcd(a, b), is the largest number that divides both a and b. One way to write c is as a linear combination of a and b. Then c is the smallest natural number such that c = ax+by for x, y ∈ N. We say that a and b are relatively prime iff gcd(a, b) = 1. Prove that a and n are relatively prime if and only if there exists integer s such that sa ≡n 1. We call s the inverse of a modulo n.

Answer 1

Theorem : a and b are relatively prime iff gcd(a, b) = 1.

So, directly using the above Theorem we get that, a & n are relatively prime off there exist integers s & t such that, sa + tn = 1

So, taking the equation modulo n,

sa + tn = 1 (mod n)

So, sa + 0 1 (mod n) [since, n divides tn, so, tn 1 (mod n)]

So, sa 1 (mod n)

So, s is called the inverse modulo n.