How to prove the existence of a Pythagorean Triple without finding solutions?

Question

I am looking to prove that there is a Pythagorean Triple (x, y, 173) without finding solutions.

I know that a solution does exist ((52, 165, 173)), however I would like to prove this more generally (in order to apply it to other values).

The Pythagorean Triple is primitive since 173 is prime, and thus $\gcd(x, y, 173) = 1$, meaning that the solutions can be expressed as $x = u^2 - v^2, y = 2uv, z = u^2 + v^2$; however, I am not sure how to go further than this.

How can I complete the proof without solving?

Answer 1

One way to find the decomposition of $173$ fairly quickly is to observe that the two component squares must add up to a number er ending with $3$. But $0+3$ fails because no square ends in $3$, and various other attempts die for a similar reason except for $4+9$. So you know the even square in the decomposition must have a square root ending with $2$ or $8$, thus limiting trials.

If you can set up screenings based in quadratic residues in modular arithmetic (basically I used mod $5$ in my argument above), you can design a reasonably efficient method to get the required sum of squares for a given prime hypotenuse.

Answer 2

We begin with a slightly different representation of Euclid's formula that fits well with other versions not shown here. $\quad A=m^2-k^2 \quad B=2mk \quad C=m^2+k^2$

Matching side C using $F(m,k)\qquad C=(4x+1), x\subset\mathbb{N}$

Since $\,(m,k)\,$ must be integers, if we solve for $\,k\,$ and, if a defined finite test of $\,m$-values results in an integer, we know that a solution exists. If no $\,k$-integer is found, then no [primitive] Pythagorean triple exists.

$$C=m^2+k^2\implies k=\sqrt{C-m^2}\\ \text{for}\quad \bigg\lfloor\frac{ 1+\sqrt{2C-1}}{2}\bigg\rfloor \le m \le \big\lfloor\sqrt{C-1}\,\big\rfloor$$

The lower limit ensures $m>k$ and the upper limit ensures $k\in\mathbb{N}$.

\begin{equation}C=173\implies \bigg\lfloor\frac{ 1+\sqrt{346-1}}{2}\bigg\rfloor=9 \le m \le \big\lfloor\sqrt{173-1}\,\big\rfloor=13 \\ \text{and we find} \quad m\in\{13\}\implies k\in\{2\} \end{equation}

By inspection, we can see that $\,13^2+2^2=169+4=173$ which confirms that a solution exists for the other two components of a Pythagorean triple.

Given a valid hypotenuse $\,C,\,$ there will be $\,2^{n-1}\,$ primitive triple solutions where $\,n\,$ is the number of distinct prime factors of $\,C.\quad$ For example $\,173\,$ is prime so there is just $\,2^{(1-1)}=2^0=1\,$ primitive solution.