Find all pairs of positive integers $(m,n)$ such that $\frac{n^2+1}{2m}$ and $\sqrt{2^{n-1}+m+4}$ are both integers.
1. We need to find all pairs of positive integers \((m, n)\) such that both \(\frac{n^2 + 1}{2m}\) and \(\sqrt{2^{n-1} + m + 4}\) are integers.

2. First, consider the condition \(\frac{n^2 + 1}{2m}\) being an integer. This implies:
   \[
   2m \mid n^2 + 1
   \]
   Since \(n\) is a positive integer, we can write \(n\) as \(n = 2x + 1\) for some positive integer \(x\) (since \(n\) must be odd for \(n^2 + 1\) to be even).

3. Substituting \(n = 2x + 1\) into the condition, we get:
   \[
   2m \mid (2x + 1)^2 + 1 = 4x^2 + 4x + 2
   \]
   Simplifying, we have:
   \[
   m \mid 2x^2 + 2x + 1
   \]
   Therefore:
   \[
   m \leq 2x^2 + 2x + 1
   \]

4. Next, consider the condition \(\sqrt{2^{n-1} + m + 4}\) being an integer. This implies:
   \[
   2^{n-1} + m + 4 = y^2
   \]
   for some positive integer \(y\). Substituting \(n = 2x + 1\), we get:
   \[
   2^{2x} + m + 4 = y^2
   \]

5. Notice that:
   \[
   (2^x)^2 = 2^{2x} < 2^{2x} + m + 4 = y^2 \leq 2^{2x} + 2x^2 + 2x + 5 < 2^{2x} + 2^{x+1} + 1 = (2^x + 1)^2
   \]
   This implies:
   \[
   2^{x+1} + 1 > 2x^2 + 2x + 5 \implies 2^x > x^2 + x + 2
   \]
   Solving the inequality \(2^x > x^2 + x + 2\) for natural numbers \(x\), we find that \(x \geq 6\).

6. However, for our condition to hold, we must have \(x \leq 5\). Therefore, we need to check \(x \in \{1, 2, 3, 4, 5\}\), which corresponds to \(n \in \{3, 5, 7, 9, 11\}\).

7. Checking each value of \(n\):

   - **When \(n = 3\):**
     \[
     x = 1 \implies m \mid 5 \implies m = 1, 5
     \]
     Checking both values:
     - For \(m = 1\):
       \[
       \sqrt{2^{3-1} + 1 + 4} = \sqrt{8 + 1 + 4} = \sqrt{13} \quad (\text{not an integer})
       \]
     - For \(m = 5\):
       \[
       \sqrt{2^{3-1} + 5 + 4} = \sqrt{8 + 5 + 4} = \sqrt{17} \quad (\text{not an integer})
       \]
     Therefore, no solutions for \(n = 3\).

   - **When \(n = 5\):**
     \[
     x = 2 \implies m \mid 13 \implies m = 1, 13
     \]
     Checking both values:
     - For \(m = 1\):
       \[
       \sqrt{2^{5-1} + 1 + 4} = \sqrt{16 + 1 + 4} = \sqrt{21} \quad (\text{not an integer})
       \]
     - For \(m = 13\):
       \[
       \sqrt{2^{5-1} + 13 + 4} = \sqrt{16 + 13 + 4} = \sqrt{33} \quad (\text{not an integer})
       \]
     Therefore, no solutions for \(n = 5\).

   - **When \(n = 7\):**
     \[
     x = 3 \implies m \mid 25 \implies m = 1, 5, 25
     \]
     Checking all values:
     - For \(m = 1\):
       \[
       \sqrt{2^{7-1} + 1 + 4} = \sqrt{64 + 1 + 4} = \sqrt{69} \quad (\text{not an integer})
       \]
     - For \(m = 5\):
       \[
       \sqrt{2^{7-1} + 5 + 4} = \sqrt{64 + 5 + 4} = \sqrt{73} \quad (\text{not an integer})
       \]
     - For \(m = 25\):
       \[
       \sqrt{2^{7-1} + 25 + 4} = \sqrt{64 + 25 + 4} = \sqrt{93} \quad (\text{not an integer})
       \]
     Therefore, no solutions for \(n = 7\).

   - **When \(n = 9\):**
     \[
     x = 4 \implies m \mid 41 \implies m = 1, 41
     \]
     Checking both values:
     - For \(m = 1\):
       \[
       \sqrt{2^{9-1} + 1 + 4} = \sqrt{256 + 1 + 4} = \sqrt{261} \quad (\text{not an integer})
       \]
     - For \(m = 41\):
       \[
       \sqrt{2^{9-1} + 41 + 4} = \sqrt{256 + 41 + 4} = \sqrt{301} \quad (\text{not an integer})
       \]
     Therefore, no solutions for \(n = 9\).

   - **When \(n = 11\):**
     \[
     x = 5 \implies m \mid 61 \implies m = 1, 61
     \]
     Checking both values:
     - For \(m = 1\):
       \[
       \sqrt{2^{11-1} + 1 + 4} = \sqrt{1024 + 1 + 4} = \sqrt{1029} \quad (\text{not an integer})
       \]
     - For \(m = 61\):
       \[
       \sqrt{2^{11-1} + 61 + 4} = \sqrt{1024 + 61 + 4} = \sqrt{1089} = 33 \quad (\text{an integer})
       \]
     Therefore, \((m, n) = (61, 11)\) is a solution.

8. The suitable pairs are \((m, n) = (1, 3)\) and \((m, n) = (61, 11)\).

The final answer is \( \boxed{ (m, n) = (1, 3) } \) and \((m, n) = (61, 11)\)