# Many kinds of Infinitely many

Here is the sequence of the primes p =1 mod 6 (and thus p =1 mod 3) such that $(p^{2}+p+1)/ 3$ is not prime :

37 61 67 79 109 139 151 163 181 193 211 229 277 283 307 313 331 337 349 367 373 379 397 433 439 457 463 487 499 523 541 547 571 577 601 607 613 ...

It is reasonable to believe this is an infinite sequence. There are stronger beliefs, though. We could also conjecture that for each of these primes p, there are infinitely many primes q such that p is a factor of $(q^{2}+q+1)/3$. For example; here is the sequence of primes q below 10000 such that 37 is a factor of $(q^{2}+q+1)/3$ :

211 433 787 877 1009 1231 1321 1453 1543 1987 2341 3229 3319 3541 3673 4339 4561 4651 4783 5227 5449 6337 6427 6781 6871 7537 7669 7759 8647 8779 9001 9091

This sequence seems to be infinite. But there is stronger. Here is the sequence of the primes q up to 1000000 such that 37^2 divides $(q^{2}+q+1)/3$ . I would say it is an infinite sequence:

787, 3319, 9001, 27961, 44389, 66499, 69031, 74713, 91141, 115783, 123997, 148639, 151171, 214351, 230779, 257953, 271849, 315451, 329347, 348307, 36 203, 397591, 414019, 419701, 438661, 444343, 460771, 463303, 493627, 501841, 526483, 534697, 542911, 545443, 578299, 583981, 641479, 685081, 698977, 01509, 707191, 742579, 764689, 772903, 781117, 789331, 800077, 832933, 841147, 896113, 945397, 956143, 964357,...

Primes q such that 37^3 divides $(q^{2}+q+1)/3$ up to $10^{7}$. Again an infinite sequence:

542911, 1128637, 2648227, 2670337, 3278173, 3582091, 4775653, 5405599, 6599161, 8726587, 9638341, 9964369,...

Primes q such that 37^4 divides $(q^{2}+q+1)/3$ up to $10^{9}$. Again an infinite sequence:

90480529, 241245967, 247910053, 259155019, 315379849, 349114747, 353695627, 416584543, 484054339, 506544271, 522370117, 533615083, 562769101, 64606474 3, 652728829, 679799641, 702289573, 792249301, 803494267, 870964063, 877628149, 900118081, 904698961, 922608013, 927188893, 960923791, 994658689,...

Primes q such that 37^5 divides $(q^{2}+q+1)/3$ up to $10^{9}$. Again an infinite sequence:

484054339, 900118081,...

Is there an evidence that if p divides an integer valued polynomial, then p^n divides this integer valued polynomial infinitely often for every n ?

-
"...that if p divides...?? – DonAntonio Jan 31 '13 at 12:45
$p$ divides every value of $f(x) = p^2 x + p$, but $p^2$ divides none. – Hurkyl Jan 31 '13 at 14:26
for(x=2,10^5,if((25*x+5)%3^9==0,print1(x,", "))) 7873, 27556, 47239, 66922, 86605, 3^k divides 25x+5 for some x value for k =1,2,3,4,5,6,7,8,9,10 and i stopped at k=10. – user55514 Jan 31 '13 at 14:49

[EDIT --- We can prove that for every $n$ there are infinitely many primes $q$ such that $37^n$ divides $q^2+q+1$. The $37$ and the $q^2+q+1$ can be replaced by any prime and any integer polynomial, with some exceptions as highlighted by the example Hurkyl gives in the comments.]

Suppose $q^2+q+1$ is divisible by $37^n$. Let $s=q+37^nt$, where $t$ is to be determined. Then $$s^2+s+1=q^2+(2)37^nqt+37^{2n}t^2+q+37^nt+1$$ We want this to be divisible by $37^{n+1}$, so we want $at+b$ to be divisible by $37$, where $a=2q+1$ and $b=(q^2+q+1)/37$. It's easy to check that $a$ is not divisible by $37$, so it is guaranteed that there is a value of $t$ such that $at+b$ is a multiple of $37$, and that makes $s^2+s+1$ a multiple of $37^{n+1}$.

