A more or less mechanical approach is to work modulo $4$. Note that for any integer $k$, $k^2\equiv 0 \pmod{4}$ or $k^2\equiv 1\pmod{4}$.
So, modulo $4$, $x^2-y^2$ can only take on the values $0$, $1$, and $-1$.
More basic, and more useful, is to suppose that $x^2-y^2=n$. Then $(x-y)(x+y)=n$. Note that for any integers $x$ and $y$, the numbers $x-y$ and $x+y$ are both even or both odd. (If we want a proof, their difference $2y$ is even.)
In neither case is $(x-y)(x+y)$ twice an odd integer. You started along these lines. Note that you were one step from the end.
Remark: The reason the second idea is more useful is that when it comes to solving $x^2-y^2=n$, we express $n$ as a product $st$ of integers of the same parity, and solve the system $x-y=s$, $x+y=t$. The solution is $x=\frac{s+t}{2}$, $y=\frac{s-t}{2}$. If $n$ is twice an odd integer, then this process breaks down, because one of $s$ and $t$ will be odd and the other even, so we do not get integers $x$ and $y$.
Well, it certainly depends on how you define things and how abstract you want to be but I guess I would come up with what I think is the easiest answer for me.
We define a relation on $\mathbb{Z}$: $a \equiv b \mod n \iff n \mid a-b$
If $a \equiv b \mod n$ then $\exists q \in \mathbb{Z}: nq = a-b$, but by the division algorithm we can write $b=nk+r$ such that $0 \leq r < n$. If we replace this instead of $b$ we'll have $a - (nk+r) = nq \implies a -r = nQ' \implies a \equiv r \mod n$
Therefore every integer number is congruent to some number $0\leq r<n$.
If $n=2$, then $r$ is either $0$ or $1$ provided that you take the standard order on integers for granted. However, it's easy to prove that there is no positive integer between $1$ and $0$. Because if there was an integer, say $m$, such that $0<m<1$, then the set $S=\{x \in \mathbb{Z}: 0<x<1\}$ would be a non-empty subset of natural numbers and hence it has a least element by the well-ordering principle. Let $m_0 = \min(S)$. But field axioms on reals implies that $0<m_0^2<m_0<1$, that means $m_0 ^2 < m_0 \in S$ and that's contradiction. But we have already assumed a well-defined order on integers (in fact on $\mathbb{R}$ and all of its subsets) which could be challenged depending on how you want to define an order on integers and how you build them. Hence, I have so far shown that there is no integer number between 1 and 0, I guess with shifting by $n$ one can prove that there is no integer number between $n$ and $n+1$. But anyway, the relation I have defined on $\mathbb{Z}$ can be proved to be an equivalence relation. Therefore, it partitions $\mathbb{Z}$ into disjoint non-empty subsets that are our equivalence classes. We call the equivalence class of $0$ as 'even' numbers and call the equivalence class $1$ as 'odd' numbers. Your statements now are obvious because our partitioned sets are disjoint (therefore a number can't be both even and odd) and their union is all of $\mathbb{Z}$ (any number must be either even or odd). This could be proved independently by using only the definitions of partitions and equivalence relations.
Now it's easily possible to prove that our partitioned set inherits a natural algebraic structure from $\mathbb{Z}$. I.e. $[a] + [b] = [a+b]$ and $[a].[b] = [a.b]$ where $[a]$ represents the class of all elements equivalent to $a$.
I guess it should be easy to prove by induction that if $s(n)$ is in the same equivalence class as $n$ then we'll have only equivalence class, therefore, to avoid that, $s(n)$ must fall in the other equivalence class because we have only two equivalence classes in $mod 2$.
I hope my arguments aren't that terrible and naive. I'm not a logician after all.
Best Answer
The equation being dealt with is
$$(a + bc)(b + ca) = 13^d \tag{1}\label{eq1A}$$
Since $a$, $b$, $c$ and $d$ are positive integers, then both $a + bc$ and $b + ca$ must be positive powers of $13$. Thus, have $a = 13^{e}(a')$ and $b = 13^{f}(b')$, where $a'$ and $b'$ have no factors of $13$. If $e \lt f$, then $a + bc = 13^{e}(a' + 13^{f-e}(b'))$, which is not a power of $13$. Similarly, $e \gt f$ also leads to a contradiction. Therefore, we have $e = f = m$, which gives
$$a = 13^m(a'), \; 13 \not\mid a', \; \; b = 13^m(b'), \; 13 \not\mid b' \tag{2}\label{eq2A}$$
Using this and dividing both sides of \eqref{eq1A} by $13^{2m}$ gives
$$(a' + b'c)(b' + a'c) = 13^{d'} \tag{3}\label{eq3A}$$
where $d' = d - 2m$ has the same parity as $d$. Next, since $a'$ and $b'$ are also positive integers, we get for some positive integers $s$ and $t$ that
$$a' + b'c = 13^s \tag{4}\label{eq4A}$$
$$b' + a'c = 13^t \tag{5}\label{eq5A}$$
with $s + t = d'$. Multiplying \eqref{eq4A} by $c$ and subtracting \eqref{eq5A} gives
$$\begin{equation}\begin{aligned} b'c^2 - b' & = 13^{s}c - 13^t \\ b'(c - 1)(c + 1) & = 13(13^{s-1}c - 13^{t-1}) \end{aligned}\end{equation}\tag{6}\label{eq6A}$$
Since $13 \not\mid b'$, then $c \equiv \pm 1 \pmod{13}$. If $c = 1$, then \eqref{eq4A} and \eqref{eq5A} results in $13^s = 13^t \implies s = t$, with this giving $d'$ and $d$ being even. Otherwise, using the $p$adic order function, if $\operatorname{ord}_{13}(c \mp 1) = k$, then $c = 13^{k}u \pm 1$ where $13 \not\mid u$. Substituting this into \eqref{eq4A} and \eqref{eq5A} gives
$$a' \pm b' + b'(13^{k}u) = 13^s \tag{7}\label{eq7A}$$
$$b' \pm a' + a'(13^{k}u) = 13^t \tag{8}\label{eq8A}$$
Next, note if $a' = b'$, then \eqref{eq7A} and \eqref{eq8A} results in $a' = b' = u = 1$ and $s = t = k$, so $d'$ and, thus $d$, are even. Otherwise, have
$$\operatorname{ord}_{13}(a' \pm b') = v \tag{9}\label{eq9A}$$
If $v \lt k$, then $\operatorname{ord}_{13}(a' \pm b' + b'(13^{k}u)) = \operatorname{ord}_{13}(b' \pm a' + a'(13^{k}u)) = v$, so $s = t = v$. Thus, $d' = 2v$ would be even, so $d$ would be even as well. If $v \gt k$, then $\operatorname{ord}_{13}(a' + b' + b'(13^{k}u)) = \operatorname{ord}_{13}(a' + b' + a'(13^{k}u)) = k$, so $s = t = k$ and, once again, we get that $d$ is even.
Thus, the only possibility where $d'$, and thus $d$, might possibly not be even is where $v = k$. Then \eqref{eq9A} gives, for some non-zero integer $w$ with $13 \not\mid w$, that
$$a' \pm b' = 13^k(w) \tag{10}\label{eq10A}$$
First, consider the case where it's $a' + b' \equiv 0 \pmod{13}$. Substituting \eqref{eq10A} into \eqref{eq7A} and \eqref{eq8A} gives
$$13^k(w + b'u) = 13^s \implies w + b'u = 13^{s-k} \tag{11}\label{eq11A}$$
$$13^k(w + a'u) = 13^t \implies w + a'u = 13^{t-k} \tag{12}\label{eq12A}$$
Note the powers of $13$ on the right side of \eqref{eq11A} and \eqref{eq12A} must both be positive. Thus, subtracting the $2$ equations gives
$$u(b' - a') \equiv 0 \pmod{13} \tag{13}\label{eq13A}$$
However, $13 \not\mid u$. Also, $b' + a' \equiv 0 \pmod{13}$ means $b' - a' \not\equiv 0 \pmod{13}$. Thus, \eqref{eq13A} can't be true.
With the second case of $a' - b' \equiv 0 \pmod{13}$, following similar steps will lead to $u(b' + a') \equiv 0 \pmod{13}$, with this giving another contradiction.
This means the assumption of $v = k$ can't be true. Thus, $s$ and $t$ must always be equal in \eqref{eq4A} and \eqref{eq5A}, leading to $d'$ and $d$ being even.
Note this proof only relies on $13$ being an odd prime, so any other odd prime in \eqref{eq1A} instead would also give the same result, i.e., that $d$ must be even.