1
$\begingroup$

I'm looking for a prime $p$ such that $(p-1)$ has many "small", preferably distinct, divisors.

I tried framing the question as solutions for $p$ to the system, \begin{align*} \phi(p) = 0 \mod p_i \quad \text{for } i=1\cdots n \end{align*} where $p_i$ is the i'th prime.

Does anybody know any efficient ways to solve this or have some literature that touches this topic?

|cite|improve this question
$\endgroup$
  • $\begingroup$ For example, like $p=M_{17}=2^{17}-1$? Then $p-1=2\cdot 3\cdot 5\cdot 17\cdot 257$. Have a look for literature in cryptography (smooth numbers), e.g., Pollard's $p-1$ method etc. $\endgroup$ – Dietrich Burde Aug 23 at 15:27
  • $\begingroup$ Sorry, I made a typo, I'm of cause looking at \phi(p) = 0 \mod p_i $\endgroup$ – limeeattack Aug 23 at 15:32
  • $\begingroup$ mathworld.wolfram.com/HighlyCompositeNumber.html or en.m.wikipedia.org/wiki/Primorial_prime $\endgroup$ – Roddy MacPhee Aug 23 at 15:37
  • 2
    $\begingroup$ Number theorists call $\,p-1\,$ smooth. Searching on that should reveal much of interest. $\endgroup$ – Bill Dubuque Aug 23 at 15:53
  • $\begingroup$ (Although "friable" is much better terminology than "smooth".) $\endgroup$ – Greg Martin Aug 23 at 15:54
2
$\begingroup$

You can't do much better than http://oeis.org/A018239, which has the primes that are one more than a primorial. In particular $200560490131$ is one more than the product of all the primes up to $31$. The next one is rather large $$171962010545840643348334056831754301958457563\\ 589574256043877110505832165523856261308397965147\\ 9555788009994557822024565226932906295208262756822\\ 275663694111$$ You can find more from http://oeis.org/A005234 which gives the highest prime to multiply before adding $1$ to get a prime.

|cite|improve this answer
$\endgroup$

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.