Why is this statement true: $\gcd(a,n) = 1$ iff $\gcd(n-a,n) = 1$? I know this has to do with Euclidean division, I just can't prove the => direction.
Any tips would be appreciated!
 A: Every common divisor $d$ of $a$ and $n$ is also a common divisor of $n - a$ and $a$. Conversely, every common divisor $d$ of $n - a$ and $a$ is also a common divisor of $n - a + a = n$ and $a$. Therefore the greatest common divisor of $a$ and $n$ is the same as the greatest common divisor of $n - a$ and $a$.
So, in general, $\gcd(a,n) = \gcd(n-a,n)$.
A: By Bézout's identity we have
$$\gcd(a,n)=1\iff \exists \alpha,\beta\in \mathbb Z\;|\; \alpha a+\beta n=1=(\alpha+\beta)a+\beta(n-a)=1\\\iff\gcd(n-a,a)=1$$
A: Hint $ $ If $\, d\mid n\ $ then $\ d\mid \color{#0a0}{n-a}\iff d\mid \color{#c00}a.\ $ Thus $\ \color{#0a0}{n-a},n\ $ and $\ \color{#c00}a,n\ $ have the same set $S$ of common divisors $\,d,\,$ so they have the same greatest common divisor $\,(= \max S).$
Alternatively, note that the map $\ (a,n)\mapsto (n-a,n)\ $ is linear with determinant $\,\Delta = \color{}{-1}.\ $ Therefore, by the proof below$\ \gcd(a,n) = \gcd(n-a,n).$

Theorem  $\ $ If $\rm\,(x,y)\overset{A}\mapsto (X,Y)\,$ is linear then $\: \rm\gcd(x,y)\mid \gcd(X,Y)\mid \Delta \gcd(x,y),\,\ \Delta = \det A$
Proof $\ $ Inverting the linear map $\rm\,A\,$ by Cramer's Rule (multiplying by the adjugate) yields 
$$\rm \begin{eqnarray} a\ x\, +\, b\ y &=&\rm X\\ \\ \rm c\ x\, +\, d\ y &\ =\ &\rm Y\end{eqnarray}
\quad\Rightarrow\quad \begin{array} \rm\Delta\ x\ \ \ =\ \ \ \rm d\ X\, -\, b\ Y \\\\ \rm\Delta\ y\ =\ \rm -c\ X\, +\, a\ Y \end{array}\ ,\quad\ \Delta\ =\ ad-bc\qquad $$
Hence, by RHS system, $\rm\ n\ |\ X,Y\ \Rightarrow\ n\ |\ \Delta\:x,\:\Delta\:y\ \Rightarrow\ n\ |\ gcd(\Delta\:x,\Delta\:y)\ =\ \Delta\ gcd(x,y)\:.$
In particular $\rm\ n = \gcd(X,Y) \mid \Delta\, \gcd(x,y).\ $ 
Further, by LHS system $\rm\,n\mid x,y\ \Rightarrow\ n\mid X,Y\ \Rightarrow\ n\mid\gcd(X,Y).$
In particular $\rm\ n = gcd(x,y)\mid \gcd(X,Y).\ \ \ $  QED
A: Proof by Zout's identity:
If $\gcd(a,n)=1$ then there exists $x$ and $y$ for them $ax+ny=1$, hence $a(x+y)+(n-a)y=1$ and then $\gcd(n-a,a)=1$
A: Use the property $gcd(a,b)=1 \Leftrightarrow$ there exist $m,n$ such that $ma+nb=1$
$(\Rightarrow)$ Suppose that $gcd(a,n)=1$. Then there exist $l,k$ such that $la+kn=1 \Leftrightarrow kn-ka+ka+la=1\Leftrightarrow k(n-a)+(k+l)a=1$. So $gcd(n-a,a)=1.$
$(\Leftarrow)$ Suppose $gcd(n-a,a)=1$. Then there exist $l,k$ such that  $l(n-a)+ka=1 \Leftrightarrow  ln+(k-l)a =1$. Thus $gcd(a,n)=1$.
