# Are $n^2-1$ and $N$ always relatively prime? [closed]

Consider $$n = 2,3,4,5$$ for which we have the corresponding $$N=3,8,15,24$$.

In fact, so are the numbers up to 15: Their GCD is 1.

How can I prove that these expressions are always relatively prime to each other (or not)?

• Do you mean to ask if $n$ and $n^2-1$ are always coprime? – Eevee Trainer Feb 21 '19 at 4:21
• $n\cdot n - (n^2-1) = 1\$ – Bill Dubuque Feb 21 '19 at 4:24
• How can they not be relatively prime? If a prime $p$ divides $n$ then it can not divide $n^2 - 1$. – fleablood Feb 22 '19 at 7:39

Hint $$:$$

$$a,b \in \Bbb Z$$ with $$ax+by = 1$$ for some integers $$x,y \in \Bbb Z \implies \text {gcd}\ (a,b)=1.$$

Proof $$:$$

Let $$\text {gcd} (a,b) = d$$ then $$d \mid a,d \mid b$$ $$\implies d \mid ax+by = 1$$ $$\implies d=1.$$

Now use the hint given by Bill Dubuque in his comment above to complete the proof.

You have $$gcd(n,n-1) = 1$$ and $$gcd(n,n+1)=1$$.

So, it follows $$gcd(n,(n+1)(n-1)) = gcd(n,n^2-1)= 1$$.

If a prime number $$p$$ divides $$n$$ then $$p$$ divides $$n^2$$ and $$p$$ does not divide $$n^2 - 1$$.

So $$n$$ and $$n^2 - 1$$ can't have any prime divisors in common.