Number Theory/Abstract Algebra?

Question

Let n and a be a positive integers and let d = gcd(a,n). Show that 1 = ax mod n has a solution for x iff d = 1.

This is what I have so far:

(->) Assume ax = 1 mod n is true <=> 1 = ax mod n. Then ax = qn + 1 (by division algorithm). So, ax +(-q)n = 1. This implies that gcd(a,n) = 1.

(<-) Assume gcd(a,n) = 1. By GCD Thm, 1 = as + nt for some integers s and t. Then, as = 1 + (-t)n which implies that 1 is the remainder upon dividing as by n. So, as mod n = 1.

Answer 1

It looks to me like you&#039;ve already proved it yourself.

Your (-&gt;) is fine. And for (&lt;-), you&#039;re basically done. You found that there exists an integer s such that as = 1 mod n. Letting x = s, we see that 1 = ax mod n has a solution.