-1
$\begingroup$

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

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

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.