# Let d = gcd(a,n). Show that if $\bar {a}$ $\bar{x}$ = $\bar{1}$ has a solution for x, then d = 1

The full question is:

Let $a$ and $n$ be positive integers and let $d = \gcd(a, n)$. Show that if $\bar{a}$$\bar{x} = \bar{1} has a solution for x, then d = 1. My approaching is: Since \gcd(a,n) = d, d is the smallest positive integer that can be written as$$ax + ny = d \text.$$Assume that the function is modulo n, then we have: (ax + ny) \mod n = d \mod n Hence (1 + ny) \mod n = d \mod n (1 + 0) \mod n = d \mod n 1 = d Please correct me if I'm wrong. Thank you. • What does the bar notation mean? Commented Feb 8, 2018 at 6:42 • @user_194421 The bar notation means the equivalence class modulo a number (most of the time n) and a is just an integer. Commented Feb 8, 2018 at 6:47 ## 1 Answer Only with d\equiv1\pmod n you can't conclude that d=1. You should mention that since d is a positive divisor of n, 1\le d\le n. There is another more serious fault. You use Bezout's identity to write$$ax+by=d$$and then you assume that this same x is the solution of \bar a\bar x=\bar 1. My approach: Since \bar a\bar x=\bar 1, that is,$$ax\equiv 1\pmod n,$$there is some y\in\Bbb Z such that$$ax-1=yn$$or$$ax-yn=1$$Now, if d is a positive, common divisor of a and n, say a=a'd, n=n'd, we have$$d(a'x-yn')=1$$so$d$divides$1$. This implies$\gcd(a,n)=1\$.

• So if I can't assume there is the same x, how can I improve my solution? Commented Feb 8, 2018 at 6:51
• Great, I understand this now. Thank you so much. Commented Feb 8, 2018 at 15:47