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!

  • $\begingroup$ what does $gcd(a:b)$ means? $\endgroup$ – Dr. Sonnhard Graubner Oct 5 '16 at 13:39
  • 1
    $\begingroup$ First, show that $a,b$ must be divisible by $6$. $\endgroup$ – Thomas Andrews Oct 5 '16 at 13:39
  • $\begingroup$ It's the greatest common divider... @Dr.SonnhardGraubner $\endgroup$ – jrs Oct 5 '16 at 13:39
  • $\begingroup$ Are $a,b$ known to be positive, or can they be negative? $\endgroup$ – Thomas Andrews Oct 5 '16 at 13:43
  • 1
    $\begingroup$ $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... $\endgroup$ – 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$.


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.