<s>[INST] 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
 [/INST] Here are a few necessary conditions on $n$ summarizing my statements from the chat:


*

*$n$ is odd. 

*any prime factor $p\mid n^2-1$ is of the form $p \equiv
    1,2,4,8 \mod 15$.

*$n \equiv 3,93 \mod 120$



proofs:
1)
It is clear that $3 \nmid 3^n+5^n$ and $5\nmid 3^n+5^n$. Thus $3\mid n$.
Write $n = 3m$, then $$3^n+5^n \equiv 0 \mod n^2-1 \\\Rightarrow (3^{-1}5)^n \equiv -1 \mod 9m^2-1.$$ Suppose $n$ is even. Then $-1$ is a square mod $9m^2-1$, so every odd prime factor $p$ of $9m^2-1$ is $p\equiv 1 \mod 4$. But $9m^2-1 \equiv 3 \mod 4$ as $n$ is even, a contradiction.
2)
The inverse of $3$ is $3^{-1} \equiv 3m^2 \mod 9m^2-1$, so from the identity shown above we get $$(15m^2)^n \equiv -1 \mod 9m^2-1. \\ \Rightarrow (-15) \equiv (15)^{-n+1}m^{-2n} \mod 9m^2-1$$
As $n$ is odd by 1.) we see that for any odd prime $p$ dividing $9m^2-1$ the Legendre-symbol $$1 = \left( \frac{-15}{p} \right) = \left( \frac{-1}{p} \right)\left( \frac{3}{p} \right)  \left( \frac{5}{p} \right) = \left( \frac{p}{3} \right)\left( \frac{p}{5} \right)$$
using the Quadratic Reciprocity Theorem. This shows $p \equiv 1,2,4,8 \mod 15$.
3) 
By 2) $n^2-1 \equiv 1,2,4,8 \mod 15$ because these residues form a multiplicative subgroup. We already know $3\mid n$ showing  $n\equiv 3 \mod 15$.
As $16 \nmid 3^n+5^n$, we know $8 \nmid n^2-1 =(n-1)(n+1)$ and 1) shows $n\equiv 3,5 \mod 8$. Chinese Remainder Theorem gives the result stated in 3).
</s>