Find a solution to $x^2+y^2=65^2$ with $(x,y)=1$ Before this problem, I had to show that $65$ could be written as a sum of two squares. After this, I used ProofWiki to find solutions of the problem, which I got, for example, $65^2=(1+8^2)(4^2+7^2)=60^2+(-25)^2$. But $(60^2,25^2)\neq 1$. I used Bezout's identity, and can't find any connections to Euclidean Division.
 A: If you want, you could find all solutions then filter for the ones where $x$ and $y$ are relatively prime.
To do this, note that $x^2 + y^2 = 65^2$ is equivalent to:
$$(x+iy) (x-iy) = 65^2 = 5^2 \cdot 13^2 = (2+i)^2 (2-i)^2 (3+2i)^2 (3-2i)^2.$$
Therefore, by unique factorization in the Gaussian integers $\mathbb{Z}[i]$, we can conclude
$$x+iy = u (2+i)^a (2-i)^b (3+2i)^c (3-2i)^d,$$
where $u \in \{ \pm 1, \pm i \}$ is a unit, and $0 \le a, b, c, d \le 2$.  Now, the equation for $(x+iy) (x-iy)$ also implies that $a + b = 2$ and $c + d = 2$.  Therefore, there are 36 solutions $(x, y) \in \mathbb{Z}^2$ in all.
Also, note that for example if $a = b = 1$, then $5 \mid x + iy$ so $5 \mid x$ and $5 \mid y$, so these solutions can be excluded.  Similarly, solutions with $c = d = 1$ can be excluded.  This leaves just 16 possibilities to check (and many of them are related to each other by natural symmetries).
A: All Primitive Pythagorean Triples have the property that they can be written as
$$(m^2-n^2,2mn,m^2+n^2)$$
If you let $m=7,n=4$ you will get the triple
$$33^2+56^2=65^2$$ and they're coprime.
You could also let $m=8,n=1$ and you get the triple 
$$16^2+63^2=65^2$$
also coprime.
These are the only solutions, as there is no other way to write $65$ as $m^2+n^2.$
A: Let us solve the problem with the computer.
First of all the sage code, to have a clear image:
sage: K.<j> = QuadraticField(-1)
sage: N = 65^2
sage: K(N).factor()
(-3*j - 2)^2 * (-j - 2)^2 * (2*j + 1)^2 * (2*j + 3)^2
sage: AllSolutions = [ (x,y) for x in [1..N] for y in [1..N] if x^2+y^2 == N ]
sage: RelativelyPrimeSolutions = [ (x,y) for (x,y) in AllSolutions if gcd(x,y)==1 ]
sage: AllSolutions
[(16, 63),
 (25, 60),
 (33, 56),
 (39, 52),
 (52, 39),
 (56, 33),
 (60, 25),
 (63, 16)]
sage: RelativelyPrimeSolutions
[(16, 63), (33, 56), (56, 33), (63, 16)]

Now in words. Every decomposition of $N=65^2$ in the form $N=x^2+y^2$ is equivalent to one decomposition
$$ N =(x+iy)(x-y) $$
in the ring of gaussian integers 
$$ R = \Bbb Z[i] $$
which is the integers ring of the field $\Bbb Q(i)$. The arithmetic ring $R$ is a unique factorization domain, and the decomposition of $N$ is unique in this ring, explicitly it is:
$$
65^2 = N = (2+i)^2(2-i)^2\, (3+2i)^2(3-2i)^2\ .
$$
Now we "combine factors", taking some factors for $(x+iy)$, such that the same amount of conjugated factors remain for $(x-iy)$. We have many chances to do this. From the part with four prime factors $(2+i)^2(2-i)^2$ we may extact one of the following multiplicative pieces, always two "pieces" (i.e. prime factors):


*

*$s+it=(2+i)^2$, or

*$s+it=(2+i)(2-i)=5$, or

*$s+it=(2-i)^2$.


The same happens with the other factors, we can only combine:


*

*$u+iv=(3+2i)^2$, or

*$u+iv=(3+2i)(3-2i)=13$, or

*$u+iv=(3-2i)^2$.


Now we combine the chances, getting solutions 
$$x+iy = \text{unit}\cdot(s+it)(u+iv)$$
for the combined choices of the factors of $5^2$ and $13^2$.
The units are $1,i,-1,-i$. Multiplying with a unit means either changing "some" signs, or exchanging $x,y$ and changing "some" signs. We will search for solutions up to these simple operations.
Note that in case we already have $s+it=5\in \Bbb Z$ or $u+iv=13\in \Bbb Z$, the obtained solution is not relatively prime in $\Bbb Z$.
The remained four cases lead to the four solutions $\pm x\pm iy$, by isolating the real, respectively imaginary part in $R=\Bbb Z[i]$ from 
$$ (2\pm i)^2(3\pm2i)^2\ .$$
Then we pass from $\pm x$ to $|\pm x|$, if needed, same for the $y$ component. Here we have:
sage: for a in [ 2+j, 2-j ]:
....:     for b in [ 3+2*j, 3-2*j ]:
....:         print "(%s)^2(%s)^2 = %s" % ( a, b, a^2*b^2 )
....:         
(j + 2)^2(2*j + 3)^2 = 56*j - 33
(j + 2)^2(-2*j + 3)^2 = -16*j + 63
(-j + 2)^2(2*j + 3)^2 = 16*j + 63
(-j + 2)^2(-2*j + 3)^2 = -56*j - 33

Above we get only two "true solutions", $(56,33)$, and $(16,63)$ in natural numbers, after changing signs.
The other two solutions are obtained by exchanging the components. (Use the unit $i$... This and the $\pm$ adjustment comes from the existence of the units $\pm1, \pm i$ in the gaussian ring of integers $R=\Bbb Z[i]$.)
The solution was displayed, so that the structure is transparent, and 
the pattern is clear for the next time, when we have for instance $N=8125$...
A: $$x^2+y^2=65^2 \implies x \le 65$$
so you can put $x=1,2,3...64$ and try to find $y $ for each $x $.
a kind of disjunction of cases.
