Let $\phi(n)$ be the number of positive integers less than $n$ that are relatively prime to $n$, where $n$ is a positive integer. Find all pairs of positive integers $(m,n)$ such that \[2^n + (n-\phi(n)-1)! = n^m+1.\]
We are given the equation:
\[2^n + (n - \phi(n) - 1)! = n^m + 1\]
where $\phi(n)$ is the Euler's totient function, which counts the number of positive integers less than $n$ that are relatively prime to $n$. We need to find all pairs of positive integers $(m, n)$ that satisfy this equation.

### Lemma 1:
Given any positive integer $n > 1$, let $p$ be the smallest prime dividing it. Then $\gcd(n, p-1) = 1$.

**Proof:**
Suppose $\gcd(n, p-1) = d > 1$ and let $q$ be any prime divisor 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$, so $q \mid n$ and $q < p$, which contradicts the minimality of $p$. Hence, $\gcd(n, p-1) = 1$.

### Lemma 2:
Suppose $n > 1$ is a positive integer, and let $p$ denote its smallest prime divisor. If $n \leq p^2$, then $n = p$ or $n = p^2$.

**Proof:**
Since $p \mid n$, we can write $n = kp$ where $k$ is some positive integer. Given $n \leq p^2$, this implies $1 \leq k \leq p$. Suppose $1 < k < p$ and let $q$ be any prime divisor of $k$. Then $q \leq k < p$, so $q < p$ and $q \mid k \mid kp = n$, contradicting the minimality of $p$. Hence, $k = 1$ or $k = p$, i.e., $n = p$ or $n = p^2$.

### Lemma 3:
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$ that are not co-prime to it. Consider the numbers $p, 2p, 3p, \ldots, \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}$.

### Main Problem:
We have:
\[2^n + (n - \phi(n) - 1)! = n^m + 1\]

#### Case 1: $n - \phi(n) - 1 \geq p$
In this case, $p \mid (n - \phi(n) - 1)!$, so reading the equation modulo $p$ we get:
\[2^n \equiv 1 \pmod{p}\]
This implies $p$ is odd. By Fermat's Little Theorem, $p \mid 2^{p-1} - 1$. Since $p$ also divides $2^n - 1$, we have:
\[p \mid 2^{\gcd(p-1, n)} - 1\]
By Lemma 1, $\gcd(p-1, n) = 1$, so:
\[p \mid 2^1 - 1 = 1\]
This is a contradiction. Thus, there are no solutions in this case.

#### Case 2: $n - \phi(n) - 1 < p$
This implies $p \geq n - \phi(n)$. By Lemma 3, $p \geq n - \phi(n) \geq \frac{n}{p}$, which gives $p^2 \leq n$. By Lemma 2, this means $n = p$ or $n = p^2$.

- **If $n = p$:**
  The equation becomes:
  \[2^p = p^m\]
  This implies $2 \mid p$, forcing $p = 2$. Consequently, $m = 2$. This gives the solution $(m, n) = (2, 2)$, which indeed satisfies the original equation.

- **If $n = p^2:**
  The equation becomes:
  \[2^{p^2} + (p^2 - \phi(p^2) - 1)! = p^{2m} + 1\]
  Since $\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 \pmod{4}$, a contradiction). Thus, $4 \nmid 2^{p^2} + (p-1)!$. Clearly, $4 \mid 2^{p^2}$, so $4 \nmid (p-1)!$, which forces $p-1 \leq 3$, giving $p = 2$ or $3$. Of these, only $p = 2$ works, giving $m = 2$. This gives the solution $(m, n) = (2, 4)$, which indeed works.

We conclude that the only solutions to the equation are $(m, n) = (2, 2)$ and $(2, 4)$.

The final answer is \( \boxed{ (2, 2) } \) and \((2, 4)\).