A direct proof that there is a prime between $n$ and $n^2+1$? I am trying to prove there is a prime between $n$ and $n^2+1$ without using Bertrand's postulate or Prime number theorem.
Do you have any idea?  
Yuval Filmus's answer for this problem provides a quite useful idea.
But since $n^2+1\lt n!$ for $n\ge4$,  I do not know how to use it for this question.
 A: We need to find (or at least prove the existence of) a positive integer $K = K(n)$ having a prime factor between $n$ and $n^2+1$.
For a prime $p$ and a postivie integer $k$, let $v_p(k)$ denote the exponent of $p$ in the prime factorisation of $k$, i.e. $v_p(k)$ is characterised by $p^{v_p(k)} \mid k$ and $p^{v_p(k)+1} \nmid k$. Next recall Legendre's formula
$$v_p(n!) = \sum_{\ell = 1}^{\infty} \biggl\lfloor \frac{n}{p^{\ell}}\biggr\rfloor = \sum_{\ell = 1}^{\bigl\lfloor \frac{\log n}{\log p}\bigr\rfloor} \biggl\lfloor \frac{n}{p^{\ell}}\biggr\rfloor$$
for the prime factorisation of the factorials. Much of Legendre's formula generalises to arbitrary (increasing) arithmetic progressions. If we have an arithmetic progression
$$A_m = a + m\cdot d$$
with $a \geqslant 0$ and $d > 0$, then for every $r$ coprime to $d$ exactly one of every $r$ consecutive terms of the progression is a multiple of $r$. Let $\mu_r(k)$ denote the number of multiples of $r$ among $A_1, A_2, \dotsc, A_k$. Without any special knowledge about $d$ and $r$ we cannot pin down $\mu_r(k)$ exactly, but we know that for $r$ coprime to $d$ we have
$$\biggl\lfloor \frac{k}{r}\biggr\rfloor \leqslant \mu_r(k) \leqslant \biggl\lceil \frac{k}{r}\biggr\rceil.$$
By the same argument that shows Legendre's formula we can, for the "A-orial"
$$P_k = \prod_{m = 1}^k A_m,$$
see that
$$v_p(P_k) = \sum_{\ell = 1}^{\infty} \mu_{p^{\ell}}(k)$$
for all primes $p$. For primes not dividing $d$, although we cannot give an explicit exact form for $v_p(P_k)$, we have pretty reasonable bounds, namely
$$\sum_{\ell = 1}^{\bigl\lfloor \frac{\log k}{\log p}\bigr\rfloor} \biggl\lfloor \frac{k}{p^{\ell}}\biggr\rfloor \leqslant v_p(P_k) \leqslant \sum_{\ell = 1}^{\bigl\lfloor \frac{\log A_k}{\log p}\bigr\rfloor} \biggl\lceil \frac{k}{p^{\ell}}\biggr\rceil,$$
since evidently $\mu_r(k) = 0$ for $r > A_k$.
Now let's come to the proof that for $n > 1$ there is always a prime strictly between $n$ and $n^2$ (for $n = 1$ we need the extra $+1$). Fix $n \geqslant 2$, and let $p_s$ be the largest prime not exceeding $n$, so $p_s \leqslant n < p_{s+1}$. Consider the arithmetic progression
$$A_m = 1 + m \cdot p_s$$
and let $k = p_s - 1$. On the one hand, we have
$$P_k = \prod_{m = 1}^k A_m > \prod_{m = 1}^k (A_m - 1) = p_s^{k}\cdot k!\,.\tag{1}$$
On the other hand, we have $A_k = p_s(p_s - 1) + 1 = p_s^2 - p_s + 1 < p_s^2$ and thus by the above
$$v_p(P_k) \leqslant \sum_{\ell = 1}^{\bigl\lfloor 2 \frac{\log p_s}{\log p}\bigr\rfloor}\biggl\lceil \frac{k}{p^{\ell}}\biggr\rfloor \leqslant \biggl\lfloor 2\frac{\log p_s}{\log p}\biggr\rfloor + \sum_{\ell = 1}^{\infty} \biggl\lfloor \frac{k}{p^{\ell}}\biggr\rfloor = \biggl\lfloor 2\frac{\log p_s}{\log p}\biggr\rfloor + v_p(k!)$$
for all primes $p \neq p_s$, hence
$$\prod_{p < p_s} p^{v_p(P_k)} \leqslant \prod_{p < p_s} \Bigl( p_s^2\cdot p^{v_p(k!)}\Bigr) = p_s^{2(s-1)}\cdot k!\,.\tag{2}$$
Also, none of the $A_m$ is divisible by $p_s$, whence $v_{p_s}(P_k) = 0$. Therefore it follows from $(1)$ and $(2)$ that
$$\prod_{p \leqslant n} p^{v_p(P_k)} < P_k$$
and consequently $P_k$ has a prime factor larger than $n$ as soon as $2(s-1) \leqslant k = p_s-1$, or equivalently $p_s \geqslant 2s - 1$. Which in fact holds for all $s$. And since a prime factor of $P_k$ divides at least one $A_m, \, 1 \leqslant m \leqslant k$ it follows that all prime factors of $P_k$ are $\leqslant A_k < p_s^2 \leqslant n^2$. So for $n \geqslant 2$ there always is at least one prime $q$ satisfying $n < q < n^2$ (or, slightly more tightly, $n < q \leqslant n^2 - n + 1$).
A: Attempt 1 (failure):
Since $n^2+1$ is an integer, there exists some prime $p\le n^2+1$ such that $p\mid n^2+1$.
Suppose by way of contradiction we have $p<n$ for all $p\mid n^2+1$. Then $p\mid n^2$. But then $p\not\mid n^2+1$, because $n^2+1=kp+1$ for some $k\in\mathbb{N}$.
Thus for some $p\mid n^2+1$ we must have $n\le p\le n^2+1$.
Why does this not work? @Daniel Fischer points out that $n=7$ is a counterexample. All the primes that divide $n^2+1=50=2\cdot 5^2$ are smaller than $7$ and none of them divide $n^2$.
