<s>[INST] 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$? 
 [/INST] 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$.
</s>