$\gcd(N, a)=\gcd(N, N-a)$ for positive integers $N$ and $a$?

Question

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.

Answer 1

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$.

Answer 2

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$

Answer 3

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)$

Answer 4

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).$