# Find $\gcd(a,b)$ knowing that $(a^3+6b^2,6480)=216$ and $11a+8b \mid 540$

I'm stuck with this problem, it should be simple but I can't get far:

Let $a,b \in \Bbb Z$. Find $\gcd(a,b)$ knowing that $\gcd(a^3+6b^2,6480)=216$ and $11a+8b \mid 540$

From $(a^3+6b^2,6480)=216$ I know that $(\frac{a^3+6b^2}{216},30) = 1$. So $a^3+6b^2$ should have a maximun exponent of $2^3$ and $3^3$ times some other number. I'm not sure on how to combine the data that I have, I just need a hint because there's something that I'm missing or forgetting. Ideas? Thanks!

• what does $gcd(a:b)$ means? – Dr. Sonnhard Graubner Oct 5 '16 at 13:39
• First, show that $a,b$ must be divisible by $6$. – Thomas Andrews Oct 5 '16 at 13:39
• It's the greatest common divider... @Dr.SonnhardGraubner – jrs Oct 5 '16 at 13:39
• Are $a,b$ known to be positive, or can they be negative? – Thomas Andrews Oct 5 '16 at 13:43
• $a^3+6b^2$ is divisible by 216. Hence it is divisible at least by 6. But $6b^2$ is surely divisible by 6, hence so must be $a^3$, which means $a$ itself is divisible by 6, which means $a^3$ is... – Ivan Neretin Oct 5 '16 at 14:15

The question doesn't ask for $a$ and $b$, but for $\gcd(a,b)$. This turns out to be 6. As folks have pointed out, $a=6a_0$ and $b=6b_0$, giving us $\gcd(a_0^3+b_0^2, 30) = 1$ and $11a_0+8b_0 \mid 90.$ If $d=\gcd(a_0, b_0)$, so that $a_0=kd$ and $b_0=ld$, then this last equation is $\gcd(d^2(k^3d+l^2),30)=1$. Which is to say that $d$ has no common factors with 30. But the divisibility condition says $11kd+8ld \mid 90$, so $d$ must divide 90. The only positive integer dividing 90 but relatively prime to 30 is 1. So $\gcd(a,b) = 6.$

The statement that $\gcd(a^3+6b^2:6480)=216$ means that you know $a^3+6b^2$ is not divisible by $5$, is divisible by $2^3$ but not $2^4$ and $3^3$ but not $3^4$.

This means that $a$ is divisible by $6$, and hence so must $b$ be too, so $a=6a_0,b=6b_0$ and $a_0^3+b_0^2$ is relatively prime to $30,$ and $11a_0+8b_0\mid 90$.

The general solution to $11x+8y=D$ is $x=3D-8k, y=-4D+11K$. If $a_0=3D-8k,b_0=-4D+11k$ then \begin{align}a_0^3 +b_0^2 &= (3D-8k)^3+(-4D+11k)^2 \\ &= 27D^3-27\cdot 8D^2k+9\cdot 8^2Dk^2-8^3k^3 + 16D^2-8\cdot 11Dk+11^2k^2 \\ &= 27D^3-D^2(27\cdot 8k-16)+D(9\cdot 8^2k^2-8\cdot 11k) +(11^2k^2-8^3k^3)\end{align}

Modulo $2$, this is $D^3+k^2$, so $D,k$ must be opposite parity.

Modulo $3$, this is $D^2-Dk+k^2+k$, and you want $D,k$ so that this is not divisible by $3$.

Modulo $5$, this means that $2D^3-D^2(k-1)+D(k^2-3k)+(k^2-2k^3)$ is not divisible by $5$.

A lot of tedious enumeration work will go into this for each $D$.

Case $D=30$ or $D=90$

For example, if $D=30$ or $D=90$, then the above reduces to $k$ being odd, $k^2+k$ not divisible by $3$ (so $k\equiv1 \pmod 3)$ and $k^2-2k^3$ not divisible by $5$, so $k\equiv 1,2,4\pmod 5$.

This means that when $D=30$ or $D=90$ then $k\equiv 1,7,19\pmod{30}$ and $(a,b)=(6(3D-8k),6(-4D+11k))$ is a solution.

One example would be $D=30, k=7$ which gives $(a,b)=(204,-258)$.

Case $D=1$

If $D=1$, then $k$ must be even, $k^2+1$ is not divisible by $3$ (true for any $k$) and $2-(k-1)+(k^2-3k)+(k^2-2k^3) = 3+k+2k^2-2k^3$ must not be divisible by $5$, so $k\equiv 0,1,2,4\pmod{5}$.

So when $D=1$, $k\equiv 0,2,4,6\pmod{10}$, and $(a,b)=(6(3-8k),6(-4+11k))$. At $k=0$, this gives $(a,b)=(18,-24)$.

Other cases

It gets messier for other values of $D$. Not sure if there is a better way than just enumerating $D\mid 90$ and then working it out in each case. We've already done $D=1,30,90$. There are $9$ other possible $D$.