I define a complex integer $z = a + b\cdot i$ (with $a, b \in \mathbb{Z}$) to be primitive if $gcd(a, b) = 1$ and $a$ and $b$ have opposite parity (i.e., one is odd and the other is even).
[These are precisely the pairs that generate primitive Pythagorean triples, and hence the name.]
I'm trying to find a condition to determine when the product of two complex integers $z = a + b\cdot i$ and $w = c + d\cdot i$ is also primitive.
The product $z\cdot w = (a + b\cdot i) \cdot (c + d\cdot i) = (a\cdot c - b\cdot d) + (a\cdot d + b \cdot c)\cdot i \equiv (e + f\cdot i) \equiv v$
Verifying that $e$ and $f$ have opposite parity is easy.
So far, I have been able to conclude that $gcd(e, f) \vert gcd(z\cdot \bar{z}, w \cdot \bar{w})$. My idea uses the fact that any integer linear combination of $e$ and $f$ is divisible by $\delta$, the $gcd$ of $e$ and $f$.
$a\cdot e + b\cdot f = c\cdot (a^2 + b^2)$, and
$-b\cdot e + a\cdot f = d\cdot (a^2 + b^2)$.
Now, since these are integer linear combinations of $e$ and $f$, $\delta \vert c\cdot (a^2 + b^2)$ and $\delta \vert d\cdot (a^2 + b^2)$. Since $w$ is a primitive complex integer and $gcd(c, d) = 1$, it can be concluded that $\delta \vert (a^2 + b^2)$. Similarly, one can show that $\delta \vert (c^2 + d^2)$. Therefore, $\delta \vert gcd(a^2 + b^2, c^2 + d^2)$.
However, I haven't been able to do much beyond this and haven't been able to determine exactly when $e$ and $f$ are co-prime (and $v$ is a primitive complex integer). Any help would be appreciated.
The Gaussian integers $\bf G$ are the set of all $a+bi$ where $a,b$ are integers and $i^2=-1$. Here are some facts that are well-known and discussed in many Number Theory textbooks, so I'll present them without proof.
$\bf G$ is an integral domain.
The units in $\bf G$ (that is, the elements of $\bf G$ whose multiplicative inverses are also in $\bf G$) are $\pm1$ and $\pm i$.
Prime numbers one less than a multiple of four (e.g., $3,7,11,19,23,31,\dots$) are also primes in $\bf G$.
The prime number $2$ factors in $\bf G$ as $2=(1+i)(1-i)$, and those factors are irreducible in $\bf G$. The two factors are associates, that is, either one is a unit times the other: $1+i=i(1-i)$.
Prime numbers one more than a multiple of four (e.g., $5,13,17,29,37,\dots$) can be expressed as a sum of two integer squares (e.g., $5=2^2+1^2$, $13=3^2+2^2$, $17=4^2+1^2$, and so on) and therefore factor in $\bf G$; $p=u^2+v^2=(u+vi)(u-vi)$. The factors are primes in $\bf G$. Moreover, they are not associates, so they are relatively prime to each other.
$\bf G$ is a unique factorization domain; every nonzero element of $\bf G$ has a factorization into primes, unique up to associates.
Now, let $z=a+bi$, $w=c+di$, $zw=e+fi$, and assume $zw$ is not primitive. The case where $e,f$ are of the same parity was settled in the body of the question, so we assume $\gcd(e,f)=r$ is odd and exceeds $1$. Then there is an odd prime $p$ dividing both $e$ and $f$, so $p$ divides $zw$.
If $p$ is one less than a multiple of four, then $p$ is still prime in $\bf G$, so $p$ divides at least one of $z,w$, so $z,w$ aren't both primitive.
We're left with the case that $p$ is one more than a multiple of four, in which case $p=(u+vi)(u-vi)$ for some integers $u,v$, and $u+vi,u-vi$ are both primes in $\bf G$. Since $p$ divides $zw$, it follows that both $u+vi$ and $u-vi$ divide $zw$, and then by primality $u+vi$ divides at least one of $z,w$, and also $u-vi$ divides at least one of $z,w$.
If $u+vi$ and $u-vi$ divide the same number, then, since they are relatively prime to each other, their product divides the number. But their product is the integer $p$, so the number can't be primitive. Hence, we may assume $u+vi$ divides $z$, and $u-vi$ divides $w$. Now $u-vi$ divides $w$ if and only if $u+vi$ divides $w'$ (since $(st)'=s't'$), so $\gcd(z,w')$ is divisible by $u+vi$ and, in particular, is not $1$.
Summing up, if $z,w$ are primitive, then $zw$ is primitive if and only if $\gcd(z,w')=1$.
In practice, if you want to determine whether $zw$ is primitive, you have a choice between
(a) calculating $zw=e+fi$ and then (if $e,f$ are of different parity) calculating $\gcd(e,f)$, or
(b) just calculating $\gcd(z,w')$, which can be done by the Euclidean algorithm in $\bf G$.
It's not clear to me which is easier.