GCD of cubic polynomials












3












$begingroup$


I would appreciate some help finding $GCD(a^3-3ab^2, b^3-3ba^2)$; $a,b in mathbb{Z}$. So far I've got here: if $GCD(a,b)=d$ then $exists alpha, beta$ so that $GCD(alpha, beta)=1$ and $alpha d=a$, $beta d=b$.



Therefore we know that $GCD(a^3-3ab^2, b^3-3ba^2)=d^3 GCD(alpha^3-3alpha beta^2, beta^3-3beta alpha^2)$. However I don't know to figure out $GCD(alpha^3-3alpha beta^2, beta^3-3beta alpha^2)$ given that $GCD(alpha,beta)=1$.










share|cite|improve this question









$endgroup$












  • $begingroup$
    I meant that a and b are integers.
    $endgroup$
    – Oleksandr
    9 hours ago










  • $begingroup$
    For integers, it can have many values. What do you want to prove?
    $endgroup$
    – Dietrich Burde
    9 hours ago










  • $begingroup$
    I want to find the explicit formula for GCD of those two polynomials in terms of GCD of a and b.
    $endgroup$
    – Oleksandr
    8 hours ago
















3












$begingroup$


I would appreciate some help finding $GCD(a^3-3ab^2, b^3-3ba^2)$; $a,b in mathbb{Z}$. So far I've got here: if $GCD(a,b)=d$ then $exists alpha, beta$ so that $GCD(alpha, beta)=1$ and $alpha d=a$, $beta d=b$.



Therefore we know that $GCD(a^3-3ab^2, b^3-3ba^2)=d^3 GCD(alpha^3-3alpha beta^2, beta^3-3beta alpha^2)$. However I don't know to figure out $GCD(alpha^3-3alpha beta^2, beta^3-3beta alpha^2)$ given that $GCD(alpha,beta)=1$.










share|cite|improve this question









$endgroup$












  • $begingroup$
    I meant that a and b are integers.
    $endgroup$
    – Oleksandr
    9 hours ago










  • $begingroup$
    For integers, it can have many values. What do you want to prove?
    $endgroup$
    – Dietrich Burde
    9 hours ago










  • $begingroup$
    I want to find the explicit formula for GCD of those two polynomials in terms of GCD of a and b.
    $endgroup$
    – Oleksandr
    8 hours ago














3












3








3


0



$begingroup$


I would appreciate some help finding $GCD(a^3-3ab^2, b^3-3ba^2)$; $a,b in mathbb{Z}$. So far I've got here: if $GCD(a,b)=d$ then $exists alpha, beta$ so that $GCD(alpha, beta)=1$ and $alpha d=a$, $beta d=b$.



Therefore we know that $GCD(a^3-3ab^2, b^3-3ba^2)=d^3 GCD(alpha^3-3alpha beta^2, beta^3-3beta alpha^2)$. However I don't know to figure out $GCD(alpha^3-3alpha beta^2, beta^3-3beta alpha^2)$ given that $GCD(alpha,beta)=1$.










share|cite|improve this question









$endgroup$




I would appreciate some help finding $GCD(a^3-3ab^2, b^3-3ba^2)$; $a,b in mathbb{Z}$. So far I've got here: if $GCD(a,b)=d$ then $exists alpha, beta$ so that $GCD(alpha, beta)=1$ and $alpha d=a$, $beta d=b$.



Therefore we know that $GCD(a^3-3ab^2, b^3-3ba^2)=d^3 GCD(alpha^3-3alpha beta^2, beta^3-3beta alpha^2)$. However I don't know to figure out $GCD(alpha^3-3alpha beta^2, beta^3-3beta alpha^2)$ given that $GCD(alpha,beta)=1$.







number-theory polynomials greatest-common-divisor






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked 10 hours ago









OleksandrOleksandr

644




644












  • $begingroup$
    I meant that a and b are integers.
    $endgroup$
    – Oleksandr
    9 hours ago










  • $begingroup$
    For integers, it can have many values. What do you want to prove?
    $endgroup$
    – Dietrich Burde
    9 hours ago










  • $begingroup$
    I want to find the explicit formula for GCD of those two polynomials in terms of GCD of a and b.
    $endgroup$
    – Oleksandr
    8 hours ago


















  • $begingroup$
    I meant that a and b are integers.
    $endgroup$
    – Oleksandr
    9 hours ago










  • $begingroup$
    For integers, it can have many values. What do you want to prove?
    $endgroup$
    – Dietrich Burde
    9 hours ago










  • $begingroup$
    I want to find the explicit formula for GCD of those two polynomials in terms of GCD of a and b.
    $endgroup$
    – Oleksandr
    8 hours ago
















$begingroup$
I meant that a and b are integers.
$endgroup$
– Oleksandr
9 hours ago




$begingroup$
I meant that a and b are integers.
$endgroup$
– Oleksandr
9 hours ago












$begingroup$
For integers, it can have many values. What do you want to prove?
$endgroup$
– Dietrich Burde
9 hours ago




$begingroup$
For integers, it can have many values. What do you want to prove?
$endgroup$
– Dietrich Burde
9 hours ago












$begingroup$
I want to find the explicit formula for GCD of those two polynomials in terms of GCD of a and b.
$endgroup$
– Oleksandr
8 hours ago




