GCD of cubic polynomials
$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$.
number-theory polynomials greatest-common-divisor
$endgroup$
add a comment |
$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$.
number-theory polynomials greatest-common-divisor
$endgroup$
$begingroup$
I meant that a and b are integers.
$endgroup$
– Oleksandr
yesterday
$begingroup$
For integers, it can have many values. What do you want to prove?
$endgroup$
– Dietrich Burde
yesterday
$begingroup$
I want to find the explicit formula for GCD of those two polynomials in terms of GCD of a and b.
$endgroup$
– Oleksandr
yesterday
add a comment |
$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$.
number-theory polynomials greatest-common-divisor
$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
number-theory polynomials greatest-common-divisor
asked yesterday
OleksandrOleksandr
644
644
$begingroup$
I meant that a and b are integers.
$endgroup$
– Oleksandr
yesterday
$begingroup$
For integers, it can have many values. What do you want to prove?
$endgroup$
– Dietrich Burde
yesterday
$begingroup$
I want to find the explicit formula for GCD of those two polynomials in terms of GCD of a and b.
$endgroup$
– Oleksandr
yesterday
add a comment |
$begingroup$
I meant that a and b are integers.
$endgroup$
– Oleksandr
yesterday
$begingroup$
For integers, it can have many values. What do you want to prove?
$endgroup$
– Dietrich Burde
yesterday
$begingroup$
I want to find the explicit formula for GCD of those two polynomials in terms of GCD of a and b.
$endgroup$
– Oleksandr
yesterday
$begingroup$
I meant that a and b are integers.
$endgroup$
– Oleksandr
yesterday
$begingroup$
I meant that a and b are integers.
$endgroup$
– Oleksandr
yesterday
$begingroup$
For integers, it can have many values. What do you want to prove?
$endgroup$
– Dietrich Burde
yesterday
$begingroup$
For integers, it can have many values. What do you want to prove?
$endgroup$
– Dietrich Burde
yesterday
$begingroup$
I want to find the explicit formula for GCD of those two polynomials in terms of GCD of a and b.
$endgroup$
– Oleksandr
yesterday
$begingroup$
I want to find the explicit formula for GCD of those two polynomials in terms of GCD of a and b.
$endgroup$
– Oleksandr
yesterday
add a comment |
3 Answers
3
active
oldest
votes
$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$.
$endgroup$
$begingroup$
Wow, this is an outstanding explanation and it completely solves the problem. Thank you very much.
$endgroup$
– Oleksandr
yesterday
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
yesterday
add a comment |
$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.
$endgroup$
add a comment |
$begingroup$
I'll write $alpha=m,beta=n$ for the ease of typing
If $d(ge1)$ divides $m^3-3mn^2,n^3-3m^2n$
$d$ will divide $n(m^3-3mn^2)+3m(n^3-3m^2n)=-8m^3n$
and $3n(m^3-3mn^2)+m(n^3-3m^2n)=-8mn^3$
Consequently, $d$ must divide $(-8m^3n,-8mn^3)=8mn(m^2,n^2)=8mn$
So, $d$ will divide $8$
As $(m,n)=1,$ both $m,n$ cannot be even
If $m$ is even, $n^3-3m^2n$ will be odd $implies d=1$
If both $m,n$ are odd,. $m^2,n^2equiv1pmod8$
$m(m^2-3n^2)equiv m(1-3)equiv-2mpmod8$
Similarly, we can establish the highest power of $2$ in $m^3-3mn^2$ will be $2$
$implies d=2$ if $m,n$ are odd
$endgroup$
add a comment |
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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$.
$endgroup$
$begingroup$
Wow, this is an outstanding explanation and it completely solves the problem. Thank you very much.
$endgroup$
– Oleksandr
yesterday
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
yesterday
add a comment |
$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$.
$endgroup$
$begingroup$
Wow, this is an outstanding explanation and it completely solves the problem. Thank you very much.
$endgroup$
– Oleksandr
yesterday
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
yesterday
add a comment |
$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$.
$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$.
edited yesterday
answered yesterday
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
yesterday
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
yesterday
add a comment |
$begingroup$
Wow, this is an outstanding explanation and it completely solves the problem. Thank you very much.
$endgroup$
– Oleksandr
yesterday
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
yesterday
$begingroup$
Wow, this is an outstanding explanation and it completely solves the problem. Thank you very much.
$endgroup$
– Oleksandr
yesterday
$begingroup$
Wow, this is an outstanding explanation and it completely solves the problem. Thank you very much.
$endgroup$
– Oleksandr
yesterday
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
yesterday
$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
yesterday
add a comment |
$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.
$endgroup$
add a comment |
$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.
$endgroup$
add a comment |
$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.
$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.
answered yesterday
Daniel ScheplerDaniel Schepler
9,2591821
9,2591821
add a comment |
add a comment |
$begingroup$
I'll write $alpha=m,beta=n$ for the ease of typing
If $d(ge1)$ divides $m^3-3mn^2,n^3-3m^2n$
$d$ will divide $n(m^3-3mn^2)+3m(n^3-3m^2n)=-8m^3n$
and $3n(m^3-3mn^2)+m(n^3-3m^2n)=-8mn^3$
Consequently, $d$ must divide $(-8m^3n,-8mn^3)=8mn(m^2,n^2)=8mn$
So, $d$ will divide $8$
As $(m,n)=1,$ both $m,n$ cannot be even
If $m$ is even, $n^3-3m^2n$ will be odd $implies d=1$
If both $m,n$ are odd,. $m^2,n^2equiv1pmod8$
$m(m^2-3n^2)equiv m(1-3)equiv-2mpmod8$
Similarly, we can establish the highest power of $2$ in $m^3-3mn^2$ will be $2$
$implies d=2$ if $m,n$ are odd
$endgroup$
add a comment |
$begingroup$
I'll write $alpha=m,beta=n$ for the ease of typing
If $d(ge1)$ divides $m^3-3mn^2,n^3-3m^2n$
$d$ will divide $n(m^3-3mn^2)+3m(n^3-3m^2n)=-8m^3n$
and $3n(m^3-3mn^2)+m(n^3-3m^2n)=-8mn^3$
Consequently, $d$ must divide $(-8m^3n,-8mn^3)=8mn(m^2,n^2)=8mn$
So, $d$ will divide $8$
As $(m,n)=1,$ both $m,n$ cannot be even
If $m$ is even, $n^3-3m^2n$ will be odd $implies d=1$
If both $m,n$ are odd,. $m^2,n^2equiv1pmod8$
$m(m^2-3n^2)equiv m(1-3)equiv-2mpmod8$
Similarly, we can establish the highest power of $2$ in $m^3-3mn^2$ will be $2$
$implies d=2$ if $m,n$ are odd
$endgroup$
add a comment |
$begingroup$
I'll write $alpha=m,beta=n$ for the ease of typing
If $d(ge1)$ divides $m^3-3mn^2,n^3-3m^2n$
$d$ will divide $n(m^3-3mn^2)+3m(n^3-3m^2n)=-8m^3n$
and $3n(m^3-3mn^2)+m(n^3-3m^2n)=-8mn^3$
Consequently, $d$ must divide $(-8m^3n,-8mn^3)=8mn(m^2,n^2)=8mn$
So, $d$ will divide $8$
As $(m,n)=1,$ both $m,n$ cannot be even
If $m$ is even, $n^3-3m^2n$ will be odd $implies d=1$
If both $m,n$ are odd,. $m^2,n^2equiv1pmod8$
$m(m^2-3n^2)equiv m(1-3)equiv-2mpmod8$
Similarly, we can establish the highest power of $2$ in $m^3-3mn^2$ will be $2$
$implies d=2$ if $m,n$ are odd
$endgroup$
I'll write $alpha=m,beta=n$ for the ease of typing
If $d(ge1)$ divides $m^3-3mn^2,n^3-3m^2n$
$d$ will divide $n(m^3-3mn^2)+3m(n^3-3m^2n)=-8m^3n$
and $3n(m^3-3mn^2)+m(n^3-3m^2n)=-8mn^3$
Consequently, $d$ must divide $(-8m^3n,-8mn^3)=8mn(m^2,n^2)=8mn$
So, $d$ will divide $8$
As $(m,n)=1,$ both $m,n$ cannot be even
If $m$ is even, $n^3-3m^2n$ will be odd $implies d=1$
If both $m,n$ are odd,. $m^2,n^2equiv1pmod8$
$m(m^2-3n^2)equiv m(1-3)equiv-2mpmod8$
Similarly, we can establish the highest power of $2$ in $m^3-3mn^2$ will be $2$
$implies d=2$ if $m,n$ are odd
answered 21 hours ago
lab bhattacharjeelab bhattacharjee
227k15158276
227k15158276
add a comment |
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
$begingroup$
I meant that a and b are integers.
$endgroup$
– Oleksandr
yesterday
$begingroup$
For integers, it can have many values. What do you want to prove?
$endgroup$
– Dietrich Burde
yesterday
$begingroup$
I want to find the explicit formula for GCD of those two polynomials in terms of GCD of a and b.
$endgroup$
– Oleksandr
yesterday