5
$\begingroup$

I just read that for a natural number $x$, the three numbers $x$, $x^3 + 1$ and $x^2 + x + 1$ are all mutually co-prime.

I couldn't find a reason why this is true. OK, any of them does not divide either of the other two, but is it enough to conclude that their GCD is 1?

Couldn't they have any common factors?

Also on what basis, are two consecutive integers co-prime? I know they cannot have a common factor but don't know why.

$\endgroup$
3
  • 2
    $\begingroup$ Try to run Euclidean algorithm. $\endgroup$
    – peterwhy
    Dec 2, 2014 at 14:45
  • 1
    $\begingroup$ $\forall{n,m,p>1} : p|n \implies p\not|(mn+1)$ $\endgroup$ Dec 2, 2014 at 15:03
  • 1
    $\begingroup$ If two numbers have a common factor, their difference must be a multiple of that factor. $\endgroup$ Dec 2, 2014 at 23:14

4 Answers 4

14
$\begingroup$

We see that the gcd of $m$ and $n$ always divides any expression of the form $am+bn$ since $m=ck, n=cj\implies c|(am+bn)=c(ak+bj)$. Being coprime means the gcd is $1$, so let's show this.

Case 1: For $m=x$ and $n=x^3+1$ we see with $a=-x^2$ and $b=1$ we have

$$-x^3+x^3+1=1$$

so they are coprime.

Case 2: For $m=x$ and $n=x^2+x+1$ we see $a=-(x+1)$ and $b=1$ gives

$$-x^2-x+x^2+x+1=1$$

which verifies coprimality.

Case 3: Finally with $m=x^2+x+1$ and $n=x^3+1$ we see that $a=(x-1)$ and $b=-1$ gives us

$$-x^3+1+x^3+1=2$$

so that $\gcd(x^2+x+1,x^3+1)\big|2$. But $x^2+x+1$ is always odd, so the gcd must be $1$.

$\endgroup$
4
  • 1
    $\begingroup$ I think you mean integers a and b, as -(x^2) is never going to be a natural number... $\endgroup$
    – StephenTG
    Dec 2, 2014 at 17:13
  • 1
    $\begingroup$ How stupid of me! I could have applied Euclid's algorithm - such an easy question. Though, I do not understand how does the algorithm indicate "$m,n$ are coprime iff there are integers $a, b$ so that $am+bn=1$". $\endgroup$ Dec 4, 2014 at 11:11
  • 1
    $\begingroup$ @Swapnil That's a theorem. If you do not believe it, you do not need that particular result, you can just use that the GCD divides any combination, that is all I have used. $\endgroup$ Dec 4, 2014 at 14:08
  • 1
    $\begingroup$ @Swapnil I've edited my answer to clarify exactly what I did, hopefully that makes things clear. $\endgroup$ Dec 4, 2014 at 18:45
7
$\begingroup$

For your second question, say, $x$ and $x+1$ has some common factor $d$. Then consider

$$(x+1)-x = 1$$

The left hand side is a multiple of $d$, so the right hand side should also have $d$ as a factor. Then $d$ can only be $1$.

$\endgroup$
1
  • $\begingroup$ A Very good and intuitive method. Thanks. $\endgroup$ Dec 2, 2014 at 15:06
2
$\begingroup$

In general $\gcd(a,b)=\gcd(b,a)$ and $\gcd(a,b)=\gcd(a,b-ca)$ (do you understand why?).

Applying that gives: $$\gcd(x,x^3+1)=\gcd(x,1)=1$$ and: $$\gcd(x,x^2+x+1)=\gcd(x,1)=1$$ Also $$\gcd(x^3+1,x^2+x+1)=\gcd(-x^2-x+1,x^2+x+1)=\gcd(2,x^2+x+1)$$ and $x^2+x+1$ is odd for each integer $x$.

This allows the conclusion that $\gcd(x^3+1,x^2+x+1)=1$

$\endgroup$
3
  • $\begingroup$ $\gcd(a,b)=\gcd(a,b-ca)$ because $\gcd(a,b)$ divides $a$ (and hence $ca$ and $b$ and so it divides $b-ca$ as well? Correct reasoning? $\endgroup$ Dec 2, 2014 at 15:11
  • $\begingroup$ Yes. $x|a$ and $x|b$ if and only if $x|a$ and $x|b-ca$. So pair $(a,b)$ has the same set of divisors as pair $(a,b-ca)$. $\endgroup$
    – drhab
    Dec 2, 2014 at 15:18
  • $\begingroup$ @Swapnil: Not correct. Your reasoning only shows that $\gcd(a,b) \mid \gcd(a,b-ca)$. You also need to show that $\gcd(a,b-ca) \mid \gcd(a,b)$. $\endgroup$
    – user21820
    Dec 3, 2014 at 1:34
0
$\begingroup$

If integer $d$ divides both $x^2+x+1, x^3+1;$

$d$ must divide $x(x^2+x+1)-(x^3+1)=x^2+x-1$

$\implies d$ must divide $x^2+x+1-(x^2+x-1)=2$

But $2\mid x(x+1)\implies x^2+x\pm1=x(x+1)\pm1$ are odd $\implies d=1$

$\endgroup$
4
  • $\begingroup$ Why must $d$ divide $x(x^2+x+1)-(x^3+1)=x^2+x-1$? $\endgroup$ Dec 2, 2014 at 16:25
  • $\begingroup$ @Swapnil, If $d$ divides both $a,b;d$ must divide $ax+by$ for any integers $x,y$ right? $\endgroup$ Dec 2, 2014 at 16:26
  • $\begingroup$ So let me guess, all we are trying to do is choosing $a$ and $b$ in $ax+by$ so that we have no variables after solving and then the GCF may be calculated, right? $\endgroup$ Dec 2, 2014 at 16:30
  • $\begingroup$ @Swapnil, ya, that what I've tried $\endgroup$ Dec 2, 2014 at 16:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .