Now, what I have done so far is the following:
Let $p$ be a prime such that $p | n^2+n-1$, then $n^2+n-1 \equiv 0 \pmod p$
This congruence has a solution if and only if $x^2 \equiv \Delta \pmod p$ has a solution, where $\Delta = b^2 - 4ac = 1^2 - 4\cdot1\cdot(-1) = 5$.
Since $\Delta = 5$, this has a solution iff $(\frac{5}{p}) = 1$ (the Legendre symbol).
And this Legendre symbol is $1$ iff $p \equiv 1, 4 \pmod 5$
Which, in turn, means $p \equiv 1, 4, 6, 9 \pmod {10}$. But $p$ cannot be congruent to $4$ or $6$ modulo $10$, for otherwise it would not be a prime.
Therefore, $p \equiv 1, 9 \pmod {10}$.
How do I get rid of the $p \equiv 1 \pmod {10}$ solution and prove that it can only be congruent to $9$, i.e. be of the form $10k + 9$, for some k?
Is this proof valid for all choices of $p\neq 5$? If so, mayhap my teacher forgot about the $p$ of the form $10k+1$?
As the comments indicate, the claim is plainly false if we consider only positive prime factors. But, if we consider primes over the integers, then they come in additive inverse pairs. Thus by choosing the proper sign any allowable prime factor could be either $10k+1$ or $10(-k)-1$ for some integer $k$.
Except, of course, that the proposition $(5|p)=+1$ is not necessary. Certainly $(5|p)=-1$ fails, but there can also be $(5|p)=0$ -- for $p=5$. You must allow or specifically exclude $5$, or over the integers $\pm 5$, as a prime factor.