12
$\begingroup$

This question was asked on NMBRTHRY by Kurt Foster:

If $p$ is a prime number and $\mathbb{F}_p$ the field of $p$ elements, the zeroes of the Artin-Schreier polynomial

$x^p - x - 1 \in \mathbb{F}_p[x]$

obviously have multiplicative order dividing $1 + p + p^2 + \dots + p^{p-1} = (p^p - 1)/(p-1)$ (express the norm as the product of the compositional powers of the Frobenius map)

Once upon a time, long long ago, I read that it had been conjectured (by Shafarevich IIRC) that this is the exact multiplicative order for every prime $p$. Can anyone supply a reference?

$\endgroup$
0

2 Answers 2

10
$\begingroup$

I've never seen it ascribed to Shafarevich, but it is an old question. As a question, it equivalent to determining the period mod p of the sequence of Bell numbers discussed, e.g. in:

Levine, Jack; Dalton, R. E. Minimum periods, modulo p, of first-order Bell exponential integers. Math. Comp. 16 1962 416–423.

But they refer to even older papers. Any conjecture is wishful thinking since we can't get past $p=29$ or so with current technology. (Edit: As Kevin points out in the comments, I am seriously underestimating current technology, so this comment applies only to last century.)

Incidentally, I proved that the order is at least $2^{2.54p}$ in JTNB 16 (2004) 233-239.

$\endgroup$
4
  • 1
    $\begingroup$ @Felipe: I don't understand what you mean by "we can't get past $p=29$ or so with current technology". I just checked that $(31^{31}-1)/30$ was prime in a gazillionth of a second on a computer, so aren't I done for $p=31$? And if it hadn't been prime then I would have just checked to see if the order of $t$ divided $N/q$ for all prime divisors $q$. Aah---are you saying that we can't get past "the point after which we can't factor random numbers of size about $p^p$"? $\endgroup$ Nov 15, 2010 at 20:08
  • $\begingroup$ @Kevin Your "Aah" is correct :-) $\endgroup$ Nov 15, 2010 at 20:40
  • $\begingroup$ I think $p=67$ is getting tough for my laptop. On the other hand I suspect that there are people who do spend their time trying to factor numbers of the form $a^b\pm1$ (the Cunningham Project?) and so one might be able to look up a lot more answers there. $\endgroup$ Nov 15, 2010 at 21:04
  • $\begingroup$ Hmm, seems they like to have $a\leq 12$\ldots $\endgroup$ Nov 15, 2010 at 22:55
10
$\begingroup$

The current computational status is that this is known for all p < 126 and also for p = 137, 149, 157, 163, 167 and 173. See Peter L. Montgomery, Sangil Nahm and Samuel S. Wagstaff Jr., "The period of the Bell numbers modulo a prime", Math. Comp., 79, 271, July 2010, 1793-1800. The method used requires a factorization of (p^p-1)/(p-1) which is hard for larger p :-)

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.