If $n-\phi (n)-1>1$ then $n$ is odd. Let $p$ be smallest prime factor of $n$ then if $p\leq n-\phi (n)-1$ then $p|2^n-1$ also $p|2^{p-1}-1$ but also $(p,n-1)=1$. So $p\geq n-\phi (n)$. taking $n=\prod p_i^{\alpha_i}$ and $p_1$ be least prime factor, we get $p_1\geq p_1^{\sum \alpha_i -k}.2\implies \alpha_i=1$ for all $i$. ( If $n$ is not prime).So now we've $p_1+\prod (p_i-1)\geq \prod p_i$ but that's impossible since $n$ is not prime. Thus if $n$ is prime then $n=p=2=m$. Now so we've to look for when $n-\phi (n)-1\leq 1$, which is easy case chase.

Let $n=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\ldots\cdot p_k^{\alpha_k}$, where $p_1<p_2<\ldots<p_k$ are prime divisors of $n$. Note that \[n-\varphi(n)-1=n\frac{p_1\cdot p_2\cdot\ldots\cdot p_k-(p_1-1)(p_2-1)\cdot\ldots\cdot(p_k-1)}{p_1\cdot p_2\cdot\ldots\cdot p_k}-1>\frac{n}{p_1}-1\] If $k>1$ or $\alpha_1>2$ then $n-\varphi(n)-1>p_1$ therefore looking at equation modulo $p_1$ we'll get $p_1\mid 2^{n}-1$ but $p_1\mid 2^{p_1-1}-1$ hence $\text{ord}_{p_1}(2)\mid (p_1-1,n)$ therefore there exist prime $q$ such that $q\mid (p_1-1,n)$ but then $q<p_1$ which is absurd! Now we must have $n=p$ or $n=p^2$. If $n=p$ then $2^p=p^m$ therefore $n=2$ and $m=2$. If $n=p^2$ then $2^{p^2}+(p-1)!=p^2+1$. If $p$ is odd then look at the equation modulo $4$ to get that $(p-1)!\equiv 2 \mod 4$ which means that $p-1<4$ hence $p=3$ which isn't solution. If $p=2$ then we get one more solution $(n,m)=(4,2)$ so we get that only solution's are $(n,m)=(2,2),(4,2)$.$\blacksquare$

Let $n= \prod_{i=1}^k p_{i}^{a_i}$ Then $n- \phi(n) - 1= n(1- \prod_{i=1}^k (1-\frac{1}{p_i})) - 1$. Since $1- \frac{1}{p_i} <1$, we have $n-\phi(n)-1 \ge n(\frac{1}{p_1})-1$, where $p_1$ is the smallest prime divisor of n. For convenience i'll call $p_1=p$. If $p \le n- \phi(n) -1$, $2^n \cong 1(mod$ $p)$. By FLT, $2^{p-1} \cong 1(mod$ $p)$. Suppose that $d=ord_p(2)$ Then $d|p-1$ and $d|n$. $d|p-1 \Longrightarrow d \le p-1 \Longrightarrow d<p$, contradiction. So, $p\ge (n-\phi(n) -1) \ge \frac{n}{p}-1 \Longrightarrow n \le p(p+1)$. If $n=p(p+1)$, since $p \nmid p+1$, $p+1$ must itself be a prime because otherwise it has a prime factor less than $p$. Therefore $p=2$ which gives $n=6$ but this isn't a solution. Since $p|n$, $n \le p^2$. But since $n$ cannot have a prime divisor less than $p$, $n=p$ or $n=p^2$. In the first case, $2^p = p^m \Longrightarrow n=p=2$ and therefore, $(n,m)=(2,2)$. In the second case $2^{p^2} + (p-1)! =p^{2m} + 1$. If $p$ is odd, taking mod $4$ gives $(p-1)! \cong 2(mod$ $4)$. So, $p=3$. But this isn't a solution. So $p=2$. This gives $(n,m)=(4,2)$.

n=1 is a trivial case to check and gives no solution . first lets get rid of the cases when $(n-\phi(n)-1)!$ is odd . then it turns into $2^n=n^m$. and is trivial to deal with. now consider the case $n-\phi(n)-1 \ge 2$ then clearly $n$ is odd. now , dealing the case when $n$ is a prime power or prime is easy. now , consider the case that $n$ has atleast 2 prime factors. then we claim that $n-\phi(n)-1 \ge p$ where $p$ is the smallest prime factor of $n$ proof--- the proof follows by induction of $\omega(n)$ i.e. the number of prime factors of $n$ then suppose $n>1$. and $p$ is the smallest prime dividing $n$ then $2^n=1(modp)$ and $2^{p-1}=1(modp)$ so , $p$ divides $2^{1}-1=1$. a contradiction!

