Essentially, I am aware of the proof that if a primitive Pythagorean triple is of the form $x^2+y^2=z^2,$ then $x=q^2-p^2,$ $y=2pq$ and $z=p^2+q^2.$ But I'm not going to write this proof here.
My question was, does it follow that for any $p,q$ element of the integers, that one can follow this formula and find a primitive Pythagorean triple?
Or is it simply the case that, any primitive Pythagorean triple will have this form?
This is not homework related, so feel free to give me in depth proofs/explanations.
The short answer is: Yes, the formula you showed generates all primitive Pythagorean triples and all primitive triples will have this form.$\space\space$ (Primitives have $\space(q,p) \space$ of opposite parity and $\space GCD(q,p)=1.\quad$ It also generates trivial triples where one-or-more of $\space (x,y,z) \space$ is zero, and imprimitives where $\space GCD(x,y,z)>1.\quad$
Let's begin with this arbitrary expression of Euclid's formula: $ A=m^2-k^2,\quad B=2mk,\quad C=m^2+k^2.\quad$ We can see $$\space m=0\implies A<0\space\land\space B=0 \\ \veebar\\ k=0\implies\space A=C\space\land\space B=0$$ $$\\$$
$$m<0\space\veebar k<0\space\implies B<0$$ $$\\$$
$$GCD(m,k)>1 \implies GCD(A,B,C)>1$$
If we vary Euclid's formula slightly, we get \begin{align*} A&=(2n-1+k)^2-k^2\quad= &(2n-1)^2+& 2(2n-1)k \\ B&=2(2n-1+k)k \qquad\quad=& & 2(2n-1)k+ 2k^2\\ C&=(2n-1+k)^2+k^2 \quad =&(2n-1)^2+& 2(2n-1)k+ 2k^2 \end{align*} and this formula produces a non-trivial Pythagoreaan triple for ever pair of natural numbers $\space (n,k).\quad$ It produces about a third of the imprimitive triples as Euclid's formula but it does produce "some" because $\space GCD(A,B,C)=(2x-1)^2,\space x\in\mathbb{N}.\quad$ Note: $\space GCD(A,B,C)=(2(1)-1)^2=1\space$ includes all primitives.
We can see the $\space Sets\space$ of triples it produces in the table below. I actually developed the formula in 2009 by arranging hundreds of the smallest triple into this periodic-like table and noticing $\quad C-B=(2n-1)^2\space $ and $\quad A_{n+1} - A_n=2(2n-1).\quad$
$$\begin{array}{c|c|c|c|c|c|} Set_n & k=1 & k=2 & k=3 & k=4 &\cdots \\ \hline Set_1 & 3,4,5 & 5,12,13& 7,24,25& 9,40,41 &\cdots\\ \hline Set_2 & 15,8,17 & 21,20,29 &27,36,45 &33,56,65 &\cdots\\ \hline Set_3 & 35,12,37 & 45,28,53 &55,48,73 &65,72,97 &\cdots\\ \hline Set_{4} &63,16,65 &77,36,85 &91,60,109 &105,88,137 &\cdots\\ \hline \end{array}$$
We can see $\space C-B=(2n-1)^2\space$ and $\space n=1\implies C-B=1\implies$ all members of $\space Set_1\space$ are primitive. $\space\space$ If $\space (2n-1)\space$ is prime, then this variation will repeatedly "generate $(2n-1)-1$ primitives and skip an imprimitive."
\begin{align*} &A=(2n-1)^2+&2(2n-1)\bigg(k+\bigg\lfloor\frac{(k-1)}{(2n-2)}\bigg\rfloor\bigg)&\qquad\\ &B=&2(2n-1)\bigg(k+\bigg\lfloor\frac{(k-1)}{(2n-2)}\bigg\rfloor\bigg)&\qquad+2\bigg(k+\bigg\lfloor\frac{(k-1)}{(2n-2)}\bigg\rfloor\bigg)^2\\ &C=(2n-1)^2+&2(2n-1)\bigg(k+\bigg\lfloor\frac{(k-1)}{(2n-2)}\bigg\rfloor\bigg)&\qquad+2\bigg(k+\bigg\lfloor\frac{(k-1)}{(2n-2)}\bigg\rfloor\bigg)^2 \end{align*}
If $\space (2n-1)\space$ is composite, then $\space(A,B,C)\space$ is imprimitive when $\space GCD(n,k)>1.\quad$
Could this new formula be missing triples in the subset where $\space GCD(A,B,C)\space$ is and odd square? Let us assume that some other $A$-interval $(x)$ will include $A$-values in an extended version of the Table and reveal missing triples. If we derive $\space (B,\space C)\space$ from $\space A\space$ using the Pythagorean theorem, we get: $$A=(2n-1)^2+xk \quad\implies\\ B=xk+\frac{x^2k^2}{2(2n-1)^2 }\\ \land \\ C=(2n-1)^2+xk+\frac{x^2k^2}{2(2n-1)^2}$$
The $B$ and $C$ functions will not yield integers if $\space 2(2n-1)^2\not\mid x^2k^2\space$ for most values of $k$ so that $F(n,k)$ is not missing any triples (especially primitives) in the subset where $\space GCD(A,B,C)\space$ is an odd square –– and $F(n,k)$ is a subset of $F(m,k)$.
$\quad\therefore :\quad$All primitives are represented by both formulas.