$begingroup$
I want to find the explicit formula for GCD of those two polynomials in terms of GCD of a and b.
$endgroup$
– Oleksandr
8 hours ago










2 Answers
2






active

oldest

votes


















4












$begingroup$

As you've already shown, factoring out the cube of the GCD of $a$ and $b$ gives a new equation



$$e = gcdleft(alpha^3-3alpha beta^2, beta^3-3beta alpha^2 right) tag{1}label{eq1}$$



where



$$gcdleft(alpha,beta right) = 1 tag{2}label{eq2}$$



Update: Here is a simpler solution than what I originally wrote. First, note that no factor of $e$ may divide $alpha$ or $beta$. If any do, let's say $alpha$, then it must divide $beta^3 - 3betaalpha^2$ and, thus, must divide $beta^3$, which is not possible due to eqref{eq2}. Thus, from the first term of eqref{eq1}, since $alpha^3-3alpha beta^2 = alphaleft(alpha^2 - 3beta^2right)$, this means that $e mid alpha^2 - 3beta^2$. Similarly, for the second term, $beta^3-3beta alpha^2 = betaleft(beta^2 - 3alpha^2right)$ gives that $e mid beta^2 - 3alpha^2$. Also, $e$ must divide any linear combination of these values, including $e | alpha^2 - 3beta^2 + 3left(beta^2 - 3alpha^2right) = -8alpha^2$. Thus, $e$ can only be a power of $2$. To finish this off, go to the second last paragraph. Otherwise, for the rest of the original, longer solution, continue reading.



$ $



Next, note that if $f = gcd(g,h)$, then $f$ divides $g$ and $h$ and, thus, will also divide any linear combination of $g$ and $h$, including their sum & difference. From eqref{eq1}, first check the sum of the $2$ inside values:



begin{align}
alpha^3-3alpha beta^2 + beta^3-3beta alpha^2 & = alpha^3 + beta^3 -3left(alpha betaright)beta - 3left(alpha betaright)alpha \
& = left(alpha + betaright)left(alpha^2 - alphabeta + beta^2right) - 3alphabetaleft(alpha + betaright) \
& = left(alpha + betaright)left(alpha^2 - 4alphabeta + beta^2right) tag{3}label{eq3}
end{align}



Suppose there's a factor $m gt 1$ which divides $e$ and $alpha + beta$. Then, $alpha equiv -beta pmod m$, so $alpha^3-3alpha beta^2 equiv 2beta^3 pmod m$. From eqref{eq2}, this means that $m = 2$, and that any other factors of $e$ must divide $alpha^2 - 4alphabeta + beta^2$.



From eqref{eq1}, next check the difference of the $2$ inside values:



begin{align}
alpha^3-3alpha beta^2 - beta^3 + 3beta alpha^2 & = alpha^3 - beta^3 -3left(alpha betaright)beta + 3left(alpha betaright)alpha \
& = left(alpha - betaright)left(alpha^2 + alphabeta + beta^2right) + 3alphabetaleft(alpha - betaright) \
& = left(alpha - betaright)left(alpha^2 + 4alphabeta + beta^2right) tag{4}label{eq4}
end{align}



Suppose there's a factor $n gt 1$ which divides $e$ and $alpha - beta$. Then, $alpha equiv beta pmod n$, so $alpha^3-3alpha beta^2 equiv -2beta^3 pmod m$. From eqref{eq2}, this means that $n = 2$, and that any other factors of $e$ must divide $alpha^2 + 4alphabeta + beta^2$.



This shows that any factor, other than $2$, which divides $e$ must divide both $alpha^2 - 4alphabeta + beta^2$ and $alpha^2 + 4alphabeta + beta^2$. Thus, it must also divide their difference, which is $8alphabeta$. This can only be true for $2$, $4$ or $8$.



At this shows overall, only powers of $2$ may possibly divide $e$. Since $e$ is relatively prime to $alpha$ & $beta$, this means they must both be odd. From $alpha^3 - 3alphabeta^2 = alphaleft(alpha^2 - 3beta^2right)$, note that $alpha^2 equiv beta^2 equiv 1 pmod 4$, so $alpha^2 - 3beta^2 equiv -2 pmod 4$. In other words, there will only be $1$ factor of $2$.



In summary, with your original equation of $d = gcdleft(a,bright)$, we get that $gcdleft(a^3-3ab^2, b^3-3ba^2right)$ is $2d^3$ if both $frac{a}{d}$ and $frac{b}{d}$ are odd, else it's $d^3$.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Wow, this is an outstanding explanation and it completely solves the problem. Thank you very much.
    $endgroup$
    – Oleksandr
    7 hours ago






  • 1




    $begingroup$
    @Oleksandr You are welcome. I had put in, removed (as I temporarily thought it was wrong) and now put back a shorter, simpler solution near the start of the answer. Sorry for any confusion my back & forth may have caused with this.
    $endgroup$
    – John Omielan
    6 hours ago





















2












$begingroup$

Note that $alpha^3 - 3 alpha beta^2$ and $3betaalpha^2 - beta^3$ are the real and imaginary parts respectively of $(alpha + i beta)^3$; this suggests that it will be useful to work in the ring of Gaussian integers $mathbb{Z}[i]$.



