Find all positive integers $n$ s.t. $3^n + 5^n$ is divisible by $n^2 - 1$

Solution 1:

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!

Solution 2:

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

Solution 3:

[update 3] Error for even $m$ which are not only perfect powers of $2$. Section $5$ is not sufficient to prove for such $m$, especially eqn. $(5.3)$ and $(5.8)$ must be completed for that cases, then this affects $(5.4)$ and $(5.10)$ and the general conclusion. I hope I can cure that problem, otherwise I'll retract my claim here soon*[/update 3]*

[update 2] I've added the consideration of the primefactor $2$ and can now defend the statement, that $n=3$ is the only solution. See section 6. [/update]

[update]: It seems to me that I've solved the problem nearly completely, while some yet unconsidered minor details might allow a small finite set of (perhaps trivial) solutions.
I consider the problem in terms of a number $m=n+1$, proceed from assuming $m$ as prime, as product of two, then of three primenumbers and see that the arguments extend easily to any squarefree number with the same result in each step, that there is no such $m$ and the final conclusion:

No solution for $m=n+1$ an odd squarefree number.

I consider then $m=p^a$ being a perfect prime power with the same result:

No solution for $m=n+1$ an odd perfect prime power with only a single prime.

I added a more comprehensive and -hopefully- full proof as section 5 below which replace sections 1 to 4. For redundancy and explanativity I'll leave that sections for the moment until someone could confirm that the proof is valid.
[/update]

I don't want however add my result to the common-wiki list unless someone has gone thru for a check against errors.

0: Useful notations/definitions
I introduce some notations first which I've explained in a couple of answers here in MSE and also in MO (I'll give the links later).

Let $ \{a,p\} = m $ denote the exponent $m$ to which the primefactor $p$ occurs in the number $a$
Let $ [ a : p] = 0 $ if $p$ does not divide $a$ and $ [ a : p] = 1 $ if it does (which is also known as Iverson brackets)
Let $f(n) = 5^n-3^n $ and $g(n)= f(2n)/f(n) = 5^n+3^n$ for shortness of notation
Let $\lambda$ denote the order of the cyclic subgroup modulo a prime $p$ such that $ \{f(\lambda_p),p\}\ge 1 $ with $\lambda$ minimal. We know, that $ \lambda$ is equal to or a divisor of $p-1$, such that also $ p=1 + \lambda_p \cdot \gamma_p$ with some $\gamma_p$
Let $\alpha$ denote the exponent, to which that primefactor p occurs at $f(\lambda)$ such that $\{ f( \lambda) , p \}=\alpha \ge 1$
Let's use indices like $\lambda_p$,$\alpha_q$ if multiple primefactors like $p,q$ are involved.

In general, we can now write the exponent of some primefactor $p$ of the primefactorization as $$ \{ f(n),p \} = [n : \lambda]( \alpha + \{n , p \} ) \tag 1$$ (for the primefactor $2$ we have a small modification but which will not bother here since in our argumentation that primefactor does not play an important role)

Finally let uns consider the given problem in terms of $m=n+1$ instead of $n$. Then $n^2-1 = m(m-2)$ and we ask for solutions of
$$ m(m-2) | 5^{m-1} + 3^{m-1}$$ or shorter $$ g(m-1) = k \cdot m (m-2) \qquad \qquad \text{ with some } k \gt 0$$ In the following I reduce the question to the simpler problem to show, that not even $m$ itself can be a factor of $g(m-1)$ which is then sufficient for the original question, whether $m(m-2) $ can be a factor of $g(m-1)$

1) Let's assume $m$ is a single odd prime.
Thus let's write $p$ for $m$ where $ p\in \mathbb P$ . Then also $p=1 + \lambda_p \cdot \gamma_p$ and $f(p-1)=f(\gamma \cdot \lambda) $ is divisible by $p$ by the above (because of Fermat's little theorem), or explicitely $$\{f(\lambda_p \cdot \gamma_p),p \} \ge 1 \qquad \qquad \text{ by definition of } \lambda_p$$

