GCD of two numbers $4a^2 + 3,4ab-1$ I came across this problem while solving some contest math. Please help me out with this.
What are all the possible GCD for two numbers of the form $4a^2 + 3,4ab-1$?
 A: We show below that there are infinitely many primes which can divide the gcd.
We also characterize all of them.
Claim 1: If $p$ is any prime
$$p|gcd( 4a^2 + 3,4ab-1) .$$
then $p \neq 2,3$.
Proof $4a^2 + 3$ is odd hence $p \neq 2$.
Assume by contradiction that $p=3$. Then $3|4a^2 + 3 \Rightarrow 3|a \Rightarrow 3|4ab \Rightarrow 3 \nmid 4ab-1$.
Claim 2: If $p\neq 3$ any odd prime such that $-3$ is a quadratic residue modulo $p$, then there exists $a,b$ such that 
$$p|gcd( 4a^2 + 3,4ab-1) .$$
Note that Legendre symbol immediately tells you what the prime needs to be modulo 12.
Proof of claim 1.
The equation 
$$ 4a^2 + 3 \equiv 0 \pmod{p}$$
has solutions.
Pick one such $a$, and then the equation 
$$3b=-a \pmod{p}$$
has solutions. Pick such $b$.
Then 
$$4a^2\equiv -3 \pmod{p}$$
and 
$$12ab \equiv 4a (3b) \equiv -4a^2 \equiv 3 \pmod{p}$$
which yields 
$$4ab \equiv 1 \pmod{p}$$
Claim 3: If $p$ is any prime
$$p|gcd( 4a^2 + 3,4ab-1) .$$
then $-3$ is a quadratic residue $\pmod{p}$.
Proof
$$p |gcd( 4a^2 + 3,4ab-1)  \Rightarrow p|4a^2+3 \Rightarrow \\
-3=(2a)^2 \pmod{p}$$ 
Conclusion Let $p$ be a prime. Then there exists $a,b$ such that $p|gcd( 4a^2 + 3,4ab-1)$ if and only if $p \neq 2,3$ and 
$$ \left(\frac{-3}{p} \right)=1$$
if and only if $$p\equiv 1,7 \pmod{12}$$