There is another finishing approach that I found. As in the above solutions we get that $m,n$ are odd. Checking the $v_2's$ in both the sides and by Lifting the exponent we get $v_2((n-\phi(n)-1)!)=v_2(n^m+1)=v_2(n+1)$. Now, let $p_1$ be the smallest prime factor of $n$. Then $\log_2(n+1) \ge v_2(n+1) \ge \frac{(n-\phi(n)-1)}{2} \ge \frac{n}{p_1}-1$ now, this is a sharp bound leaving us with trivial case analysis.

We prove some lemmas first: Lemma1: Given any positive integer $n>1$, let $p$ be the smallest prime dividing it.Then $\gcd(n,p-1) = 1$ Proof: Suppose that $\gcd(n,p-1) = d>1$ and pick any prime divisor $q$ of $d$.Then $q \mid d \mid p-1$ and since $p-1>0$, this gives $q \leq p-1 < p$. Also $q \mid d \mid n$ and so we have $q \mid n$ and $q < p$, which contradicts the minimality of $p$. So $\gcd(n,p-1) = 1$ Lemma2: Suppose that $n>1$ is a positive integer, and let $p$ denote its smallest prime divisor. If $n \leq p^2$, then $n = p$ or $p^2$ Proof: As $p \mid n$, we may write $n = kp$ where $k$ is some positive integer Since $n \leq p^2$, this gives $1 \leq k \leq p$ Suppose that $1 < k < p$ and pick any prime divisor $q$ of $k$ Then $q \leq k < p$ and so $q < p$ with $q \mid k \mid kp = n$, contradicting the minimality of $p$ Hence $k =1,p$ i.e. $n = p,p^2$ Lemma3: Let $n$ be a positive integer greater than $1$ and let $p$ be its smallest prime divisor. Then $n - \phi(n) \geq \frac{n}{p}$ Proof: The number $n - \phi(n)$ denotes the number of positive integers less than or equal to $n$, which are not co-prime to it. Consider the numbers $p,2p,3p,\cdots,\frac{n}{p}\cdot p$ These numbers are not co-prime to $n$ and are $\frac{n}{p}$ in number. It follows that $n - \phi(n) \geq \frac{n}{p}$ Coming back to the main problem we have $$2^n + (n - \phi(n) -1)! = n^m + 1$$Clearly for $n = 1$ there is no solution, and so assume $n > 1$ and let $p$ be the smallest prime dividing $n$ We consider two potential cases: Case1:$n - \phi(n) -1 \geq p$ In this case we have $p \mid (n - \phi(n) - 1)!$ and so reading the equation modulo $p$ we get $2^n \equiv 1 \mod p$ This makes $p$ odd and so by Fermat's little theorem $p \mid 2^{p-1} - 1$ As $p$ also divides $2^n - 1$, we have $p \mid 2^{\gcd(p-1,n)} - 1$ By Lemma1 this gives $p \mid 2 - 1 = 1$, a contradiction. Thus there are no solutions in this case. Case2:$n - \phi(n) -1 < p$ or equivalently $p \geq n - \phi(n)$ By lemma3 this gives $p \geq n - \phi(n) \geq \frac{n}{p}$ which further gives $p^2 \leq n$ This along with lemma2 gives $n = p$ or $p^2$ If $n = p$, the equality becomes $2^p = p^m$ which gives $2 \mid p$, forcing $p = 2$ and consequently $m = 2$ This gives the solution $(m,n) = (2,2)$, which indeed satisfies the original statement of the problem. If $n = p^2$, the equality becomes $2^{p^2} + (p^2 - \phi(p^2)-1)! = p^{2m} + 1$ As $\phi(p^2) = p^2 - p$, this gives $$2^{p^2} + (p-1)! = p^{2m} + 1$$Note that $p^{2m} + 1$ cannot be divisible by $4$(if it were then $(p^{m})^2 \equiv 3 \mod 4$, a contradiction) and so $4 \nmid 2^{p^2} + (p-1)!$ Clearly $4 \mid 2^{p^2}$ and so we have $4 \nmid (p-1)!$ which forces $p-1 \leq 3$ which gives $p = 2$ or $3$ Of these only $p = 2$ works giving $m = 2$ This gives the solution $(m,n) \equiv (2,4)$ which indeed works. We conclude that the only solutions to the equation are $(m,n) \equiv (2,2);(2,4)$