We can complete our question with the equality $$ g(p-1) = f(2(p-1))/f(p-1) = 5^{p-1} + 3^{p-1} $$ as $$ \begin{eqnarray} \{ g(p-1) , p \} &=& \{ f(2(p-1)) , p \} - \{f(p-1),p\} \\ &=& \; [2(p-1) : \lambda_p](\alpha_p + \{ 2(p-1) , p \}) \\ & & - [p-1 : \lambda_p](\alpha_p + \{p-1,p \}) \end{eqnarray} \tag {1.1} $$

We can then algebraically manipulate: the braces-expressions in the right parentheses can be omitted, since $p$ cannot be a factor of $p-1$ and so we can collect the rhs expressions: $$ \begin{eqnarray} \{ g(p-1) , p \} &=& [2(p-1) : \lambda_p](\alpha_p + 0) - [p-1 : \lambda_p](\alpha_p + 0) \\ &=& ([2(p-1) : \lambda_p] - [p-1 : \lambda_p])(\alpha_p + 0) \\ &=& ([2(\gamma_p \cdot \lambda_p ) : \lambda_p] - [\gamma_p \cdot \lambda_p : \lambda_p])\alpha_p \\ &=& ( 1 - 1) \alpha_p \\ &=& 0 \end{eqnarray} \tag {1.2} $$ which means, that the primefactor $p$ does not occur in $g(p-1)$ and so

$g(n)$ cannot be divisible by $n^2-1$ if $m=n+1$ is prime.

2) Now let's look at numbers $m$ which consist of $2$ primefactors like $m = p \cdot q$ .

In simple extension of the previous equation $(2)$ we get now two determinations: one for the exponent of the primefactor $p$ and one for that of the primefactor $q$ :
$$ \begin{eqnarray} \{ g(pq-1) , p \} &=& [2(pq-1) : \lambda_p](\alpha_p + \{2(pq-1),p \}) - [pq-1 : \lambda_p](\alpha_p + \{pq-1,p \}) \\ \{ g(pq-1) , q \} &=& [2(pq-1) : \lambda_q](\alpha_q + \{2(pq-1),q \}) - [pq-1 : \lambda_q](\alpha_q + \{pq-1,q \}) \end{eqnarray} \tag {2.1} $$ Again we can omit the braces in the most-righthand factors, because neither can $p$ divide $pq-1$ nor can $q$, so we have the reduced (and already collected) expressions $$ \begin{eqnarray} \{ g(pq-1) , p \} &=& ([2(pq-1) : \lambda_p] - [pq-1 : \lambda_p])\alpha_p \\ \{ g(pq-1) , q \} &=& ([2(pq-1) : \lambda_q] - [pq-1 : \lambda_q])\alpha_q \end{eqnarray} \tag {2.2} $$

We look at the first row for the primefactor $p$. We expand the term $$ \begin{eqnarray} pq-1 &=& (\gamma_p \lambda_p+1)(\gamma_q \lambda_q+1)-1 \\ &=& \gamma_p \lambda_p \gamma_q \lambda_q + \gamma_q \lambda_q+\gamma_p \lambda_p \end{eqnarray} $$ and get for the first Iverson-bracket the longer expression $$ [2(\gamma_p \lambda_p \gamma_q \lambda_q + \gamma_q \lambda_q+\gamma_p \lambda_p) : \lambda_p] $$ which can obviously (by cancelling of the $\lambda_p$ summands) be reduced to $$ [2( \gamma_q \lambda_q) : \lambda_p] $$ which, when similarly applied to the other Iverson brackets lead to the final equations $$ \begin{eqnarray} \{ g(pq-1) , p \} &=& ([2 \gamma_q \lambda_q : \lambda_p] - [ \gamma_q \lambda_q : \lambda_p])\alpha_p \\ \{ g(pq-1) , q \} &=& ([2 \gamma_p \lambda_p : \lambda_q] - [ \gamma_p \lambda_p : \lambda_q])\alpha_q \end{eqnarray} \tag {2.3} $$ Now we seem to arrive at a situation which alludes to an infinite descent - but it is simpler. In order that the parentheses do not evaluate to zero, the $\lambda$-values must divide in the first Iverson bracket but not in the second and thus must have exactly as many factors $2$ as are present in the numerator of the first Iverson bracket.
So let's rewrite

