# GCD of cubic polynomials

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$$.

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

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$$.

• Wow, this is an outstanding explanation and it completely solves the problem. Thank you very much. – Oleksandr Mar 21 at 18:28
• @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. – John Omielan Mar 21 at 18:54

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.

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