We claim that $(n,m) = (2,2) , (4,2)$ are the only solutions. It is easy to see they work, so it suffices to show that these are the only solutions. Let $p$ be the smallest prime divisor of $n$. If $p\leq n - \varphi{(n)} - 1$, then taking modulo $p$ yields $2^n \equiv 1 \pmod{p}$. Let $d$ be the order of $2$ modulo $p$. Then $d\mid \gcd(n,p-1) = 1 \implies d=1 \implies p\mid 1$. Contradiction. So all prime divisors of $n$ are $\geq n - \varphi{(n)}$. Let $n=p_1^{\alpha_{1}}p_2^{\alpha_{2}} ... p_k^{\alpha_{k}}$ with $p_i$ being primes and $p_1 < p_2 < ... < p_k$. We have $n - \varphi{(n)} = p_1^{\alpha_{1} - 1}p_2^{\alpha_{2} - 1} ... p_k^{\alpha_{k} - 1} ( p_1p_2 ... p_k - (p_1 - 1)(p_2 - 1) ... (p_k - 1)) \leq p_1$. If $k\geq 2$, then $p_1p_2 - (p_1 - 1)(p_2 - 1) = p_1 + p_2 - 1 \leq p_1^{\alpha_{1} - 1}p_2^{\alpha_{2} - 1} ... p_k^{\alpha_{k} - 1} ( p_1p_2 ... p_k - (p_1 - 1)(p_2 - 1) ... (p_k - 1)) \leq p_1 \implies p_2\leq 1$. Contradiction. So $k=1$ and we must have $\alpha_{1} \leq 2$. So $n$ must be of the form $p$ or $p^2$ where $p$ is a prime. If $n=p$ where $p$ is a prime, then $2^p = p^m \implies p=2 \implies (n,m)=(2,2)$ is a solution. If $n=p^2$ where $p$ is a prime, then $2^{p^2} + (p-1)! = p^{2m} + 1$. If $p\geq 3$, taking modulo $4$ yields $(p-1)!\equiv 2 \pmod{4} \implies p\leq 3 \implies p=3$ but when $p=3$ there is no solution. Finally, if $p=2$, then we get $(n,m) = (4,2)$ as a solution.

$p$ be the smallest prime divisor of $n$. $n - \phi(n) \geq \frac{n}{p}$.this easy. $n=p^2$ mod4

1 if $n=1$, it is obviously not true 2 if $n=p$, $p$ is a prime. $\Rightarrow \phi (n)=n-1\Rightarrow 2^n+1=n^m+1\Rightarrow n=2\Rightarrow (m,n)=(2,2)$ 3 if $n=p^2$, $p$ is a prime. $\Rightarrow \phi (n)=p^2-p\Rightarrow n-\phi (n)-1=p-1\Rightarrow 2^{p^2}+(p-1)!=p^{2m}+1$ 1 if $p=2$, $\Rightarrow m=2\Rightarrow (m,n)=(2,4)$ 2 if $p\geq 3$, $p^2\equiv 1\pmod {4}\Rightarrow 2^{p^2}+(p-1)!\equiv 2\pmod 4\Rightarrow p=3$ so that $n=9$, and it is obviously not true. 4 others Let $p$ be the smallest prime factor of $n$, and $n=pk$, $k>p$ $\Rightarrow p,2p,\dots,p^2<n,\gcd (p,n)=\gcd (2p,n)=\cdots =\gcd (p^2,n)>1$ $\therefore \phi (n)\leq n-p-1\Rightarrow n-\phi (n)+1\geq p\Rightarrow (n-\phi (n)+1)!\equiv 0\pmod p$ $p|n\Rightarrow 2^n\equiv 1\pmod p\Rightarrow \gcd (2,p)=1\Rightarrow 2^{p-1}\equiv 1\pmod p$ $\Rightarrow 2^{\gcd (n,p-1)}\equiv 1\pmod p\Rightarrow 2^1\equiv 1\pmod p$ which is obviously not true. $\therefore (m,n)=(2,2),(2,4)$