$n| 3^n +1$
My progress so far:
$3^n + 1$ is even , thus $n$ is also even
$3^n + 1 \equiv n \equiv 2 \mod 10$ or $3^n + 1 \equiv n \equiv 0 \mod 10$
$3^n + 1 \equiv n \equiv 1 \mod 3$ / I'm not quite sure about this
I've found 3 solutions: $n=1, n=2, n=10$
Are there more?
On
There are infinitely many such numbers $n$. In fact, you can demand that $n$ have a given number of prime divisors.
Claim: Fix an integer $a>1$. Let $k$ be a nonnegative integer. There exists a positive integer $n_k$ such that exactly $k$ distinct prime natural numbers divide $n_k$ and $n_k\mid a^{n_k}+1$.
Proof.
The base case $k=0$ is trivial (i.e., $n_0=1$). For $k=1$, take $n_k$ to be the largest prime natural number $q$ that divides $a+1$. This choice ($n_1=q$) works because $$a^q + 1 \equiv a\left(a^{q-1}\right)+1 \equiv a\cdot 1+1 \equiv 0\pmod{q}$$ by Fermat's Little Theorem.
Now, if $q$ is odd, then we set $p:=q$. If $q=2$, then $a+1$ is a power of $2$, and we let $p$ be an odd prime divisor of $a^{n_1}+1=a^2+1$. Since $a^2+1=(a+1)(a-1)+2\equiv 2\pmod{8}$, $p$ exists.
Next, suppose that $n_k$ exists. If $k=1$ and $p\neq q$ (i.e., $q=2$), set $n_{k+1}:=pn_k=2p$. That is, $$n_{k+1}\mid a^2+1 \mid (a^2+1)\sum_{j=0}^{p-1}\,(-1)^j\,a^{2j}=a^{2p}+1=a^{n_{k+1}}+1\,.$$
For $p=q$ or $k>1$, consider the factorization $$a^{p\,n_k}+1=\left(a^{n_k}+1\right)\,\Phi_{2p}\left(a^{n_k}\right)\,,$$ where $\Phi_{2p}(t)=t^{p-1}-t^{p-2}+t^{p-3}-\ldots-t+1 \in \mathbb{Z}[t]$ is the $(2p)$-th cyclotomic polynomial. There exists a prime natural number $p_k$ dividing $\Phi_{2p}\left(a^{n_k}\right)$ that does not divide $a^{n_k}+1$. To show this, we first note that $$\Phi_{2p}(t)=\sum_{j=0}^{p-1}\,(-1)^jt^j=p+\sum_{j=0}^{p-1}\,(-1)^j\,\left(t^j-(-1)^j\right)\,.$$ If $a^{n_k}+1=pm$ for some positive integer $m$, then $$\Phi_{2p}\left(a^{n_k}\right)=\Phi_{2p}\left(pm-1\right)=p+\sum_{j=0}^{p-1}\,(-1)^j\,\left((pm-1)^j-(-1)^j\right)\,.$$ Ergo, $$\Phi_{2p}\left(a^{n_k}\right)\equiv p +\sum_{j=0}^{p-1}\,(-1)^j\big((-1)^{j-1}jpm\big)=p-pm\sum_{j=0}^{p-1}\,j\equiv p\pmod{p^2}\,,$$ since $\sum_{j=0}^{p-1}\,j=p\left(\frac{p-1}{2}\right)\equiv0\pmod{p}$. Furthermore, it is clear that $\Phi_{2p}\left(a^{n_k}\right)>p$ is an odd number. By setting $q_k$ to be a prime natural number that divides $\frac{\Phi_{2p}\left(a^{n_k}\right)}{p}$, we see that $n_{k+1}:=q_k p n_{k}$ satisfies the divisibility condition $n_{k+1} \mid a^{pn_k}+1 \mid a^{n_{k+1}}+1$. The induction is now complete.
Corollary: For given integers $a>1$ and $k>1$, there are infinitely many positive integers $n$ with exactly $k$ distinct prime divisors such that $n\mid a^n+1$.
Proof.
Let $n_k$ and $p$ be as in the proof of the claim above. Then, $n:=p^rn_k$ works for every $r=0,1,2,3,\ldots$. In fact, let $n_k=2^\mu\,\prod_{i=1}^\ell\,s_i^{\alpha_i}$ be a prime factorization of $n_k$ ($\mu\in\mathbb{Z}_{\geq 0}$, $\alpha_1,\alpha_2,\ldots,\alpha_\ell\in\mathbb{Z}_{>0}$, and $s_1,s_2,\ldots,s_\ell$ are primes such that $2<s_1<s_2<\ldots<s_\ell$), then any natural number of the form $n:=2^{\mu}\,\prod_{i=1}^\ell\,s^{\beta_i}$, where $\beta_i$ is an integer such that $\beta_i\geq \alpha_i$ for every $i=1,2,\ldots,\ell$, is a solution to $n\mid a^n+1$.
P.S. The following statement is also true (with a similar proof). If $a>2$ and $k>1$ are integers, then there exist infinitely many positive integers $n_k$ such that $n_k$ is divisible by exactly $k$ distinct prime natural numbers and $n_k\mid a^{n_k}-1$.
On
In addition to your solutions,Suppose n is odd, then :
$3^n+1=(4-1)^n+1= 4 k$.
So we must have $n|k$, that is n can be any factor of a composite odd number like k.
On
I have a factoring program that accepts a bound; it checks the target for divisibility by all primes up to the bound, then stops. In this way I can give a little bit of information about some very large numbers.
So, for example, $3^{10} \equiv -1 \pmod {1181}.$ It follows that, whenever $k$ is odd, we also get $3^{10k} \equiv -1 \pmod {1181}.$ Next $3^{50} \equiv -1 \pmod {394201}.$ It follows that, whenever $k$ is odd, we also get $3^{50k} \equiv -1 \pmod {394201}.$ This is why there was room for the surprise value $n=11810.$
Thu Jul 5 14:45:12 PDT 2018
n 1 = 1 ; 3^n + 1 = 2^2 //
n 2 = 2 ; 3^n + 1 = 2 5 //
n 10 = 2 5 ; 3^n + 1 = 2 5^2 1181 //
n 50 = 2 5^2 ; 3^n + 1 = 2 5^3 101 1181 394201 61070817601 //
n 250 = 2 5^3 ; 3^n + 1 = 2 5^4 101 1181 3001 8501 394201 cdot mbox{BIG} //
n 1250 = 2 5^4 ; 3^n + 1 = 2 5^5 101 1181 3001 8501 394201 cdot mbox{BIG} //
n 5050 = 2 5^2 101 ; 3^n + 1 = 2 5^3 101^2 1181 394201 cdot mbox{BIG} //
n 6250 = 2 5^5 ; 3^n + 1 = 2 5^6 101 1181 3001 8501 212501 394201 cdot mbox{BIG} //
n 11810 = 2 5 1181 ; 3^n + 1 = 2 5^2 1181^2 cdot mbox{BIG} //
n 25250 = 2 5^3 101 ; 3^n + 1 = 2 5^4 101^2 1181 3001 8501 394201 cdot mbox{BIG} //
n 31250 = 2 5^6 ; 3^n + 1 = 2 5^7 101 1181 3001 8501 62501 212501 394201 cdot mbox{BIG} //
n 59050 = 2 5^2 1181 ; 3^n + 1 = 2 5^3 101 1181^2 394201 cdot mbox{BIG} //
n 126250 = 2 5^4 101 ; 3^n + 1 = 2 5^5 101^2 1181 3001 8501 394201 cdot mbox{BIG} //
n 156250 = 2 5^7 ; 3^n + 1 = 2 5^8 101 1181 3001 8501 62501 212501 394201 cdot mbox{BIG} //
First we can say that clearly $n$ is not divisible by $3$.
And clearly $n=1$ is a solution because $1$ divides every integer.
So $n\mid 3^n+1 \implies 3^n\equiv -1 \bmod n$. We know from Fermat's Little Theorem that for $p$ prime, $3^n\equiv 3 \bmod p$, so to have $n$ prime we need $3\equiv -1\bmod n$, so $n\mid 4 \implies n=2$ is the only prime solution.
Otherwise since $3\nmid n$ we know that there is some minimum $k>0$ with $3^k\equiv 1\bmod n$. (This $k$ is $\text{ord}_n(3)$.) Now if there is a value $\ell>0$ such that such that $3^\ell\equiv -1\bmod n$ then the minimum value of $\ell$ is $k/2$, since $3^{2\ell}\equiv -1^2\equiv 1 \bmod n$. If $k$ is not even, there will be no solution and even if $k$ is even, it's not guaranteed that there is such a value, since there will be other roots of $1$ with $n$ composite.
So we need $k:=\text{ord}_n(3)$ even and does not divide $n$, with $\ell:=k/2$ divides $n$ and $3^\ell\equiv -1\bmod n$.
... to be continued with Carmichael function and proof of $2\cdot 5^i$ solutions...