$ \lambda_p = 2^a l_p $ and $ \gamma_p = 2^A g_p $
$ \lambda_q = 2^b l_q $ and $ \gamma_q = 2^B g_q $

where $g_q,l_q,g_p,l_p$ are odd and all exponents are nonnegative.

Then by the above argument it must be that the exponents of the primefactor $2$ must match $a = 1+b+B $ in order that the whole parenthese does not vanish.
At the same time we must have that $ b = 1+a+A $ and thus $a = 1+1+a+A+B $ or $A+B=-2$
But since all exponents must be nonnegative we have a contradiction!
Thus we can conclude:

also $ m$ of the form $m=pq$ cannot satisfy the equation and thus for $n+1 = pq$ with $p,q$ odd primes allow no solution.

3) Considering $m$ as a number with 3 different primefactors shows now also a general key for disproving any squarefree number for $m$.

We assume $m=pqr$ and begin with the 3 equations $$ \begin{eqnarray} \{ g(pqr-1) , p \} &=& [2(pqr-1) : \lambda_p](\alpha_p + \{2(pqr-1),p \}) - [pqr-1 : \lambda_p](\alpha_p + \{pqr-1,p \}) \\ \{ g(pqr-1) , q \} &=& [2(pqr-1) : \lambda_q](\alpha_q + \{2(pqr-1),q \}) - [pqr-1 : \lambda_q](\alpha_q + \{pqr-1,q \}) \\ \{ g(pqr-1) , r \} &=& [2(pqr-1) : \lambda_r ](\alpha_r + \{2(pqr-1),r \}) - [pqr-1 : \lambda_r ](\alpha_r + \{pqr-1,r \}) \end{eqnarray} \tag {3.1} $$ Completely analoguous to the previous steps from (2.1) to (2.2) we can reduce the braces and collect items. $$ \begin{eqnarray} \{ g(pqr-1) , p \} &=& ([2(pqr-1) : \lambda_p] - [pqr-1 : \lambda_p])\alpha_p \\ \{ g(pqr-1) , q \} &=& ([2(pqr-1) : \lambda_q] - [pqr-1 : \lambda_q])\alpha_q \\ \{ g(pqr-1) , r \} &=& ([2(pqr-1) : \lambda_r] - [pqr-1 : \lambda_r])\alpha_r \end{eqnarray} \tag {3.2} $$ Only the expression for the iverson-brackets change in a significant way; but this shows also the way how this generalizes. We get $$pqr-1 = (\gamma_p \lambda_p+1)(\gamma_q \lambda_q+1)(\gamma_r \lambda_r+1)-1 $$ and get for the first iverson-bracket after cancelling by the "denominator" $$ [ (\gamma_q \lambda_q+1)(\gamma_r \lambda_r+1)-1 : \lambda_p $$ The full expansion of the parenthese becomes tidier now (and even more when more primefactors are involved), but we can easily step to the next equation, that of the exponents of 2.
We rewrite similar like in section 2
$$ \begin{eqnarray} \gamma_p &=& 2^a g_p &\qquad& \lambda_p &=& 2^A l_p \\ \gamma_q &=& 2^b g_q &\qquad& \lambda_q &=& 2^B l_q \\ \gamma_r &=& 2^c g_r &\qquad& \lambda_r &=& 2^C l_r \end{eqnarray} \tag {3.3} $$

where again all new indeterminates are odd and all exponents are nonnegative.
The equations for the exponents of the $2$'s contain now $\min()$-expressions, we get $$\begin{eqnarray} a &=& 1 + \min(b,c) + \min(B,C) \\ b &=& 1 + \min(c,a) + \min(C,B) \\ c &=& 1 + \min(a,b) + \min(A,B) \end{eqnarray} \tag {3.4} $$ It suffices now to assume one of the indeterminates $a,b,c$ to be the minimal one, say $c$ to arrive at the contradiction; because if we assume $c$ to be the minimum, and $b$ the next greater number, then the expression $1+\min(a,b)$ requires $c \gt b$ which is then a contradiction. Because this problem is symmetric for all indeterminates this derivation shows, that

that for no sqquarefree $m$ there is a solution possible.

The result in terms of $n$ is

There is no solution for $n = pqr... - 1$ where $pqr...$ means any squarefree number.

4) The final step must then be to generalize to repeated primefactors.
4.1) The case of $m=p^a$ is easily handled:

