Find all positive integers $n$ s.t. $3^n + 5^n$ is divisible by $n^2 - 1$ 
As is the question in the title, I am wishing to find all positive integers $n$ such that $3^n + 5^n$ is divisible by $n^2 - 1$. 

I have so far shown both expressions are divisible by $8$ for odd $n\ge 3$ so trivially a solution is $n=3$. I'm not quite sure how to proceed now though. I have conjectured that the only solution is $n=3$ and have tried to prove it but have had little luck. Can anyone point me in the right direction? thanks

This is a community wiki answer to summarize the main results we've got for quick access. Feel free to edit and add more results. Theoretical achievements are here:
Result. $3\mid n$, by virtually everyone.
Result. $n\equiv 1\pmod 2$, and, thus, $n\equiv 3\pmod 6$, obtained by benh. See also the message on chat.
Result. if a prime $p$ divides $n^2-1$, then $p\equiv 2^k\pmod{15}$ for some $k$, obtained by benh.
Result. $n^2-1$ isn't divisible by $3, 5, 7, 11$. Obtained by Yiorgos S. Smyrlis.
Result. $n\equiv \pm 3\pmod 8$. Obtained by Tim Ratigan.
Result. combining the congruences, $n\equiv 3,  93 \pmod{120}$. See a proof here.
Result. Jack D'Aurizio was able to rule out $n\not\equiv \pm1\pmod p$ for every prime number $p>5$ for which $(3\cdot 5^{-1})$ has an odd order $\pmod{p}$ or an order divisible by $4$, see here. In combination with benh's result this gives that the smallest odd prime factor of $n^2-1$ is at least $19$. 

Numerical checkings are given and updated in this part.
Result. Listing was able to verify by brute force that $n=3 \lor n>10^{12}$, extending the result by Tapio Rajala that $n=3 \lor n>10^{11}$.
Add your own result or someone else's. Please give proper credit and don't post the proofs here; link them instead. For further discussion, e.g. disproving or strengthening any claim, use this chatroom.

This turned out to be a long standing open problem. Needless to say, breakthroughs in this question will be very well rewarded. I don't want this question to stop here, so I'll offer a +100 bounty very soon. Keep the good work up!
