1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ @Paul $1$ is square-free, by convention (there is no prime whose square divides $1$). $\endgroup$ – Arthur Sep 19 '16 at 17:59
9
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
7
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can you please explain what does $Z/p^2Z$ means? Thanks. $\endgroup$ – maverick Sep 19 '16 at 18:17
  • $\begingroup$ It is the quotient ring of the integers modulo $ p^2 $. $\endgroup$ – Ege Erdil Sep 19 '16 at 18:22
  • $\begingroup$ Can you share a link for someone like me to understand it? I have no idea about what a quotient ring is. $\endgroup$ – maverick Sep 19 '16 at 18:24
  • $\begingroup$ en.wikipedia.org/wiki/Quotient_ring $\endgroup$ – Ege Erdil Sep 19 '16 at 18:27
  • $\begingroup$ @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". $\endgroup$ – David K Sep 19 '16 at 19:01
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – Ege Erdil Sep 20 '16 at 10:16
  • 1
    $\begingroup$ @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... $\endgroup$ – Gottfried Helms Sep 20 '16 at 10:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.