$p\in\mathbb P\iff\Big(2\leq k<\sqrt p\implies\gcd(k^2,p-k^2)=1\Big ),\;p>3$

Question

This is sharper variant of

A condition for being a prime: $\;\forall m,n\in\mathbb Z^+\!:\,p=m+n\implies \gcd(m,n)=1$

It seems enough to test that for some sums: $p=m+n\implies\gcd(m,n)=1$, namely for the pairs $(k^2,p-k^2),\; 2\leq k < \sqrt p\;$.

Verified for $3<p<10000$.

---

Comment:

This algorithm can be used as a fancy integer factoring program, since $\gcd(k^2,p-k^2)=m>1\implies m|p$.

Answer 1

This is not enough. A counterexample is $p=9$. We must have $2\leq k < 3$, so $k=2$. For $k=2$ we have $k^2=4$ and $p-k^2=5$ and $\gcd(4,5)=1$.

However, when the last inequality is changed form a strict one into a non-strict one, it is true.

So we should have for all integers $2\leq k \color{red}{\leq} \sqrt p$ that $\gcd(k^2,p-k^2)=1$. Suppose that $p$ is not prime, then it has a divisior $l$ smaller than or equal to $\sqrt{p}$.

Then $l|l^2$ and $l\mid p-l^2$. Hence $\gcd(k^2,p-k^2)\geq l>1$. Contradiction. So $p$ is prime.

Answer 2

This is almost correct.

If $p$ is not prime, say $p=k\cdot m$ with $2\le k\le m$, then $2\le k\le\sqrt p$ and $k\mid \gcd(k^2,p-k^2)$.

Hence by contraposition:

If $p>1$ and $\gcd(k^2,p-k^2)=1$ for all $k$ with $2\le k\le\sqrt p$, then $p$ is prime.

Answer 3

Since $\ (k^2,p-k^2) = (k^2,p) = 1\iff (k,p) = 1,\,$ your criterion is equivalent to testing that $\,p\,$ is coprime to all $\,k\le \sqrt p,\ $ i.e. it is equivalent to the brute-force trial divisor factorization / primality algorithm that tests all integers below the square root of $\,p\,$ as possible factors.

Note that we need $\,k\le \sqrt p\ $ not $\, k < \sqrt p\ $ in order to find the prime factor $\,q\,$ of $\,q^2$.