Now, suppose that for some integer prime $p$, $p mid alpha^3 - 3alpha beta^2$ and $pmid 3betaalpha^2 - beta^3$; then $p mid (alpha + i beta)^3$. If $p equiv 3 pmod{4}$, then $p$ remains irreducible in $mathbb{Z}[i]$, so $p mid alpha + i beta$, implying that $p mid gcd_{mathbb{Z}}(alpha, beta)$ which gives a contradiction. Similarly, if $p equiv 1 pmod{4}$, then the factorization of $p$ into irreducibles is of the form $p = (c + di) (c - di)$ for some $c, d in mathbb{Z}$. Thus, $c + di mid (alpha + i beta)^3$ implies $c + di mid alpha + ibeta$ and $c - di mid (alpha + ibeta)^3$ implies $c - di mid alpha + i beta$. Since $c + di$ and $c - di$ are relatively prime in $mathbb{Z}[i]$ (being irreducibles which do not differ by multiplication by a unit), this implies $(c + di) (c - di) mid alpha + i beta$; in other words, $p mid alpha + i beta$, again giving a contradiction.



The only remaining possibility is $p = 2$ which factors as $-i (1+i)^2$ in $mathbb{Z}[i]$. Now, by a similar argument to the above we have $(1 + i)^2 nmid alpha + beta i$, so the order of $1+i$ in $(alpha + beta i)^3$ is either 0 or 3. In the former case we get that $gcd(alpha^3 - 3alphabeta^2, 3betaalpha^2 - beta^3) = 1$, and in the latter case we get that $gcd(alpha^3 - 3alphabeta^2, 3betaalpha^2 - beta^3) = 2$.





Note that this solution is very closely tied to the exact form of the polynomials under consideration; whereas the general idea of John Omielan's answer should be more generally applicable to other cases.






share|cite|improve this answer









