GCD of two numbers $4a^2 + 3,4ab-1$

Question

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$?

Answer 1

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}$$