$$ \begin{eqnarray} \{ g(p^a-1) , p \} &=& \{ f(2(p^a-1)) , p \} - \{f(p^a-1),p\} \\ &=& \; [2(p^a-1) : \lambda_p](\alpha_p + \{ 2(p^a-1) , p \}) \\ & & - [p^a-1 : \lambda_p](\alpha_p + \{p^a-1,p \}) \\ \end{eqnarray} \tag {4.1}$$ It can immediately be reduced to
$$ \{ g(p^a-1) , p \} =( [2(p^a-1) : \lambda_p] - [p^a-1 : \lambda_p])\alpha_p \tag {4.2}$$ Now, $p^a-1$ factors into $(p-1)h(p)$ where $h(p)$ is an integer expression. Writing that factorization we find that $$ \{ g(p^a-1) , p \} =( [2(p-1)h(p) : \lambda_p] - [(p-1)h(p) : \lambda_p])\alpha_p \tag {4.3} $$ where it is obvious, that the parenthese in the rhs evaluates to zero $$ \{ g(p^a-1) , p \} =( 1 - 1 )\alpha_p $$ because $(p-1)$ is divisible by $\lambda_p$ due to the definitions/observations above in both Iverson-brackets.
That means:
- There is no solution for $m$ being a perfect power of a single primefactor.

4.2) The cases of arbitrarily composed odd $m$

I've not yet done the further generalization but I think it is the same arguing which leads to the complete result, that
- No odd $m$ of any composition allows a solution
(where perhaps some (possibly trivial) exceptions might be existent)

5) Generalization to repeated primefactors and full proof.
Here I rewrite the sections 1 to 4 in a more compact form and complete the proof for any $m$. The strategy is the same as before: I reduce the problem to the simpler question whether $ m | g(m-1) $ and then show by comparision of the primefactors of $m$ with that of $g(m-1)$ that at least one of the primefactors of $m$ does not occur in $g(m-1)$ and thus $m$ cannot be a factor of $g(m-1)$.
For the sake of conciseness I reduce the notation of $\lambda$ and $\alpha$ of a prime of some index $k$ - say $p_k$ to $\lambda_k$ resp. $\gamma_k$ instead of $\lambda_{p_k}$ and $\gamma_{p_k}$ as it would be required by their definition.

For a general squarefree $m$ and one primefactor $p_k$ of $m$ we get the equation in the most general form: $$ \begin{eqnarray} \{g(m-1) , p_k \} &=& \;\; [2(m-1):\lambda_k](\alpha_k + \{2(m-1),p_k \})\\ & & -[ (m-1):\lambda_k](\alpha_k + \{ (m-1),p_k \}) \end{eqnarray} \\ \tag {5.1}$$ for every primefactor $p_k$ of $m$.

