Why $\gcd(a,a+N) =1$

87 Views Asked by At

By experiment, I notice that $$\gcd(a,a+N) =1$$ Where $N$ is a big composite integer number that is hard to factor and does not have a common divisor with $a$. And $a$ is a positive big integer that might be bigger than $N$.

Is it really the case, and if so then why it's happening?

2

There are 2 best solutions below

0
On BEST ANSWER

in general $$gcd(a,b)=gcd(a,a-b)$$ then $$gcd(a,a+N)=gcd(a,a+N-a)=gcd(a,N)=1$$

0
On

When the $\gcd$ of two numbers is $1$, all that means is that they have no common divisors (other than $\pm 1$). If $N$ has no common divisor with $a$, then neither does $a+N$.