# Is $x^2+x-1$ squarefree?

I noticed that the expression $f(x) = x^2+x-1$ seemed to be squarefree for every positive integer value of $x$. Equivalently, there does not exist a prime $p$ for any $x \in \mathbb{Z}^+$ such that $$\dfrac{x^2+x-1}{p^2}$$ is an integer. Is this true and if so how do we prove it?

• @Paul $1$ is square-free, by convention (there is no prime whose square divides $1$). Sep 19, 2016 at 17:59

Its not square free. Following are few examples:
x = 36, f(x) = 1331 and is divisible by 11*11
x = 42, f(x) = 1805 and is divisible by 19*19
x = 84, f(x) = 7139 and is divisible by 11*11
x = 157, f(x) = 24805 and is divisible by 11*11
x = 198, f(x) = 39401 and is divisible by 31*31
x = 205, f(x) = 42229 and is divisible by 11*11
x = 226, f(x) = 51301 and is divisible by 29*29
x = 278, f(x) = 77561 and is divisible by 11*11
x = 318, f(x) = 101441 and is divisible by 19*19

It is quite easy to see that this proposition cannot be true from a purely theoretical perspective. Fix a prime $p \neq 2, 5$, and that is $1$ or $4$ modulo $5$, for example $p = 11$. (The reason for this choice will become clear shortly.) Working in $\mathbf Z/p^2 \mathbf Z$, we can write

$$X^2 + X - 1 = 0$$ $$\left( X + \frac{1}{2} \right)^2 = \frac{5}{4}$$

where the inverses make sense since $p \neq 2$. On the other hand, squares in $\mathbf Z/p \mathbf Z$ lift to squares in $\mathbf Z_p$ (the p-adic integers) by Hensel's lemma, therefore $5$ is a quadratic residue modulo $p^2$ iff it is a quadratic residue modulo $p$. By quadratic reciprocity, this is true if and only if $p$ is $1$ or $4$ modulo $5$. Hence, we may take square roots on both sides and find the solution

$$X = \frac{\pm \sqrt{5} - 1}{2}$$

For instance, $48^2 = 5$ modulo $11^2$, so for $X = 47/2 = 47 \cdot 61 = 84$ modulo $121$, the given expression is divisible by $121$. This produces infinitely many such examples. Note that exactly the same method yields that if $p \equiv 2, 3 \pmod{5}$ then $p$ cannot divide $X^2 + X - 1$ for any value of $X$, so the examples found this way are the only ones, a result which agrees with the computational answer provided by maverick.

• Can you please explain what does $Z/p^2Z$ means? Thanks. Sep 19, 2016 at 18:17
• It is the quotient ring of the integers modulo $p^2$. Sep 19, 2016 at 18:22
• Can you share a link for someone like me to understand it? I have no idea about what a quotient ring is. Sep 19, 2016 at 18:24
• en.wikipedia.org/wiki/Quotient_ring Sep 19, 2016 at 18:27
• @maverick You might find en.wikipedia.org/wiki/Modular_arithmetic#Integers_modulo_n a little more accessible than the higher-level approach. Note that the article is still describing a quotient ring, but it doesn't use the term "quotient ring". Sep 19, 2016 at 19:01

Systematizing @maverick's answer and giving more examples for @Starfall's systematic solution:

It seems we get solutions only for $p \equiv \pm 1 \pmod{10}$. The $x$ occur then in the following residue classes $\pmod{p^2}$ for $k=0 .. \infty$.
So for instance for $p=11$ that means we get $x_{2k} = 3+ 3p + k p^2$ and $x_{2k+1} = 7+ 7p + k p^2$ for $k \in \mathbb N$ :

$$\small \begin{array} {r|rr} p & x_{2k} & x_{2k+1} \\ \hline 11 & 3+3*11+O(11^2) & 7+7*11+O(11^2) \\ 31 & 12+6*31+O(31^2) & 18+24*31+O(31^2) \\ 41 & 34+18*41+O(41^2) & 6+22*41+O(41^2) \\ 61 & 17+26*61+O(61^2) & 43+34*61+O(61^2) \\ 71 & 8+25*71+O(71^2) & 62+45*71+O(71^2) \\ 101 & 78+44*101+O(101^2) & 22+56*101+O(101^2) \\ 131 & 119+56*131+O(131^2) & 11+74*131+O(131^2) \\ 151 & 123+54*151+O(151^2) & 27+96*151+O(151^2) \\ 181 & 13+67*181+O(181^2) & 167+113*181+O(181^2) \\ 191 & 102+37*191+O(191^2) & 88+153*191+O(191^2) \\ ... & ... & ... \end{array}$$ and $$\small \begin{array} {r|rr} p & x_{2k} & x_{2k+1} \\ \hline 19 & 4+2*19+O(19^2) & 14+16*19+O(19^2) \\ 29 & 23+7*29+O(29^2) & 5+21*29+O(29^2) \\ 59 & 33+5*59+O(59^2) & 25+53*59+O(59^2) \\ 79 & 49+34*79+O(79^2) & 29+44*79+O(79^2) \\ 89 & 9+14*89+O(89^2) & 79+74*89+O(89^2) \\ 109 & 98+25*109+O(109^2) & 10+83*109+O(109^2) \\ 139 & 63+14*139+O(139^2) & 75+124*139+O(139^2) \\ 149 & 108+58*149+O(149^2) & 40+90*149+O(149^2) \\ 179 & 74+7*179+O(179^2) & 104+171*179+O(179^2) \\ 199 & 61+50*199+O(199^2) & 137+148*199+O(199^2) \\ ... & ... & ... \end{array}$$

• Well, odd primes are necessarily $1$ modulo $2$, so this answer doesn't really say anything new... (You are just repeating what I said, which is that the only primes that could possibly work are the ones that are $\pm 1$ modulo $5$, and you can get infinitely many examples from any such prime.) Sep 20, 2016 at 10:16
• @Starfall: you're right, I don't say anything new after your answer. I even didn't intend such. But for my own (and possibly for some other's) intuition a set of examples is always good - I didn't have a good idea for the set of concrete solutions after reading your answer with the general solution (for instance I've nearly no experience with/understanding of the "lifting" in Hensel's lemma). And the list of maverick didn't give me enough information about the structure of the set of solutions. So... Sep 20, 2016 at 10:21