First of all, if $p$ is a primefactor of $m$ it cannot be one of $m-1$, so the braces $\{2(m-1),p_k\}$ and $\{m-1,p_k\}$ evaluate to zero and can be omitted. Thus we have for all primefactors $p_k$:
$$ \{g(m-1) , {p_k}\} = ([2(m-1):\lambda_k]-[m-1:\lambda_k])\alpha_k \tag{5.2} $$ and in all these equations the parentheses must simultanuously evaluate to $1$ to allow $ m | g(m-1) $. We shall see, that at least one of those conditions can not be satisfied and thus $g(m-1)$ cannot be divisible by $m$.

Step 1: the general proof for numbers $m$ which are squarefree:
To handle the Iverson-brackets (which contain the symbol $\lambda$ for the order of cyclic subgroup) we expand the primefactors $p_k$ to show their components $$ p_k = 1+ \lambda_k \cdot \gamma_k $$ and rewrite that Iverson-bracket expanded as
$$ [2(m-1):\lambda_k] = \left[ 2 \left(\prod_{j=1..z}(1+ \lambda_j \cdot \gamma_j) - 1\right):\lambda_k \right]$$ where we use $z$ for the number of distinct primefactors.

For the $k$'th primefactor this reduces (by cancellation of the factor in the product, which contains $\lambda_k$ itself) to the two Iverson-brackets $$ \begin{eqnarray} 1. &\quad &[2(m-1):\lambda_k] &=& \left[2 \left(\prod_{j=1..z,j \ne k}(1+ \lambda_j \cdot \gamma_j \right) - 1) :\lambda_k\right] \\ 2. &\quad & [ (m-1):\lambda_k] &=& \left[ \prod_{j=1..z,j \ne k}(1+ \lambda_j \cdot\gamma_j) - 1:\lambda_k \right] \end{eqnarray} \tag{5.3} $$

In order to have this two Iverson-brackets different to get the parenthese nonzero, $ \lambda_k$ must contain exactly as many powers of $2$ as its "numerator" in the first of the two equations. Clearly, the number $w_k$ of primefactors $2$ in $\prod_{j=1..z,j \ne k}(1+ \lambda_j \cdot \gamma_j) $ $$ w_k = \{( \prod_{j=1..z,j \ne k} (1+ \lambda_j \cdot \gamma_j)) - 1 ,2\} \tag{5.4} $$ is equal or even bigger than the number of primefactors $2$ in each single value $\lambda_j$ $$ w_k \ge \min_{j=1..z,j \ne k} ( \{\lambda_j ,2\} ) \tag{5.5} $$ In order to have the Iverson-brackets evaluate to different values for some primefactor $p_k$ we must have that $$ w_k < \{\lambda_k , 2 \} = w_k+1 \tag{5.6} $$ This condition gives us now a contradiction.
If we assume $k$ such that $\lambda_k$ is the smallest of all $\lambda_j$ then we have that it must also be satisfied that $$ \{\lambda_k , 2 \} = w_k+1 \gt \min_{j=1..z,j \ne k}( \{\lambda_j \cdot \gamma_j , 2 \} ) \tag{5.7} $$ and thus is bigger than at least one of the other $\lambda_j$. But then it is no more the smallest one - hence: contradiction! So we have proven:

For every squarefree $m$ at least one of its primefactors cannot occur in $g(m-1)$ .

