If $a \equiv 9 \pmod {12}$, find all possible values for $\gcd(a^2+21a+72,252)$ 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$? 

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$
