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-3\alpha \beta^2, \beta^3-3\beta \alpha^2)$. However I don't know to figure out $GCD(\alpha^3-3\alpha \beta^2, \beta^3-3\beta \alpha^2)$ given that $GCD(\alpha,\beta)=1$.

$\endgroup$
  • $\begingroup$ I meant that a and b are integers. $\endgroup$ – Oleksandr Mar 21 at 16:31
  • $\begingroup$ For integers, it can have many values. What do you want to prove? $\endgroup$ – Dietrich Burde Mar 21 at 16:38
  • $\begingroup$ I want to find the explicit formula for GCD of those two polynomials in terms of GCD of a and b. $\endgroup$ – Oleksandr Mar 21 at 16:48
4
$\begingroup$

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

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

where

$$\gcd\left(\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 - 3\beta\alpha^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-3\alpha \beta^2 = \alpha\left(\alpha^2 - 3\beta^2\right)$, this means that $e \mid \alpha^2 - 3\beta^2$. Similarly, for the second term, $\beta^3-3\beta \alpha^2 = \beta\left(\beta^2 - 3\alpha^2\right)$ gives that $e \mid \beta^2 - 3\alpha^2$. Also, $e$ must divide any linear combination of these values, including $e | \alpha^2 - 3\beta^2 + 3\left(\beta^2 - 3\alpha^2\right) = -8\alpha^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-3\alpha \beta^2 + \beta^3-3\beta \alpha^2 & = \alpha^3 + \beta^3 -3\left(\alpha \beta\right)\beta - 3\left(\alpha \beta\right)\alpha \\ & = \left(\alpha + \beta\right)\left(\alpha^2 - \alpha\beta + \beta^2\right) - 3\alpha\beta\left(\alpha + \beta\right) \\ & = \left(\alpha + \beta\right)\left(\alpha^2 - 4\alpha\beta + \beta^2\right) \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-3\alpha \beta^2 \equiv 2\beta^3 \pmod m$. From \eqref{eq2}, this means that $m = 2$, and that any other factors of $e$ must divide $\alpha^2 - 4\alpha\beta + \beta^2$.

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

\begin{align} \alpha^3-3\alpha \beta^2 - \beta^3 + 3\beta \alpha^2 & = \alpha^3 - \beta^3 -3\left(\alpha \beta\right)\beta + 3\left(\alpha \beta\right)\alpha \\ & = \left(\alpha - \beta\right)\left(\alpha^2 + \alpha\beta + \beta^2\right) + 3\alpha\beta\left(\alpha - \beta\right) \\ & = \left(\alpha - \beta\right)\left(\alpha^2 + 4\alpha\beta + \beta^2\right) \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-3\alpha \beta^2 \equiv -2\beta^3 \pmod m$. From \eqref{eq2}, this means that $n = 2$, and that any other factors of $e$ must divide $\alpha^2 + 4\alpha\beta + \beta^2$.

This shows that any factor, other than $2$, which divides $e$ must divide both $\alpha^2 - 4\alpha\beta + \beta^2$ and $\alpha^2 + 4\alpha\beta + \beta^2$. Thus, it must also divide their difference, which is $8\alpha\beta$. 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 - 3\alpha\beta^2 = \alpha\left(\alpha^2 - 3\beta^2\right)$, note that $\alpha^2 \equiv \beta^2 \equiv 1 \pmod 4$, so $\alpha^2 - 3\beta^2 \equiv -2 \pmod 4$. In other words, there will only be $1$ factor of $2$.

In summary, with your original equation of $d = \gcd\left(a,b\right)$, we get that $\gcd\left(a^3-3ab^2, b^3-3ba^2\right)$ 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 Mar 21 at 18:28
  • 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 Mar 21 at 18:54
3
$\begingroup$

Note that $\alpha^3 - 3 \alpha \beta^2$ and $3\beta\alpha^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 - 3\alpha \beta^2$ and $p\mid 3\beta\alpha^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 + i\beta$ and $c - di \mid (\alpha + i\beta)^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 - 3\alpha\beta^2, 3\beta\alpha^2 - \beta^3) = 1$, and in the latter case we get that $\gcd(\alpha^3 - 3\alpha\beta^2, 3\beta\alpha^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$
1
$\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^2\equiv1\pmod8$

$m(m^2-3n^2)\equiv m(1-3)\equiv-2m\pmod8$

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$

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.