Step 2: the general proof for numbers $m$ of any composition:
The same occurs, if in (5.1) we allow repeated primefactors, such that we get exponents: $$ [2(m-1):\lambda_k] = \left[2 \left(\prod_{j=1..z,j \ne k} (1+ \lambda_j \cdot \gamma_j)^{a_j}\right) - 1:\lambda_k \right] \tag{5.8} $$ $$ [ (m-1):\lambda_k] = \left[ \left(\prod_{j=1..z,j \ne k} (1+ \lambda_j \cdot \gamma_j)^{a_j}\right) - 1:\lambda_k \right] \tag{5.9} $$ Because the introduced exponents $a_j$can only increase the number of primefactors $2$ in the numerators of the iverson brackets, the number of them in the $\lambda_k$ - values must also increase: $$ w_k = \{( \prod_{j=1..z,j \ne k} (1+ \lambda_j \cdot \gamma_j)^{a_j}) - 1 , 2\} \\ \ge \min_{j=1..z,j \ne k}( \{\lambda_j \cdot \gamma_j ,2\}a_j ) \tag{5.10} $$ but still the condition must be satisfied $$ w_k \lt \{\lambda_k , 2 \} = w_k+1 \tag{5.11} $$ because every $\lambda_k$ must contain more primefactors $2$ than the minimum in the others. But this is impossible because then we had no $\lambda_k$ with the smallest number of primefactors $2$.

This proves that the assumption of the existence of any $m$ which might satisfy the initial equation is false for any primefactor-composition of $m$, and so no such $m$ exists.
Consequently no $n$ with $n=m-1$ exists and we have proved the OP's assertion that there is no solution to the problem.

6. For the primefactor 2

The multiplicity of the primefactor $2$ in general $f(n)$ follows that equation:
$$ \{f(n),2 \} = 1 + 2*[n:2] + \{n,2\} \tag {6.1}$$ such that we have for $g(n)$ $$ \begin{eqnarray} \{g(n),2\} &=& \{f(2n),2\} - \{f(n),2\} \\ &=& (1 + 2 \cdot [2n:2] + \{2n,2\}) - ((1 + 2 \cdot [n:2] + \{n,2\})) \\ &=& 1 + 2 + 1+\{n,2\} - 1 - 2 \cdot [n:2] - \{n,2\} \\ &=& 1+ 2 \cdot (1-[n:2]) \\ \{g(m-1),2\} &=& 1+ 2 \cdot (1-[m-1:2]) \\ &=& 1+ 2 \cdot [m:2] \\ \end{eqnarray} \tag{6.2}$$ This means, for odd $m$ we have $ \{g(m-1),2 \} = 1 $ and for even $m$ with $m =2^a \cdot \mu $ we have $ \{g(m-1),2 \} = 3 $.

Thus for to have $ m | g(m-1) $ we can have $m=2^3 = 8$. But now the OP is more restrictive - it requires $ m(m-2) | g(m-1)$ and thus $m$ can only equal $m=2^2=4$ and $$m(m-2)=2^2 \cdot 2^1 = 2^3 | g(m-1) \tag {6.3}$$
Because in section 5 I proved that we cannot have an odd primefactor in $m$ this is the only solution and the only solution in terms of $n$ is

$n=3$ is the only solution for $ n^2-1 | g(n) $ .

Solution 4:

Not an answer, but a few considerations.

If $n+1$ is a prime then $3^{n}+5^n = 3^{p-1}+5^{p-1}\equiv 2\pmod{p}$ is not divisible by $n+1$. In a similar way if $n-1$ is a prime then $3^{n}+5^n = 3^{p+1}+5^{p+1}\equiv 34\pmod{p}$, so $p$ can be only $2$ or $17$.

Apart from specific-primes-hunting, one can also try to give a bound for the number of prime factors, or the greatest power of $2$ dividing $9m^2-1$ and $3^{3m}+5^{3m}$, hoping to get an inequality for any $m$ big enough. For istance, $\nu_2(3^n+5^n)$ is equal to $1$ when $n$ is even and is equal to $3$ when $n$ is odd. This gives $n\not\equiv\pm 1\pmod{8}$.

