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
 A: 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!
A: I'd better make this an answer. This was asked on MO long ago. Nobody could do it. Kevin Buzzard wrote to Andreescu and found out that the authors of the book don't know how to finish the problem. I put an answer summarizing what we had, in basic language. 
See
https://mathoverflow.net/questions/16341/on-polynomials-dividing-exponentials
A: 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).
A: EDIT: as pointed out in the comments, this is not correct. I'll leave the answer here for now in case someone finds a way to fix it.
By Fermat's little theorem, $a^n \equiv a \pmod{n}$, whenever $a$ and $n$ is coprime. Therefore
$$3^n + 5^n \equiv 8 \pmod{n+1}.$$
But this must be congruent to $0$ since $n^2-1=(n+1)(n-1)$ and therefore also $n+1$ should divide the expression and so 
$$8 \equiv 0 \pmod{n+1}.$$
This only happens when $n=1$, $n=3$ or $n=7$. One can check the $n=7$ case by hand but we can also use the congruence for $n-1 = 6$
$$3^7 + 5^7 \equiv 3 + 5 \equiv 2 \not \equiv 0 \pmod{6}.$$
A: This is not an answer.
So for far we know the following facts:


*

*The only $n\le 3\cdot 10^6$, for which this divisibility holds is $n=3$. (Tested numerically.)

*Clearly 3 and 5 do not divide $3^n+5^n$, and it is not hard to show that 7 and 11 also do not divide $3^n+5^n$.

*Hence if $n^2-1$ divides $3^n+5^n$, then 3,5,7,11 do not divide $n^2-1$. In particular, if  if $n^2-1$ divides $3^n+5^n$, then 3 divides $n$.
A: This seemed like a good starting point to examine the GMP C library in a little more detail, so I decided to write a quick program to print out numbers that fit this problem description. I'm not sure how much of an "answer" this is, but I thought the program might interest relevant parties.
Code below, link to a github gist here.
// This program is a quick brute force test of the question described at
// http://math.stackexchange.com/questions/612346/find-all-positive-integers-n-s-t-3n-5n-is-divisible-by-n2-1

// Copyright (C) 2014 Victor Robertson

// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>

size_t gLower = 1;
size_t gUpper = (0 - 1); // force underflow = size_t max
size_t i;

void sig_handler(int signo)
{
    printf("tested %zu to %zu\n", gLower, i - 1);
    exit(0);
}

int main(int argc, char* argv[]) {

    // all n s.t. 3^n+5^n is divisible by n^2−1

    if (signal(SIGINT, sig_handler) == SIG_ERR) {
        return 1;
    }

    // set args if provided
    if (argc > 1) {
        gLower = atol(argv[1]);
        if (argc > 2) {
            gUpper = atol(argv[2]);
        }
    }

    i = gLower;

    mpz_t i_sqr, three_n, five_n, res;

    mpz_init(i_sqr);
    mpz_init(three_n);
    mpz_init(five_n);
    mpz_init(res);

    // start by calculating 3^n and 5^n where n is the first number to test
    mpz_ui_pow_ui(three_n, 3, i);
    mpz_ui_pow_ui(five_n, 5, i);

    // 3 is a known solution, might as well skip straight to 5
    if (gLower < 5) {
        printf("3\n");
        gLower = 5;
    }

    // adjust the lower bound to exclude odds
    if (gLower % 2 == 0) {
        gLower -= 1;
    }

    for(i = gLower; i < gUpper; i += 2) {
        // I think this can be accomplished in a better, possibly more efficient means though I'm not positive.
        mpz_ui_pow_ui(i_sqr, i, 2);
        mpz_sub_ui(i_sqr, i_sqr, 1);

        mpz_add(res, three_n, five_n);

        if (mpz_divisible_p(res, i_sqr)) {
            printf("%zu\n",i);
        }

        // multiple the current 3^n and 5^n by 3 and 5 respectively to acquire 3^(n+1) and 5^(n+1)
        mpz_mul_ui(three_n, three_n, 3);
        mpz_mul_ui(five_n, five_n, 5);
    }

    printf("Done!\n");

    mpz_clear(i_sqr);
    mpz_clear(three_n);
    mpz_clear(five_n);
    mpz_clear(res);
}

A: Since $n$ is odd, we have $(3^n+5^n)\mid (3^{n^2}+5^{n^2})$ and thus $(n^2-1)\mid (3^{n^2}+5^{n^2})$. In other words, both $n$ and $n^2$ must belong to the set
$$S=\{ m\in\mathbb{N} : (m-1)\mid (3^m+5^m)\},$$
which is represented by the sequence http://oeis.org/A234535 in the OEIS.
It is therefore interesting to consider a (possibly simpler) question of finding all squares in $S$.
