Hi, I've been thinking about this question for a couple of days and thought I'd join in. I've noticed that it seems to be the case that

(didn't realise enter would send) ... it seems to be the case that $gcd(3^n + 5^n, n^2 - 1)$ is 1 when $n$ is even and 8 when $n$ is odd. Proving this would show that $n = 3$ is the only solution, however I don't know if this fact is any easier to prove.

Welcome, @RossPure

I already showed that the greatest power of $2$ that can divide both $n^2-1$ and $3^n+5^n$ is $8$, but showing that it's the GCD seems more difficult.

Who added this room? Great idea.

@RossPure I'm sorry, but why does it imply $n=3$? I can only see it implies $n\equiv\pm3\pmod8$ or $n\equiv\pm1\pmod8$, but we can do it seeing the equation $\mod 8$.

@MatsGranvik originally, I created the room to discuss this question, but it can be easily extended to other questions on elementary number theory as well.

@Ian Mateus Because $a|b$ iff $gcd(a,b) = a$, so if the gcd is either 1 or 8 then we require that $n^2 - 1$ has to be equal to either 1 or 8, for which the only solution is $n = 3$.