Here are the first $40$ integers for which $\dfrac{3^n+1}{n+1}$ is an integer. I've denoted their residue mod $72$ by color and a symbol. $$\begin{array}{r}\dagger\,\color{violet}0,&\bullet\,\color{brown}1,&*\,\color{red}3,&27,&531,\\ 1\,035,&4\,635,&6\,363,&11\,475,&19\,683,\\ 4\,131,&80\,955,&*\,\color{red}{266\,475},&280\,755,&307\,395,\\ 356\,643,&\circ\,\color{blue}{490\,371},&544\,347,&557\,955,&565\,515,\\ 572\,715,&808\,227,&1\,256\,355,&1\,695\,483,&1\,959\,075,\\ 1\,995\,075,&2\,771\,595,&2\,837\,835,&3\,004\,155,&3\,208\,491,\\ *\,\color{red}{3\,337\,635},&3\,886\,443,&4\,670\,955,&5\,619\,411,&6\,434\,595,\\ \bullet\,\color{brown}{6\,942\,817},&*\,\color{red}{7\,631\,715},&*\,\color{red}{9\,274\,755},&9\,436\,923,&9\,586\,107,\end{array}$$ $\dagger\,\color{violet}{\rm Violet}$ means $0$ mod $72$, $\circ\,\color{blue}{\rm blue}$ means $51$ mod $72$, $\bullet\,\color{brown}{\rm brown}$ means $1$ mod $72$, $*\,\color{red}{\rm red}$ means $3$ mod $72$. All the rest, ${\rm black}$, are $27$ mod $72$.
Why are so many solutions ($31$ of the first $40$) equivalent to $27$ mod $72$? It can't be a coincidence that (beyond $n=3$) the counterexamples are so few and take so long to show up.
Some other observations. Of the first $40$ solutions:
- $32$ of them are multiples of $9$.
- $37$ of them are $3$ mod $8$.
- $38$ of them are multiples of $3$.
I was honestly ready to conjecture that (other than $1$) all solutions were multiples of $3$, until $6\,942\,817$ showed up. Why is the first non-multiple of $3$ so large?? That same number is also the first one after $1$ that's not $3$ mod $8$. What's going on here?
Python code:
for n in range(10_000_000):
if (pow(3,n,n+1)==n):
print(n)
EDIT: Here's a graph of "What percentage of the first $x$ nonzero values are $27$ mod $72$?" as $x$ ranges from $1$ to $213$:
https://www.desmos.com/calculator/o1agwn8feo
(Thanks to Zubin Mukerjee for the list of the first 213 nonzero values)
The sequence is now on OEIS. https://oeis.org/A370578
This answer shows that, apart from $n = 0$, all solutions of $n$ are odd. Also, if $3 \mid n$, then $n \equiv 3 \pmod{24}$, so $n$ is congruent to one of $3$, $27$ or $51$ mod $72$, as your results show. OTOH, if $3 \nmid n$, then $n \equiv 1 \pmod{12}$.
This solution also gives heuristic explanations about why almost all $n$ are divisible by $3$, with most being divisible by $9$, i.e., with $n \equiv 27\pmod{72}$.
The following only considers $n \gt 0$. Also, note that
$$3^n \equiv -1 \pmod{n + 1} \;\;\;\to\;\;\; 3^{2n} \equiv 1 \pmod{n + 1} \tag{1}\label{eq1A}$$
Assume an integer solution $n$ to \eqref{eq1A} is even. Using the $p$-adic valuation function, this means
$$\nu_2(n) = i \;\;\;\to\;\;\; n = 2^{i}j, \;\; i\ge 1, \;\; 2\nmid j \tag{2}\label{eq2A}$$
Since $n + 1$ is odd and $\gt 1$, it's a product of one or more odd prime factors. Using the multiplicative order, for any one of these prime factors $p$, plus also using \eqref{eq1A} and \eqref{eq2A}, we get
$$\operatorname{ord}_p(3) = m \;\;\to\;\; m \nmid 2^{i}j, \; m \mid 2^{i+1}j \;\;\to\;\; m = 2^{i+1}k, \; k \mid j \tag{3}\label{eq3A}$$
The conclusion that $2^{i+1}\mid m$ comes from, if it did not, then $m \mid n$ which is not allowed since that would mean $1 \equiv -1 \pmod{p}$.
From Euler's theorem and that $\varphi(p) = p - 1$, we then also have
$$m \mid p - 1 \;\;\;\to\;\;\; p \equiv 1 \pmod{2^{i+1}} \tag{4}\label{eq4A}$$
Since \eqref{eq4A} is true for every prime factor $p$ of $n + 1$, this means the product of all of the prime factors of $n + 1$, including multiple ones, gives that
$$n + 1 \equiv 1 \pmod{2^{i+1}} \;\;\to\;\; n \equiv 0 \pmod{2^{i+1}} \;\;\to\;\; 2^{i+1} \mid n \tag{5}\label{eq5A}$$
However, this contradicts \eqref{eq2A}, thus proving there are no such even solutions of $n$.
For odd $n$, with every odd prime factor $p$ of $n + 1$, the LHS of \eqref{eq1A} shows that $3$ and $-1$ are either both quadratic residues or both quadratic nonresidues mod $p$. To see this, note each prime has a primitive root $g$, so any congruence expressed in terms of powers of $g$ requires the difference of the exponents to be divisible by $p - 1$, which is even, so the exponents must have the same parity.
The table in the Law of quadratic reciprocity section of Wikipedia's "Quadratic residue" article shows $3$ is a quadratic residue iff $p \equiv 1, 11 \pmod{12}$, while $-1$ is a quadratic residue iff $p \equiv 1 \pmod{4}$. Combining these shows $3$ and $-1$ are both quadratic residues iff $p \equiv 1 \pmod{12}$, while they are both quadratic nonresidues (since $p \neq 3$) iff $p \equiv 7 \pmod{12}$. These together give that
$$p \equiv 1 \pmod{6} \tag{6}\label{eq6A}$$
Since $p$ is any odd prime which divides $n + 1$, this means the product of all of them is congruent to $1$ mod $6$.
Due to $3^2 \equiv 1 \pmod{8}$, we have $3^n + 1 \equiv 4 \pmod{8}$, so $n + 1$ can have only $1$ or $2$ factors of $2$. For the latter case,
$$n + 1 \equiv 4 \pmod{6} \;\;\;\to\;\;\; n \equiv 3 \pmod{6} \tag{7}\label{eq7A}$$
Also $n + 1 \equiv 4 \pmod{8} \;\to\; n \equiv 3 \pmod{8}$ so, since $\operatorname{lcm}(6, 8) = 24$, this combined with \eqref{eq7A} gives
$$n \equiv 3 \pmod{24} \tag{8}\label{eq8A}$$
As stated initially, this gives that $3 \mid n$ and $n \equiv 3, 27, 51 \pmod{72}$.
If $n + 1$ has just $1$ factor of $2$ instead, we then get
$$n + 1 \equiv 2 \pmod{6} \;\;\;\to\;\;\; n \equiv 1 \pmod{6} \tag{9}\label{eq9A}$$
Since we also have $n + 1 \equiv 2 \pmod{4} \;\to\; n \equiv 1 \pmod{4}$, we get altogether that
$$n \equiv 1 \pmod{12} \tag{10}\label{eq10A}$$
Regarding why most $n$ are divisible by $3$, note \eqref{eq6A} shows that $p - 1$ always has at least one factor of $3$. If $3 \nmid n$, then \eqref{eq2A} and \eqref{eq3A} show that $3 \nmid m$ for every odd prime factor of $n + 1$, with this excluding many possible prime factors (especially the smaller ones) possibly being used. As for why $n \equiv 27 \pmod{72}$ is so relatively common, note it's the only congruence where $9 \mid n$. Many prime factors have $9 \mid m$, so having even one such prime factor in $n + 1$ would require that $9 \mid n$. Finally, the above only specifies the minimum # of factors of $3$, so $n + 1$ may have more than that, e.g., for $n = 3$ and $n = 27$.
Values of $n$ where $3 \nmid n$ are given by \eqref{eq10A}, so $n \equiv 1, 13, 25, 37, 49, 61 \pmod{72}$. As for why we only have $n \equiv 1 \pmod{72}$ or $n \equiv 25 \pmod{72}$ so far, and not also any other values, note you have only found $2$ values so far where $n \equiv 1 \pmod{72}$, and Zubin Mukerjee's comment states "... the 98th solution, $193264225 \equiv 25 \pmod{72}$". Thus, unless there's some specific reason why any of the other possible congruences should be excluded, I suspect examples of each of them will be found when large enough values of $n$ are checked.