Are complex conjugate gaussian integers always relatively prime? Trying to find general formulas for gcd of gaussian integers. I noticed that there seems to be a pattern where the factorization of 
$(a+bi)=(1+i)(\frac{a+b}{2} + \frac{b-a}{2}i)$ and 
$(b+ai)=(1+i)(\frac{a+b}{2} - \frac{b-a}{2}i)$ 
if a and b are relatively prime odd integers. 
My question is, will $(\frac{a+b}{2} + \frac{b-a}{2}i)$ and $(\frac{a+b}{2} - \frac{b-a}{2}i)$ always be relatively prime?
 A: Let $a,b$ be odd, relatively prime integers.

Claim: In $Z[i]$, the elements 
$$c + di\;\;\text{and}\;\;c - di$$
are relatively prime, where 
$$c = \frac{b+a}{2}\;\;\text{and}\;\;d=\frac{b-a}{2}$$
Note that any integer common factor of $c$ and $d$ would divide $c+d$ and $c-d$, hence would divide $a$ and $b$.

It follows that $\gcd(c,d) = 1$.

Also, since $a,b$ are odd, one of $c,d$ is odd, the other even, hence $c^2+d^2$ is odd.

Suppose that in $\mathbb{Z}[i]$, the element $s$ is a common factor of $c + di\;$and$\;c-di$.

The goal is to show that $s$ is a unit of $\mathbb{Z}[i]$.

In the steps below, the divisibility symbol means divisibility in $\mathbb{Z}$ provided the expressions on both sides of the symbol are necessarily integers; otherwise it means divisibility in $\mathbb{Z}[i]$.
\begin{align*}
\text{Then}\;\;&s \mid (c + di)\\[4pt]
\implies\;&|s|^2 \mid (c^2 + d^2)\\[4pt]
\implies\;&|s|^2\;\text{is odd}&&\text{[since $c^2 + d^2$ is odd]}\\[12pt]
\text{Also}\;\;&s \mid (c+di)\;\;\text{and}\;\;s \mid (c-di)\\[4pt]
\implies\;&s\mid \bigl((c+di) + (c-di)\bigr)\\[0pt]
&\;\;\text{and}\\[0pt]
&s\mid \bigl((c+di) - (c-di)\bigr)\\[4pt]
\implies\;&s \mid (2c)\;\;\text{and}\;\;s \mid (2di)\\[4pt]
\implies\;&|s|^2 \mid (4c^2)\;\;\text{and}\;\;|s|^2 \mid (4d^2)\\[4pt]
\implies\;&|s|^2 \mid c^2\;\;\text{and}\;\;|s|^2 \mid d^2&&\text{[since $|s|^2$ is odd]}\\[4pt]
\implies\;&|s|^2 = 1&&\text{[since $\gcd(c,d)=1$]}\\[4pt]
\end{align*}
so $s$ is a unit of $Z[i]$, as was to be shown.
A: A more algebraic number theoretic answer: Let us examine the prime factorizations of $(a + bi)$ and $(\overline{a + bi}) = (b + ai)$ in $\Bbb Z[i]$.
Set
$$
(a + bi) = \prod\mathfrak{p}^{e(\mathfrak{p})},
$$
to be the prime factorization of $a + bi$ (so the product runs over prime ideals $\mathfrak{p}$ of $\Bbb Z[i]$, and the $e(\mathfrak{p})$ are nonnegative integers with only finitely many not equal to $0$), then
$$
(\overline{a + bi}) = \prod\overline{\mathfrak{p}}^{e(\mathfrak{p})} = \prod\mathfrak{p}^{e(\overline{\mathfrak{p}})}.
$$
Say $\mathfrak{p}$ lies over an odd prime $p$ which is congruent to $3$ mod $4$ and $e(\mathfrak{p}) > 0$. Then $\mathfrak{p} = (p) = \overline{\mathfrak{p}}$, which means $p\mid a$ and $p\mid b$, contradicting the assumption that $(a,b) = 1$.
If $\mathfrak{p}$ lies over an odd prime which is congruent to $1$ mod $4$, then $\mathfrak{p}$ is not a rational prime and $\mathfrak{p}\overline{\mathfrak{p}} = (p)$. Complex conjugation exchanges $\mathfrak{p}$ with $\overline{\mathfrak{p}}$, so we need to show that at least one of $e(\mathfrak{p})$ and $e(\overline{\mathfrak{p}})$ is $0$. If both are strictly greater than $0$, then $\mathfrak{p}\overline{\mathfrak{p}} = (p)$ divides both $(a + bi)$ and $(\overline{a + bi})$, but this contradicts the fact that $a$ and $b$ were relatively prime.
So, so far we have shown that
$$
\prod_{\mathfrak{p}\mid (a + bi),\textrm{ }\mathfrak{p}\textrm{ lying over an odd rational prime}}\mathfrak{p}^{e(\mathfrak{p})} = (a + bi)\cdot (1 + i)^{-e(1 + i)}
$$
and
$$
\prod_{\mathfrak{p}\mid (\overline{a + bi}),\textrm{ }\mathfrak{p}\textrm{ lying over an odd rational prime}}\mathfrak{p}^{e(\overline{\mathfrak{p}})} = (\overline{a + bi})\cdot (1 + i)^{-e(1 + i)}
$$
are relatively prime, so that $(a + bi)$ and $(\overline{a + bi})$ share no prime factors dividing an odd rational prime. The last case to consider is when $\mathfrak{p}$ lies over $2$, which means $\mathfrak{p} = (1 + i)$. In this case, $\mathfrak{p} = \overline{\mathfrak{p}}$ again, but $\mathfrak{p}$ is not a rational prime. In this case, it is possible to have $e(\mathfrak{p}) = 1$ without contradiction. However, if $e(\mathfrak{p}) >1$, then $\mathfrak{p}^2 = (2)\mid (a + bi)$, meaning $2\mid a$ and $2\mid b$. This is again a contradiction, as $a$ and $b$ were assumed to be odd. So, $(1 + i)$ can occur at most once in the prime factorization of $(a + bi)$.
What we have shown is equivalent to what you wanted to show. But we can say more: $(1 + i)$ will occur in the prime factorization of $(a + bi)$ if and only if $(1 + i)$ occurs in the prime factorization of $(\overline{a + bi})$. Moreover, $(1 + i)$ must occur in the prime factorization of $(a + bi)$. We have
\begin{align*}
N(a + bi) &= N(\prod\mathfrak{p}^{e(\mathfrak{p})})\\
&= \prod N(\mathfrak{p})^{e(\mathfrak{p})},
\end{align*}
and each $N(\mathfrak{p})$ here is a prime in $\Bbb Z$. The left hand side is equal to $a^2 + b^2$, which is divisible by $2$, as $a$ and $b$ are both odd. This implies that $2$ must occur on the right hand side, and it can only show up as $N(1 + i)$, so that $(1 + i)$ must divide $(a + bi)$. Thus, we have proven the following:
Proposition: Let $a$ and $b$ be relatively prime odd integers. Then $(1 + i)$ divides $(a + bi)$ exactly once in $\Bbb Z[i]$, and if $\mathfrak{p} = (x + yi)$ is a prime of $\Bbb Z[i]$ lying over an odd rational prime $p$, $\mathfrak{p}$ divides $(a + bi)$ only if $p\equiv 1\pmod{4}$ and $\overline{\mathfrak{p}}$ does not divide $(a + bi)$.