$endgroup$













    Your Answer





    StackExchange.ifUsing("editor", function () {
    return StackExchange.using("mathjaxEditing", function () {
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
    });
    });
    }, "mathjax-editing");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "69"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3156949%2fgcd-of-cubic-polynomials%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    2 Answers
    2






    active

    oldest

    votes








    2 Answers
    2






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    4












    $begingroup$

    As you've already shown, factoring out the cube of the GCD of $a$ and $b$ gives a new equation



    $$e = gcdleft(alpha^3-3alpha beta^2, beta^3-3beta alpha^2 right) tag{1}label{eq1}$$



    where



    $$gcdleft(alpha,beta right) = 1 tag{2}label{eq2}$$



    Update: Here is a simpler solution than what I originally wrote. First, note that no factor of $e$ may divide $alpha$ or $beta$. If any do, let's say $alpha$, then it must divide $beta^3 - 3betaalpha^2$ and, thus, must divide $beta^3$, which is not possible due to eqref{eq2}. Thus, from the first term of eqref{eq1}, since $alpha^3-3alpha beta^2 = alphaleft(alpha^2 - 3beta^2right)$, this means that $e mid alpha^2 - 3beta^2$. Similarly, for the second term, $beta^3-3beta alpha^2 = betaleft(beta^2 - 3alpha^2right)$ gives that $e mid beta^2 - 3alpha^2$. Also, $e$ must divide any linear combination of these values, including $e | alpha^2 - 3beta^2 + 3left(beta^2 - 3alpha^2right) = -8alpha^2$. Thus, $e$ can only be a power of $2$. To finish this off, go to the second last paragraph. Otherwise, for the rest of the original, longer solution, continue reading.



    $ $



    Next, note that if $f = gcd(g,h)$, then $f$ divides $g$ and $h$ and, thus, will also divide any linear combination of $g$ and $h$, including their sum & difference. From eqref{eq1}, first check the sum of the $2$ inside values:



    begin{align}
    alpha^3-3alpha beta^2 + beta^3-3beta alpha^2 & = alpha^3 + beta^3 -3left(alpha betaright)beta - 3left(alpha betaright)alpha \
    & = left(alpha + betaright)left(alpha^2 - alphabeta + beta^2right) - 3alphabetaleft(alpha + betaright) \
    & = left(alpha + betaright)left(alpha^2 - 4alphabeta + beta^2right) tag{3}label{eq3}
    end{align}



    Suppose there's a factor $m gt 1$ which divides $e$ and $alpha + beta$. Then, $alpha equiv -beta pmod m$, so $alpha^3-3alpha beta^2 equiv 2beta^3 pmod m$. From eqref{eq2}, this means that $m = 2$, and that any other factors of $e$ must divide $alpha^2 - 4alphabeta + beta^2$.



    From eqref{eq1}, next check the difference of the $2$ inside values:



    begin{align}
    alpha^3-3alpha beta^2 - beta^3 + 3beta alpha^2 & = alpha^3 - beta^3 -3left(alpha betaright)beta + 3left(alpha betaright)alpha \
    & = left(alpha - betaright)left(alpha^2 + alphabeta + beta^2right) + 3alphabetaleft(alpha - betaright) \
    & = left(alpha - betaright)left(alpha^2 + 4alphabeta + beta^2right) tag{4}label{eq4}
    end{align}



    Suppose there's a factor $n gt 1$ which divides $e$ and $alpha - beta$. Then, $alpha equiv beta pmod n$, so $alpha^3-3alpha beta^2 equiv -2beta^3 pmod m$. From eqref{eq2}, this means that $n = 2$, and that any other factors of $e$ must divide $alpha^2 + 4alphabeta + beta^2$.



    This shows that any factor, other than $2$, which divides $e$ must divide both $alpha^2 - 4alphabeta + beta^2$ and $alpha^2 + 4alphabeta + beta^2$. Thus, it must also divide their difference, which is $8alphabeta$. This can only be true for $2$, $4$ or $8$.



    At this shows overall, only powers of $2$ may possibly divide $e$. Since $e$ is relatively prime to $alpha$ & $beta$, this means they must both be odd. From $alpha^3 - 3alphabeta^2 = alphaleft(alpha^2 - 3beta^2right)$, note that $alpha^2 equiv beta^2 equiv 1 pmod 4$, so $alpha^2 - 3beta^2 equiv -2 pmod 4$. In other words, there will only be $1$ factor of $2$.



    In summary, with your original equation of $d = gcdleft(a,bright)$, we get that $gcdleft(a^3-3ab^2, b^3-3ba^2right)$ is $2d^3$ if both $frac{a}{d}$ and $frac{b}{d}$ are odd, else it's $d^3$.






    share|cite|improve this answer











    $endgroup$













    • $begingroup$
      Wow, this is an outstanding explanation and it completely solves the problem. Thank you very much.
      $endgroup$
      – Oleksandr
      7 hours ago






    • 1




      $begingroup$
      @Oleksandr You are welcome. I had put in, removed (as I temporarily thought it was wrong) and now put back a shorter, simpler solution near the start of the answer. Sorry for any confusion my back & forth may have caused with this.
      $endgroup$
      – John Omielan
      6 hours ago


















    4












    $begingroup$

    As you've already shown, factoring out the cube of the GCD of $a$ and $b$ gives a new equation



    $$e = gcdleft(alpha^3-3alpha beta^2, beta^3-3beta alpha^2 right) tag{1}label{eq1}$$



    where



    $$gcdleft(alpha,beta right) = 1 tag{2}label{eq2}$$



    Update: Here is a simpler solution than what I originally wrote. First, note that no factor of $e$ may divide $alpha$ or $beta$. If any do, let's say $alpha$, then it must divide $beta^3 - 3betaalpha^2$ and, thus, must divide $beta^3$, which is not possible due to eqref{eq2}. Thus, from the first term of eqref{eq1}, since $alpha^3-3alpha beta^2 = alphaleft(alpha^2 - 3beta^2right)$, this means that $e mid alpha^2 - 3beta^2$. Similarly, for the second term, $beta^3-3beta alpha^2 = betaleft(beta^2 - 3alpha^2right)$ gives that $e mid beta^2 - 3alpha^2$. Also, $e$ must divide any linear combination of these values, including $e | alpha^2 - 3beta^2 + 3left(beta^2 - 3alpha^2right) = -8alpha^2$. Thus, $e$ can only be a power of $2$. To finish this off, go to the second last paragraph. Otherwise, for the rest of the original, longer solution, continue reading.



    $ $



    Next, note that if $f = gcd(g,h)$, then $f$ divides $g$ and $h$ and, thus, will also divide any linear combination of $g$ and $h$, including their sum & difference. From eqref{eq1}, first check the sum of the $2$ inside values:



    begin{align}
    alpha^3-3alpha beta^2 + beta^3-3beta alpha^2 & = alpha^3 + beta^3 -3left(alpha betaright)beta - 3left(alpha betaright)alpha \
    & = left(alpha + betaright)left(alpha^2 - alphabeta + beta^2right) - 3alphabetaleft(alpha + betaright) \
    & = left(alpha + betaright)left(alpha^2 - 4alphabeta + beta^2right) tag{3}label{eq3}
    end{align}



    Suppose there's a factor $m gt 1$ which divides $e$ and $alpha + beta$. Then, $alpha equiv -beta pmod m$, so $alpha^3-3alpha beta^2 equiv 2beta^3 pmod m$. From eqref{eq2}, this means that $m = 2$, and that any other factors of $e$ must divide $alpha^2 - 4alphabeta + beta^2$.



    From eqref{eq1}, next check the difference of the $2$ inside values:



    begin{align}
    alpha^3-3alpha beta^2 - beta^3 + 3beta alpha^2 & = alpha^3 - beta^3 -3left(alpha betaright)beta + 3left(alpha betaright)alpha \
    & = left(alpha - betaright)left(alpha^2 + alphabeta + beta^2right) + 3alphabetaleft(alpha - betaright) \
    & = left(alpha - betaright)left(alpha^2 + 4alphabeta + beta^2right) tag{4}label{eq4}
    end{align}



    Suppose there's a factor $n gt 1$ which divides $e$ and $alpha - beta$. Then, $alpha equiv beta pmod n$, so $alpha^3-3alpha beta^2 equiv -2beta^3 pmod m$. From eqref{eq2}, this means that $n = 2$, and that any other factors of $e$ must divide $alpha^2 + 4alphabeta + beta^2$.



    This shows that any factor, other than $2$, which divides $e$ must divide both $alpha^2 - 4alphabeta + beta^2$ and $alpha^2 + 4alphabeta + beta^2$. Thus, it must also divide their difference, which is $8alphabeta$. This can only be true for $2$, $4$ or $8$.



    At this shows overall, only powers of $2$ may possibly divide $e$. Since $e$ is relatively prime to $alpha$ & $beta$, this means they must both be odd. From $alpha^3 - 3alphabeta^2 = alphaleft(alpha^2 - 3beta^2right)$, note that $alpha^2 equiv beta^2 equiv 1 pmod 4$, so $alpha^2 - 3beta^2 equiv -2 pmod 4$. In other words, there will only be $1$ factor of $2$.



    In summary, with your original equation of $d = gcdleft(a,bright)$, we get that $gcdleft(a^3-3ab^2, b^3-3ba^2right)$ is $2d^3$ if both $frac{a}{d}$ and $frac{b}{d}$ are odd, else it's $d^3$.






    share|cite|improve this answer











    $endgroup$













    • $begingroup$
      Wow, this is an outstanding explanation and it completely solves the problem. Thank you very much.
      $endgroup$
      – Oleksandr
      7 hours ago






    • 1




      $begingroup$
      @Oleksandr You are welcome. I had put in, removed (as I temporarily thought it was wrong) and now put back a shorter, simpler solution near the start of the answer. Sorry for any confusion my back & forth may have caused with this.
      $endgroup$
      – John Omielan
      6 hours ago
















    4












    4








    4





    $begingroup$

    As you've already shown, factoring out the cube of the GCD of $a$ and $b$ gives a new equation



    $$e = gcdleft(alpha^3-3alpha beta^2, beta^3-3beta alpha^2 right) tag{1}label{eq1}$$



    where



    $$gcdleft(alpha,beta right) = 1 tag{2}label{eq2}$$



    Update: Here is a simpler solution than what I originally wrote. First, note that no factor of $e$ may divide $alpha$ or $beta$. If any do, let's say $alpha$, then it must divide $beta^3 - 3betaalpha^2$ and, thus, must divide $beta^3$, which is not possible due to eqref{eq2}. Thus, from the first term of eqref{eq1}, since $alpha^3-3alpha beta^2 = alphaleft(alpha^2 - 3beta^2right)$, this means that $e mid alpha^2 - 3beta^2$. Similarly, for the second term, $beta^3-3beta alpha^2 = betaleft(beta^2 - 3alpha^2right)$ gives that $e mid beta^2 - 3alpha^2$. Also, $e$ must divide any linear combination of these values, including $e | alpha^2 - 3beta^2 + 3left(beta^2 - 3alpha^2right) = -8alpha^2$. Thus, $e$ can only be a power of $2$. To finish this off, go to the second last paragraph. Otherwise, for the rest of the original, longer solution, continue reading.



    $ $



    Next, note that if $f = gcd(g,h)$, then $f$ divides $g$ and $h$ and, thus, will also divide any linear combination of $g$ and $h$, including their sum & difference. From eqref{eq1}, first check the sum of the $2$ inside values:



    begin{align}
    alpha^3-3alpha beta^2 + beta^3-3beta alpha^2 & = alpha^3 + beta^3 -3left(alpha betaright)beta - 3left(alpha betaright)alpha \
    & = left(alpha + betaright)left(alpha^2 - alphabeta + beta^2right) - 3alphabetaleft(alpha + betaright) \
    & = left(alpha + betaright)left(alpha^2 - 4alphabeta + beta^2right) tag{3}label{eq3}
    end{align}



    Suppose there's a factor $m gt 1$ which divides $e$ and $alpha + beta$. Then, $alpha equiv -beta pmod m$, so $alpha^3-3alpha beta^2 equiv 2beta^3 pmod m$. From eqref{eq2}, this means that $m = 2$, and that any other factors of $e$ must divide $alpha^2 - 4alphabeta + beta^2$.



    From eqref{eq1}, next check the difference of the $2$ inside values:



    begin{align}
    alpha^3-3alpha beta^2 - beta^3 + 3beta alpha^2 & = alpha^3 - beta^3 -3left(alpha betaright)beta + 3left(alpha betaright)alpha \
    & = left(alpha - betaright)left(alpha^2 + alphabeta + beta^2right) + 3alphabetaleft(alpha - betaright) \
    & = left(alpha - betaright)left(alpha^2 + 4alphabeta + beta^2right) tag{4}label{eq4}
    end{align}



    Suppose there's a factor $n gt 1$ which divides $e$ and $alpha - beta$. Then, $alpha equiv beta pmod n$, so $alpha^3-3alpha beta^2 equiv -2beta^3 pmod m$. From eqref{eq2}, this means that $n = 2$, and that any other factors of $e$ must divide $alpha^2 + 4alphabeta + beta^2$.



    This shows that any factor, other than $2$, which divides $e$ must divide both $alpha^2 - 4alphabeta + beta^2$ and $alpha^2 + 4alphabeta + beta^2$. Thus, it must also divide their difference, which is $8alphabeta$. This can only be true for $2$, $4$ or $8$.



    At this shows overall, only powers of $2$ may possibly divide $e$. Since $e$ is relatively prime to $alpha$ & $beta$, this means they must both be odd. From $alpha^3 - 3alphabeta^2 = alphaleft(alpha^2 - 3beta^2right)$, note that $alpha^2 equiv beta^2 equiv 1 pmod 4$, so $alpha^2 - 3beta^2 equiv -2 pmod 4$. In other words, there will only be $1$ factor of $2$.



    In summary, with your original equation of $d = gcdleft(a,bright)$, we get that $gcdleft(a^3-3ab^2, b^3-3ba^2right)$ is $2d^3$ if both $frac{a}{d}$ and $frac{b}{d}$ are odd, else it's $d^3$.






    share|cite|improve this answer











    $endgroup$



    As you've already shown, factoring out the cube of the GCD of $a$ and $b$ gives a new equation



    $$e = gcdleft(alpha^3-3alpha beta^2, beta^3-3beta alpha^2 right) tag{1}label{eq1}$$



    where



    $$gcdleft(alpha,beta right) = 1 tag{2}label{eq2}$$



    Update: Here is a simpler solution than what I originally wrote. First, note that no factor of $e$ may divide $alpha$ or $beta$. If any do, let's say $alpha$, then it must divide $beta^3 - 3betaalpha^2$ and, thus, must divide $beta^3$, which is not possible due to eqref{eq2}. Thus, from the first term of eqref{eq1}, since $alpha^3-3alpha beta^2 = alphaleft(alpha^2 - 3beta^2right)$, this means that $e mid alpha^2 - 3beta^2$. Similarly, for the second term, $beta^3-3beta alpha^2 = betaleft(beta^2 - 3alpha^2right)$ gives that $e mid beta^2 - 3alpha^2$. Also, $e$ must divide any linear combination of these values, including $e | alpha^2 - 3beta^2 + 3left(beta^2 - 3alpha^2right) = -8alpha^2$. Thus, $e$ can only be a power of $2$. To finish this off, go to the second last paragraph. Otherwise, for the rest of the original, longer solution, continue reading.



    $ $



    Next, note that if $f = gcd(g,h)$, then $f$ divides $g$ and $h$ and, thus, will also divide any linear combination of $g$ and $h$, including their sum & difference. From eqref{eq1}, first check the sum of the $2$ inside values:



    begin{align}
    alpha^3-3alpha beta^2 + beta^3-3beta alpha^2 & = alpha^3 + beta^3 -3left(alpha betaright)beta - 3left(alpha betaright)alpha \
    & = left(alpha + betaright)left(alpha^2 - alphabeta + beta^2right) - 3alphabetaleft(alpha + betaright) \
    & = left(alpha + betaright)left(alpha^2 - 4alphabeta + beta^2right) tag{3}label{eq3}
    end{align}



    Suppose there's a factor $m gt 1$ which divides $e$ and $alpha + beta$. Then, $alpha equiv -beta pmod m$, so $alpha^3-3alpha beta^2 equiv 2beta^3 pmod m$. From eqref{eq2}, this means that $m = 2$, and that any other factors of $e$ must divide $alpha^2 - 4alphabeta + beta^2$.



    From eqref{eq1}, next check the difference of the $2$ inside values:



    begin{align}
    alpha^3-3alpha beta^2 - beta^3 + 3beta alpha^2 & = alpha^3 - beta^3 -3left(alpha betaright)beta + 3left(alpha betaright)alpha \
    & = left(alpha - betaright)left(alpha^2 + alphabeta + beta^2right) + 3alphabetaleft(alpha - betaright) \
    & = left(alpha - betaright)left(alpha^2 + 4alphabeta + beta^2right) tag{4}label{eq4}
    end{align}



    Suppose there's a factor $n gt 1$ which divides $e$ and $alpha - beta$. Then, $alpha equiv beta pmod n$, so $alpha^3-3alpha beta^2 equiv -2beta^3 pmod m$. From eqref{eq2}, this means that $n = 2$, and that any other factors of $e$ must divide $alpha^2 + 4alphabeta + beta^2$.



    This shows that any factor, other than $2$, which divides $e$ must divide both $alpha^2 - 4alphabeta + beta^2$ and $alpha^2 + 4alphabeta + beta^2$. Thus, it must also divide their difference, which is $8alphabeta$. This can only be true for $2$, $4$ or $8$.



    At this shows overall, only powers of $2$ may possibly divide $e$. Since $e$ is relatively prime to $alpha$ & $beta$, this means they must both be odd. From $alpha^3 - 3alphabeta^2 = alphaleft(alpha^2 - 3beta^2right)$, note that $alpha^2 equiv beta^2 equiv 1 pmod 4$, so $alpha^2 - 3beta^2 equiv -2 pmod 4$. In other words, there will only be $1$ factor of $2$.



    In summary, with your original equation of $d = gcdleft(a,bright)$, we get that $gcdleft(a^3-3ab^2, b^3-3ba^2right)$ is $2d^3$ if both $frac{a}{d}$ and $frac{b}{d}$ are odd, else it's $d^3$.







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited 6 hours ago

























    answered 7 hours ago









    John OmielanJohn Omielan

    4,1251215




    4,1251215












    • $begingroup$
      Wow, this is an outstanding explanation and it completely solves the problem. Thank you very much.
      $endgroup$
      – Oleksandr
      7 hours ago






    • 1




      $begingroup$
      @Oleksandr You are welcome. I had put in, removed (as I temporarily thought it was wrong) and now put back a shorter, simpler solution near the start of the answer. Sorry for any confusion my back & forth may have caused with this.
      $endgroup$
      – John Omielan
      6 hours ago




















    • $begingroup$
      Wow, this is an outstanding explanation and it completely solves the problem. Thank you very much.
      $endgroup$
      – Oleksandr
      7 hours ago






    • 1




      $begingroup$
      @Oleksandr You are welcome. I had put in, removed (as I temporarily thought it was wrong) and now put back a shorter, simpler solution near the start of the answer. Sorry for any confusion my back & forth may have caused with this.
      $endgroup$
      – John Omielan
      6 hours ago


















    $begingroup$
    Wow, this is an outstanding explanation and it completely solves the problem. Thank you very much.
    $endgroup$
    – Oleksandr
    7 hours ago




    $begingroup$
    Wow, this is an outstanding explanation and it completely solves the problem. Thank you very much.
    $endgroup$
    – Oleksandr
    7 hours ago




    1




    1




    $begingroup$
    @Oleksandr You are welcome. I had put in, removed (as I temporarily thought it was wrong) and now put back a shorter, simpler solution near the start of the answer. Sorry for any confusion my back & forth may have caused with this.
    $endgroup$
    – John Omielan
    6 hours ago






    $begingroup$
    @Oleksandr You are welcome. I had put in, removed (as I temporarily thought it was wrong) and now put back a shorter, simpler solution near the start of the answer. Sorry for any confusion my back & forth may have caused with this.
    $endgroup$
    – John Omielan
    6 hours ago













    2












    $begingroup$

    Note that $alpha^3 - 3 alpha beta^2$ and $3betaalpha^2 - beta^3$ are the real and imaginary parts respectively of $(alpha + i beta)^3$; this suggests that it will be useful to work in the ring of Gaussian integers $mathbb{Z}[i]$.



    Now, suppose that for some integer prime $p$, $p mid alpha^3 - 3alpha beta^2$ and $pmid 3betaalpha^2 - beta^3$; then $p mid (alpha + i beta)^3$. If $p equiv 3 pmod{4}$, then $p$ remains irreducible in $mathbb{Z}[i]$, so $p mid alpha + i beta$, implying that $p mid gcd_{mathbb{Z}}(alpha, beta)$ which gives a contradiction. Similarly, if $p equiv 1 pmod{4}$, then the factorization of $p$ into irreducibles is of the form $p = (c + di) (c - di)$ for some $c, d in mathbb{Z}$. Thus, $c + di mid (alpha + i beta)^3$ implies $c + di mid alpha + ibeta$ and $c - di mid (alpha + ibeta)^3$ implies $c - di mid alpha + i beta$. Since $c + di$ and $c - di$ are relatively prime in $mathbb{Z}[i]$ (being irreducibles which do not differ by multiplication by a unit), this implies $(c + di) (c - di) mid alpha + i beta$; in other words, $p mid alpha + i beta$, again giving a contradiction.



    The only remaining possibility is $p = 2$ which factors as $-i (1+i)^2$ in $mathbb{Z}[i]$. Now, by a similar argument to the above we have $(1 + i)^2 nmid alpha + beta i$, so the order of $1+i$ in $(alpha + beta i)^3$ is either 0 or 3. In the former case we get that $gcd(alpha^3 - 3alphabeta^2, 3betaalpha^2 - beta^3) = 1$, and in the latter case we get that $gcd(alpha^3 - 3alphabeta^2, 3betaalpha^2 - beta^3) = 2$.





    Note that this solution is very closely tied to the exact form of the polynomials under consideration; whereas the general idea of John Omielan's answer should be more generally applicable to other cases.






    share|cite|improve this answer









    $endgroup$


















      2












      $begingroup$

      Note that $alpha^3 - 3 alpha beta^2$ and $3betaalpha^2 - beta^3$ are the real and imaginary parts respectively of $(alpha + i beta)^3$; this suggests that it will be useful to work in the ring of Gaussian integers $mathbb{Z}[i]$.



      Now, suppose that for some integer prime $p$, $p mid alpha^3 - 3alpha beta^2$ and $pmid 3betaalpha^2 - beta^3$; then $p mid (alpha + i beta)^3$. If $p equiv 3 pmod{4}$, then $p$ remains irreducible in $mathbb{Z}[i]$, so $p mid alpha + i beta$, implying that $p mid gcd_{mathbb{Z}}(alpha, beta)$ which gives a contradiction. Similarly, if $p equiv 1 pmod{4}$, then the factorization of $p$ into irreducibles is of the form $p = (c + di) (c - di)$ for some $c, d in mathbb{Z}$. Thus, $c + di mid (alpha + i beta)^3$ implies $c + di mid alpha + ibeta$ and $c - di mid (alpha + ibeta)^3$ implies $c - di mid alpha + i beta$. Since $c + di$ and $c - di$ are relatively prime in $mathbb{Z}[i]$ (being irreducibles which do not differ by multiplication by a unit), this implies $(c + di) (c - di) mid alpha + i beta$; in other words, $p mid alpha + i beta$, again giving a contradiction.



      The only remaining possibility is $p = 2$ which factors as $-i (1+i)^2$ in $mathbb{Z}[i]$. Now, by a similar argument to the above we have $(1 + i)^2 nmid alpha + beta i$, so the order of $1+i$ in $(alpha + beta i)^3$ is either 0 or 3. In the former case we get that $gcd(alpha^3 - 3alphabeta^2, 3betaalpha^2 - beta^3) = 1$, and in the latter case we get that $gcd(alpha^3 - 3alphabeta^2, 3betaalpha^2 - beta^3) = 2$.





      Note that this solution is very closely tied to the exact form of the polynomials under consideration; whereas the general idea of John Omielan's answer should be more generally applicable to other cases.






      share|cite|improve this answer









      $endgroup$
















        2












        2








        2





        $begingroup$

        Note that $alpha^3 - 3 alpha beta^2$ and $3betaalpha^2 - beta^3$ are the real and imaginary parts respectively of $(alpha + i beta)^3$; this suggests that it will be useful to work in the ring of Gaussian integers $mathbb{Z}[i]$.



        Now, suppose that for some integer prime $p$, $p mid alpha^3 - 3alpha beta^2$ and $pmid 3betaalpha^2 - beta^3$; then $p mid (alpha + i beta)^3$. If $p equiv 3 pmod{4}$, then $p$ remains irreducible in $mathbb{Z}[i]$, so $p mid alpha + i beta$, implying that $p mid gcd_{mathbb{Z}}(alpha, beta)$ which gives a contradiction. Similarly, if $p equiv 1 pmod{4}$, then the factorization of $p$ into irreducibles is of the form $p = (c + di) (c - di)$ for some $c, d in mathbb{Z}$. Thus, $c + di mid (alpha + i beta)^3$ implies $c + di mid alpha + ibeta$ and $c - di mid (alpha + ibeta)^3$ implies $c - di mid alpha + i beta$. Since $c + di$ and $c - di$ are relatively prime in $mathbb{Z}[i]$ (being irreducibles which do not differ by multiplication by a unit), this implies $(c + di) (c - di) mid alpha + i beta$; in other words, $p mid alpha + i beta$, again giving a contradiction.



        The only remaining possibility is $p = 2$ which factors as $-i (1+i)^2$ in $mathbb{Z}[i]$. Now, by a similar argument to the above we have $(1 + i)^2 nmid alpha + beta i$, so the order of $1+i$ in $(alpha + beta i)^3$ is either 0 or 3. In the former case we get that $gcd(alpha^3 - 3alphabeta^2, 3betaalpha^2 - beta^3) = 1$, and in the latter case we get that $gcd(alpha^3 - 3alphabeta^2, 3betaalpha^2 - beta^3) = 2$.





        Note that this solution is very closely tied to the exact form of the polynomials under consideration; whereas the general idea of John Omielan's answer should be more generally applicable to other cases.






        share|cite|improve this answer









        $endgroup$



        Note that $alpha^3 - 3 alpha beta^2$ and $3betaalpha^2 - beta^3$ are the real and imaginary parts respectively of $(alpha + i beta)^3$; this suggests that it will be useful to work in the ring of Gaussian integers $mathbb{Z}[i]$.



        Now, suppose that for some integer prime $p$, $p mid alpha^3 - 3alpha beta^2$ and $pmid 3betaalpha^2 - beta^3$; then $p mid (alpha + i beta)^3$. If $p equiv 3 pmod{4}$, then $p$ remains irreducible in $mathbb{Z}[i]$, so $p mid alpha + i beta$, implying that $p mid gcd_{mathbb{Z}}(alpha, beta)$ which gives a contradiction. Similarly, if $p equiv 1 pmod{4}$, then the factorization of $p$ into irreducibles is of the form $p = (c + di) (c - di)$ for some $c, d in mathbb{Z}$. Thus, $c + di mid (alpha + i beta)^3$ implies $c + di mid alpha + ibeta$ and $c - di mid (alpha + ibeta)^3$ implies $c - di mid alpha + i beta$. Since $c + di$ and $c - di$ are relatively prime in $mathbb{Z}[i]$ (being irreducibles which do not differ by multiplication by a unit), this implies $(c + di) (c - di) mid alpha + i beta$; in other words, $p mid alpha + i beta$, again giving a contradiction.



        The only remaining possibility is $p = 2$ which factors as $-i (1+i)^2$ in $mathbb{Z}[i]$. Now, by a similar argument to the above we have $(1 + i)^2 nmid alpha + beta i$, so the order of $1+i$ in $(alpha + beta i)^3$ is either 0 or 3. In the former case we get that $gcd(alpha^3 - 3alphabeta^2, 3betaalpha^2 - beta^3) = 1$, and in the latter case we get that $gcd(alpha^3 - 3alphabeta^2, 3betaalpha^2 - beta^3) = 2$.





        Note that this solution is very closely tied to the exact form of the polynomials under consideration; whereas the general idea of John Omielan's answer should be more generally applicable to other cases.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered 6 hours ago









        Daniel ScheplerDaniel Schepler

        9,1841721




        9,1841721






























            draft saved

            draft discarded




















































            Thanks for contributing an answer to Mathematics Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3156949%2fgcd-of-cubic-polynomials%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            A CLEAN and SIMPLE way to add appendices to Table of Contents and bookmarks

            Calculate evaluation metrics using cross_val_predict sklearn

            Insert data from modal to MySQL (multiple modal on website)