If I am given two natural numbers, is there a way to determine if they could be the legs of a Pythagorean triple (right triangle with all sides having integer lengths)?
I know one can simply check if $a^2 + b^2$ is a perfect square (where $a$ and $b$ are the legs), but for my purposes this is much too inefficient (ie, computationally intensive).
Are there any methods that would eliminate some candidates, assuming the pair is randomly selected from a given range?
On
If one of the numbers is odd and greater than $1$, it $is$ a leg of a Pythagorean triple but we need to find if the other number is part of the one of the one-or-more triples that contain that odd number. If we solve $A$ for $n$, we can find one or more integer values of $n$ by trying all of the integer values of $m$ between the limits shown.
$$\mathbf{A=m^2-n^2\implies n=\sqrt{m^2-A}\qquad where \qquad \bigl \lceil\sqrt{A+1}\space\bigr\rceil \le m \le \biggl\lceil\frac{A}{2}\biggr\rceil}$$
The lower limit ensures $m^2>A$ and the upper limit ensures $m-n\ge 1$. Example: $$A=21\implies \lceil\sqrt{21+1}\space\rceil=5 \le m \le \biggl\lceil\frac{21}{2}\biggr\rceil =11\quad and \quad m\in\{5,11\}\implies n\in\{2,10\} $$
$$F(5,2)=(21,20,29)\qquad\qquad F(11,10)=(21,220,221)$$
The middle number(s) will tell you if your second (even) number is part of that triple but to find other triples with that number, we can do the same for side $B$.
$$\mathbf{B=2mn\implies n=\frac{B}{2m}\qquad where\qquad \bigl\lceil\sqrt{B}\space\bigr\rceil\le m \le \frac{B}{2}}$$ The lower limit ensures $m>n$ and the upper limit ensures $m-n\ge 1$. Example:
$$B=20\implies \lceil\sqrt{20}\rceil =5 \le m \le \frac{20}{2}=10\quad and \quad m\in \{5,10\}\implies n\in \{2,1\}$$
$$F(5,2)=(21,20,29)\qquad\qquad F(10,1)=(99,20,101)$$
One caveate: Euclid's formula does not generate all triples without a multiplier. If the numbers tested to not yield integers as shown, divide both by the GCD and try again. Then multiply the result, if found, by the GCD to obtain the final triple containing both original numbers.
In any case, there will be at most one triple containing both integers.
This method is almost certainly more trouble than checking whether $a^2+b^2$ is a square, but it does arrive at the answer without calculating or directly considering $c$, the hypotenuse. It is based on the fact that for any Pythagorean triangle, $a=u^2-v^2,\ b=2uv,\ c=u^2+v^2$ where one of $u,v$ is odd and the other is even.
Let's assume $\gcd (a,b)=d$. Find $r=\frac{a}{d}$ and $s=\frac{b}{d}$. If $a,b$ are legs of a Pythagorean triangle, then $r,s$ are legs of a primitive Pythagorean triangle. We know that one of the legs of a primitive Pythagorean triangle must be odd, and the other even.
WLOG, let $r$ be odd and $s$ be even and divisible by $4$. Now, find all divisors $m_i,n_j$ of $s$ such that $m_i$ are odd and $n_j$ are even, and pair them such that $m_i\cdot n_i=s$.
Now for each pair calculate $(m_i+\frac{n_i}{2})(|m_i-\frac{n_i}{2}|)$. If it so happens that for any pair $(m_i+\frac{n_i}{2})(|m_i-\frac{n_i}{2}|)=r$, then $r,s$ are the legs of a primitive Pythagorean triangle, and $a,b$ are the legs of a Pythagorean triangle.
Like I said, more trouble than the straight forward check on the sum of squares.