Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers 2

up vote 8 down vote accepted

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.

share|improve this answer
1  
@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$"? –  Kevin Buzzard Nov 15 '10 at 20:08
    
@Kevin Your "Aah" is correct :-) –  Felipe Voloch Nov 15 '10 at 20:40
    
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. –  Kevin Buzzard Nov 15 '10 at 21:04
    
Hmm, seems they like to have $a\leq 12$\ldots –  Kevin Buzzard Nov 15 '10 at 22:55
add comment

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 :-)

share|improve this answer
1  
Thanks for the reference! Here's a link to the paper on Wagstaff's home page: cerias.purdue.edu/assets/pdf/bibtex_archive/2010-01-report.pdf –  Victor Miller Nov 16 '10 at 15:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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