View Single Post
Old 2022-04-18, 14:22   #3
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·43·71 Posts
Default

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.
Dr Sardonicus is offline   Reply With Quote