Moreover we have $n\not\equiv\pm 1\pmod{3}, n\not\equiv\pm 1\pmod{5}$. If $n\equiv\pm 1\pmod{p}$ for some $p>5$, we must have $$ 3^n + 5^n \equiv 0\pmod{p}, $$ so $$ \left(3\cdot 5^{-1}\right)^n \equiv -1 \pmod{p} $$ and the order of $3\cdot 5^{-1}\pmod{p}$ must be even, and an even divisor of $2n$. This gives the additional information that if $p\equiv -1\pmod{4}$ and $15$ is a square $\pmod{p}$, then $n\not\equiv\pm 1\pmod{p}$, so: $$ n\not\equiv \pm 1\pmod{3,5,7,8,11,43,59,67,71,103,119,127,\ldots} $$ and: $$ n\pm 1\neq p $$ for any odd prime number $p$. Very few $n$s survive to this sieve!

The first survival is $n=528=23^2-1$, however $17\mid(n^2-1)$ while $16\mid 528$, so $3^n+5^n\equiv 2\pmod{17}$.

The next survival is $n=900$. We have $n^2-1=17\cdot 29\cdot 31\cdot 53$, but since $n\equiv 4\pmod{16}$, we have $3^n+5^n\equiv 3^4+5^4\equiv 9\pmod{17}$.

The next survival is $n=1080$, for which $n^2-1=13\cdot 23\cdot 47\cdot 83$. However, since $12\mid n$, $3^n+5^n\equiv 2\pmod{13}$.

The next one is $n=1158$, for which $n^2-1=13\cdot 19\cdot 61\cdot 89$. Luckily, $13\mid 3^n+5^n$, but since $n\equiv 6\pmod{18}$, $3^n+5^n\equiv 3^6+5^6\equiv 14\pmod{19}$.

The next one is $n=1680$, for which $n^2-1=23\cdot 41^2\cdot 73$. $n\equiv 8\pmod{22}$ holds, and so $3^n+5^n\equiv -1\pmod{23}$. This is not a surprise, since $23\mid 3^n+5^n$ implies $11\mid n$.

Then comes $n=1818$, for which $n^2-1=17\cdot 23\cdot 79\cdot 107$. $11$ does not divide $n$, so $23$ cannot divide $3^n+5^n$.

We arrive at $n=1920$, for which $n^2-1=17\cdot 19\cdot 101\cdot 113$. Since $n$ is a multiple of sixteen, seventeen cannot divide $3^n+5^n$.

Going on, $n=1962$, $n^2-1= 13\cdot 37\cdot 53\cdot 151$. Twelve divides $n$, no way.

For the same reason, $n=2172,n=2508$ and $n=3132$ fall, too.

$n=2868$ falls because $19\mid n^2-1$ while $n\equiv 6\pmod{18}$.

It has become quite boring, but this considerations show that $n$ must be bigger than three thousand.

It is interesting to notice that if $n$ is even, $3^n+5^n$ is the sum of two coprime squares, so for every odd prime $p$ that divides $3^n+5^n$, $p\equiv 1\pmod{4}$. However, if $n$ is even $n^2-1\equiv -1\pmod{4}$, so there must be at least one prime divisor of $n^2-1$ that cannot belong to the set of prime divisors of $3^n+5^n$.

So we must have $n\equiv \pm 3\pmod{24}$, ruling out all the previous examples.

$n=3003$ almost survives to the new sieve. We have $n^2-1=2^3\cdot 19\cdot 79\cdot 751$, and $19\cdot79\mid 3^n+5^n$. However $n\equiv 3\pmod{750}$, and $3^3+5^3$ is too small to be divisible by $751$.

Another interesting phenomenon. In order to have $17\mid 3^n+5^n$, $n$ must be even, since the least $k$ such that $(3\cdot 5^{-1})^k\equiv -1\pmod{17}$ is $k=2$. Since $n$ is odd, we can introduce the sieve condition $n\not\equiv\pm 1\pmod{17}$. We can do this for every prime $p\equiv 1\pmod{4}$ for which the order of $(3\cdot 5^{-1})$ is a multiple of four.

Solution 5:

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:

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.

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$.

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).