$\gcd(N, a)=\gcd(N, N-a)$ for positive integers $N$ and $a$? If $\gcd(N, a)=1$, then we have $\gcd(N, N-a)=1$.
More generally, can we have $\gcd(N, a)=\gcd(N, N-a)$ for positive integers $N$ and $a$?
Thanks in advance.
 A: Let's have $d=\operatorname{gcd}(N,a)$. $d$ divides $N$ and $a$ so $d$ divides $N-a$. It is therefore a common divisor to $N$ and $N-a$. Is it the largest?
Assume we have a common divisor to $N$ and $N-a,\quad d'\gt d$ therefore $d'$ divides $N-(N-a)=a$ which contradicts the fact that $d$ is the largest common divisor to $N$ and $a$
A: It is the basis of the recursive version of Euclid's algorithm.
Indded, any number which divides $N$ and $a$ divides also $N-a$. Hence, if a number divides $N$ and $N-a$, it also divides $N-(N-a)=a$.
A: It is usual to denote $\gcd(a,b)$ by $(a,b)$.  
By definition of gcd follows $(a,b)\mid a,b$ and $n\mid a,b\iff n\mid (a,b)$.    
$(N,a)\mid N,a\iff (N,a)\mid N,N-a\iff (N,a)\mid (N,N-a)\ \ \ (1)$  
$(N,N-a)\mid N,N-a\iff (N,N-a)\mid N,a\iff (N,N-a)\mid (N,a)\ \ \ (2)$   
$(1)(2)\iff(N,a)=(N,N-a)$
A: Hint $\ $ If $\,d\mid N\ $ then $\ d\mid a\iff d\mid N\!-a.\,$ Hence $\,N,a\,$ and $\,N,N\!-a\,$ have the same set $S\,$ of common divisors $\,d,\,$ so they have the same greatest common divisor $(= \max S).$ 
