If $\gcd(m,15)=\gcd(n,15)=1,$ show that $15\mid (m^4+n^4)$ or $15\mid (m^4-n^4)$.

Since $\gcd(m,5) = \gcd(n,5)=1$ we have by Fermat little theorem:

$$ m^4\equiv 1\equiv n^4 \pmod 5$$ so $5\mid m^4-n^4$.

On the other hand since $\gcd(m,3) = \gcd(n,3)=1$ we have again by Fermat little theorem:

$$ m^2\equiv 1\equiv n^2 \pmod 3$$ so $3\mid m^2-n^2$ and so $3\mid m^4-n^4$

Since none of the existing answers is built-up on OP's work, I posted another one.

OP has proved $15\mid m^8-n^8 = (m^4-n^4)(m^4+n^4)$.

Since $15$ is a composite number, to apply Euclid's Lemma, we have to do so in two steps (on prime number $3$ and $5$).

Note that (without Fermat's Little Theorem)

• $a^2 \equiv 0, 1 \pmod 3$, so $a^4 \equiv 0,1 \pmod 3$.
  • If $3 \mid m^4 + n^4$, it's easy to see that the only possibility is that $3 \mid m,n$, which contradicts $\gcd(m,15) = \gcd(n,15) = 1$
  • Use Euclid's Lemma to show that $3 \mid m^4 - n^4$
• $a^2 \equiv 0, 1, 4 \pmod 5$, so $a^4 \equiv 0,1 \pmod 5$, and $m^4 + n^4 \equiv 0,1,2 \pmod 5$.
  • If $5 \mid m^4 + n^4$, its again easy to see that the only possibility is $5 \mid m,n$, which contradicts $\gcd(m,15) = \gcd(n,15) = 1$
  • Use Euclid's Lemma to show that $5 \mid m^4 - n^4$

Since $\gcd(3,5) = 1$, $15 \mid m^4 - n^4$.