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
  • 1
    $\begingroup$ @Paul $1$ is square-free, by convention (there is no prime whose square divides $1$). $\endgroup$
    – Arthur
    Commented Sep 19, 2016 at 17:59

3 Answers 3

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

$\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.

$\endgroup$
7
  • $\begingroup$ Can you please explain what does $Z/p^2Z$ means? Thanks. $\endgroup$
    – maverick
    Commented Sep 19, 2016 at 18:17
  • $\begingroup$ It is the quotient ring of the integers modulo $ p^2 $. $\endgroup$
    – Ege Erdil
    Commented Sep 19, 2016 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
    Commented Sep 19, 2016 at 18:24
  • $\begingroup$ en.wikipedia.org/wiki/Quotient_ring $\endgroup$
    – Ege Erdil
    Commented Sep 19, 2016 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
    Commented Sep 19, 2016 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} $$

$\endgroup$
2
  • $\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
    Commented Sep 20, 2016 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$ Commented Sep 20, 2016 at 10:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .