jmc

We find that $p(n+1)=(n+1{)}^2-(n+1)+41=n^2+2n+1-n-1+41=n^2+n+41$. By the Euclidean algorithm, $$\begin{array}{rl}& \text{gcd}(p(n+1),p(n))\\ & =\text{gcd}(n^2+n+41,n^2-n+41)\\ & =\text{gcd}(n^2+n+41-(n^2-n+41),n^2-n+41)\\ & =\text{gcd}(2n,n^2-n+41).\end{array}$$Since $n^2$ and $n$ have the same parity (that is, they will both be even or both be odd), it follows that $n^2-n+41$ is odd. Thus, it suffices to evaluate $\text{gcd}(n,n^2-n+41)=\text{gcd}(n,n^2-n+41-n(n-1))=\text{gcd}(n,41)$. The smallest desired positive integer is then $n=\boxed{41}$.

In fact, for all integers $n$ from $1$ through $40$, it turns out that $p(n)$ is a prime number.