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?
Best Answer
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.