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

How can I prove, that for any positive integer $n>0$ there is a prime $p$, such that the multiplicative group of the residue ring $Z_p^*$ contains an element $a$ of order $n$? No ideas at all...

share|improve this question

closed as too localized by Mark Sapir, Felipe Voloch, Peter Mueller, Charles, Derek Holt Jun 19 '13 at 21:40

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

    
Is this a homework problem? –  Mark Sapir Jun 19 '13 at 18:16
    
Start by investigating the case that n is prime, and look at factors of a^n - 1. When you handle that, try n a prime power. Gerhard "Eventually, Look Up Zsigmondy's Theorem" Paseman, 2013.06.19 –  Gerhard Paseman Jun 19 '13 at 18:18
    
Voted to close. –  Mark Sapir Jun 19 '13 at 18:31
    
Not research level, but also probably not homework. Please do not delete; there is information in the answer and in the comments which could be useful for mathematicians. –  Todd Trimble Jun 24 '13 at 0:49

1 Answer 1

up vote 1 down vote accepted

$Z_p^*$ is of order $p-1$ so what you are really asking is for a prime in the arithmetic progression $n+1, 2n+1, 3n+1, \ldots$. This is true by Dirichlet's theorem, see http://en.wikipedia.org/wiki/Dirichlet%27s_theorem_on_arithmetic_progressions

share|improve this answer
    
More elementarily, the poster is asking for a (positive) integer b such that b^n - 1 is a multiple of some prime p while b^m - 1 is not such a multiple for m < n. A proof by Bang was given for n > 6 (pick b=2) and for fixed b and n all the allowed cases were characterized by Zsigmondy. Gerhard "Ask Me About System Design" Paseman, 2013.06.19 –  Gerhard Paseman Jun 19 '13 at 19:10
    
But I'm not sure that's the cleanest approach, Gerhard. I would agree that Dirichlet's theorem in its full statement (involving densities) is a sledgehammer, but the infinitude of primes in this arithmetic progression can be proven in very elementary fashion. See for example proposition 3, here: math.stanford.edu/~dlitt/exposnotes/primes1mod4.pdf –  Todd Trimble Jun 24 '13 at 0:37
    
I will agree that an approach involving arithmetic progressions like that does lead to a prime p with the desired property, and may be shorter if not cleaner than an approach involving Bang or Zsigmondy. I interpret Katz's answer as saying that the "question behind the question" is about primes in such progressions; this intepretation I disagree with, and suggest for self study of this problem an alternative. However, the poster has accepted Katz's answer; perhaps a proof more than understanding is wanted. Gerhard "To Each Their Own Heaven" Paseman, 2013.06.24 –  Gerhard Paseman Jun 24 '13 at 18:08

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