If $a \equiv 9 \pmod {12}$, find all possible values for $\gcd(a^2+21a+72,252)$

Question

We know that

$$a^2+21a+72 \equiv 9^2 + 21 \cdot 9 + 0 \equiv 6 \pmod {12}$$

So we know that that expression, let's say $\alpha$, is such that $12 \mid \alpha - 6$. But then $12 \mid 2(\alpha - 6)=2a+12$, which means that $\alpha$'s prime factorization contains $2$ as a factor (with multiplicity $1$) and 3 as a factor.

We know that $3$ has multiplicity $2$ because $72=2^3 \cdot 3^2$, $21a = 7 \cdot 3^2 \cdot k, a^2= 3^2k^2$. So $18$ is the lowest possible candidate to gcd. If $a^2 \equiv 5 \pmod 7$, we know that $126$ is the other candidate solution. Is there any way to check whether the system

$$a^2 \equiv 9 \pmod {12} \\ a^2 \equiv 5 \pmod 7$$

has no solution? If it does, does this mean that the gcd is $126$ unless $a^2 \not\equiv 5 \pmod 7$?

Answer 1

Write $a=12b+9$. Then $a^2+21a+72=18 (8 b^2 + 26 b + 19)$ and so $$\gcd(a^2+21a+72,252) = 18 \gcd(8 b^2 + 26 b + 19,14)$$ Since $8 b^2 + 26 b + 19$ is always odd, we have $$\gcd(8 b^2 + 26 b + 19,14) = \gcd(8 b^2 + 26 b + 19,7) = \gcd(b^2 -2b -2,7) = \gcd((b-1)^2 -3,7) = 1 $$ because $3$ is not a square mod $7$.

Therefore, $\gcd(a^2+21a+72,252) = 18$.

Answer 2

Note $\ (f,\,\overbrace{ 9\cdot 7\cdot 4}^{\large 252}) = (f,9)(f,7)(f,4) =\, 9\cdot \color{#c00}1\cdot\color{#0a0}2\ $ for $\ f = a^2+21a+72\ $ by

$3\mid a\ \Rightarrow\ 9\mid a^2+21a+72\ \Rightarrow\ (f,9) = \color{}9$

$\!(f,7)\, =\, (f\bmod 7,\,7)\, =\, (a^2\!+2,\,7) =\,\color{#c00} 1,\ $ by $\ x^2\not\equiv -2\pmod{\! 7}$

$\!(f,4) =\, \underbrace{(f(a),4)\, =\, (f(1)\bmod 4,\,4)}_{\large a\ \equiv\ 1\pmod{\!4}} = \color{#0a0}2,\ $ by $\ f\bmod 4\, =\, a^2+a$