4
$\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$
  • 1
    $\begingroup$ Try to run Euclidean algorithm. $\endgroup$ – peterwhy Dec 2 '14 at 14:45
  • $\begingroup$ $\forall{n,m,p>1} : p|n \implies p\not|(mn+1)$ $\endgroup$ – barak manos Dec 2 '14 at 15:03
  • $\begingroup$ If two numbers have a common factor, their difference must be a multiple of that factor. $\endgroup$ – MartianInvader Dec 2 '14 at 23:14
13
$\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$
  • $\begingroup$ I think you mean integers a and b, as -(x^2) is never going to be a natural number... $\endgroup$ – StephenTG Dec 2 '14 at 17:13
  • $\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$ – Swapnil Rustagi Dec 4 '14 at 11:11
  • $\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$ – Adam Hughes Dec 4 '14 at 14:08
  • $\begingroup$ @Swapnil I've edited my answer to clarify exactly what I did, hopefully that makes things clear. $\endgroup$ – Adam Hughes Dec 4 '14 at 18:45
6
$\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$
  • $\begingroup$ A Very good and intuitive method. Thanks. $\endgroup$ – Swapnil Rustagi Dec 2 '14 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$
  • $\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$ – Swapnil Rustagi Dec 2 '14 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 '14 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 '14 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$
  • $\begingroup$ Why must $d$ divide $x(x^2+x+1)-(x^3+1)=x^2+x-1$? $\endgroup$ – Swapnil Rustagi Dec 2 '14 at 16:25
  • $\begingroup$ @Swapnil, If $d$ divides both $a,b;d$ must divide $ax+by$ for any integers $x,y$ right? $\endgroup$ – lab bhattacharjee Dec 2 '14 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$ – Swapnil Rustagi Dec 2 '14 at 16:30
  • $\begingroup$ @Swapnil, ya, that what I've tried $\endgroup$ – lab bhattacharjee Dec 2 '14 at 16:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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