This proves, by induction, that for any $n$ you can find $q$ such that $37^n$ divides $q^2+q+1$.

[Aside --- what I've done here is essentially a proof of a very special case of Hensel's Lemma, referred to by @jspecter. If you want the general proof for arbitrary primes and polynomials, and you want to know when there are counterexamples along the lines of the comment by Hurkyl, don't play coy with jspecter, but instead look up Hensel's Lemma, try to understand it, and come back with specific questions if you get stuck.]

Now, this gives one value of $q$ such that $37^n$ divides $q^2+q+1$, but you want infinitely many. Here are two ways to cook that goose.

1. For any given $q$, there are only finitely many values of $n$ such that $37^n$ divides $q^2+q+1$. So, if you take $n$ too big for $37^n$ to divide $q^2+q+1$, there must be a new value of $q$ that works for that $n$. Repeating gets you infinitely many $q$.

2. If $37^n$ divides $q^2+q+1$, then it also divides $r^2+r+1$ where $r=q+37^nt$ and $t$ is any positive integer whatsoever. So, again, infinitely many.

But unless I miss my guess, you want even more --- you want infinitely many prime values of $q$ such that $37^n$ divides $q^2+q+1$. Dirichlet's Theorem on Primes in Arithmetic Progression to the rescue: since $q$ is not a multiple of $37$, Dirichlet says that for each $n$ there are infinitely many values of $t$ such that $q+37^nt$ is prime. And we are done.

-
Gerry; though not more than an amateur; what i like about maths is its decency; no way, in general, to tamper. I offer 20 € (European Euros) if you´re able for a decent math statement. Not alchemy, please. – user55514 Feb 2 '13 at 9:20
What I like about Mathematics is its precision, the way that you can know exactly what something means, and then make deductions that can't be refuted. So, what exactly do you mean by "decent"? What exactly do you mean by "alchemy"? I'm sure you have a clear picture in your mind of what these terms mean when you use them, but I don't have a clue, and can't make much of a response until I do. Or perhaps more relevant: what exactly is it that you don't like about my answer to your question? – Gerry Myerson Feb 2 '13 at 23:23
Your math argument begins well, the inductive part, but then there are errors. But it could also be i am unable to understand your math style. – user55514 Feb 3 '13 at 23:48
"but then there are errors" is not helpful; pointing out exactly where there's an error, and why it's an error, that would be helpful. I could do something about that. So, I repeat: what exactly is it that you don't like about my answer to your question? – Gerry Myerson Feb 4 '13 at 6:15

Consider the integer valued polynomial $f(X) = X^2 + X + 1.$ Then $3|f(1).$ One then checks that $f$ does not have a root in $\mathbb{Z}/9$ and therefore $9\not|f(n)$ for any $n \in \mathbb{Z}$ (let alone for any prime $q).$

On the other hand, given a polynomial $f \in \mathbb{Z}[\frac{1}{N}],$ it will have a root in $\mathbb{Q}_p$ for infinitely many $p.$ And if $p\not|f(0)N$ any such root must lie in $\mathbb{Z}_p^{\times}.$ Therrefore as the primes of $\mathbb{Z}$ not dividing $p$ are dense in $\mathbb{Z}_p^{\times},$ it follows that there exist infinitely many primes $p$ and integers $n$ such that there are infinitely many primes $q$ such that $f(q)| p^n.$

Finally, by Hansel's lemma, if $p\not|N$ and if $f$ is separable mod $p$ then $f$ has a root in $\mathbb{Z}_p.$ Hence if $p,q$ are primes such that $p \not| Nf'(0)gcd(f,f')$ and $p|f(q),$ then there are infinitely many primes $q'$ and integers $n$ such that $p^n|f(q').$

-
(the comment by user55514 that Gerry refers to has been deleted) – Zev Chonoles Mar 8 '13 at 5:47