mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   Primes p such that p^2+p+1=q is prime, and p is largest prime factor of q^3-1 (https://www.mersenneforum.org/showthread.php?t=27728)

 Stargate38 2022-04-17 17:28

Primes p such that p^2+p+1=q is prime, and p is largest prime factor of q^3-1

I was wondering if there's even such a prime p that fits the following:

1. p^2+p+1=q is prime (seems that p must be of the form 6n-1, other than 2 and 3).
2. Largest prime factor of q^3-1 is p.

So far, I haven't found any that fit #2 (searched up to p=997), but I'm guessing #1 has infinitely many solutions. Anyone know how I might do this in PARI/gp? I want to search up to at least p=9999991.

 mathwiz 2022-04-17 18:03

[CODE]? forprime(p = 2, 10000000, q=p*p+p+1; if(isprime(q) && vecmax(factorint(q^3-1)[, 1]) == p, print(p)))
125669
138209
254537
309629
532187
1107497
1126523
1210103
1225817
1287329
1524431
1534349
1539719
1720181
1793123
1814609
1861151
1920731
1932071
1974881
2270423
2366057
2490479
2494931
2530373
2586377
2725841
2755943
2782667
2885837
...[/CODE]

 Dr Sardonicus 2022-04-18 14:22

I note that, if p == 1 (mod 3) then q = p^2 + p + 1 is divisible by 3.

Also, q^3 - 1 = (q-1)*(q^2 + q + 1). If p > 2 then p is the largest prime factor of q-1 (proof: exercise). Also, q == 1 (mod p) so q^2 + q + 1 == 3 (mod p).

So if p > 3 then p does not divide q^2 + q + 1, and we want the largest factor of q^2 + q + 1 to be less than p. Now N = q^2 + q + 1 is slightly larger than p^4, so we want the largest factor of N to be less than N^(1/4).

The probability of a "random" number being that "smooth" is given by the "Dickman function" evaluated at 1/4, which is approximately .00491.

 All times are UTC. The time now is 20:29.