# 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$). – Arthur Sep 19 '16 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. – maverick Sep 19 '16 at 18:17
• It is the quotient ring of the integers modulo $p^2$. – Ege Erdil Sep 19 '16 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. – maverick Sep 19 '16 at 18:24
• en.wikipedia.org/wiki/Quotient_ring – Ege Erdil Sep 19 '16 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". – David K Sep 19 '16 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.) – Ege Erdil Sep 20 '16 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... – Gottfried Helms Sep 20 '16 at 10:21