4

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$?

Pedro Orlando
  • 63
  • 3
    If $n=2$ then $n^2+n-1=5$. But $p=5$ is not of the form $10k+9$. (I.e., it's always a good idea to check some small examples to see if what you're trying to prove is true.) – Barry Cipra May 21 '18 at 22:44
  • 2
    For $n=3$, you get $n^2+n-1=9+3-1=11$, so your claim is wrong, but your proof seems to be correct! – Watson May 21 '18 at 23:00
  • Then how is $2^2+2-1$ divisible by $5$ (by being equal to it, of course)? You have to allow $(5|p)=0$ as well as $(5|p)=1$, thus there can be a prime factor of $5$. – Oscar Lanzi May 22 '18 at 00:14
  • Oh, apologies, another hypothesis was that $p \neq 5$. I forgot to point that out. – Pedro Orlando May 22 '18 at 00:21

1 Answers1

0

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.

Oscar Lanzi
  • 39,403