0
$\begingroup$

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...

$\endgroup$
4
  • $\begingroup$ Is this a homework problem? $\endgroup$
    – user6976
    Jun 19, 2013 at 18:16
  • $\begingroup$ 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 $\endgroup$ Jun 19, 2013 at 18:18
  • $\begingroup$ Voted to close. $\endgroup$
    – user6976
    Jun 19, 2013 at 18:31
  • $\begingroup$ 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. $\endgroup$
    – Todd Trimble
    Jun 24, 2013 at 0:49

1 Answer 1

1
$\begingroup$

$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

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$ Jun 19, 2013 at 19:10
  • $\begingroup$ 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 $\endgroup$
    – Todd Trimble
    Jun 24, 2013 at 0:37
  • $\begingroup$ 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 $\endgroup$ Jun 24, 2013 at 18:08

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