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...
4
-
$\begingroup$ Is this a homework problem? $\endgroup$– user6976Commented 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$– Gerhard PasemanCommented Jun 19, 2013 at 18:18
-
$\begingroup$ Voted to close. $\endgroup$– user6976Commented 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 TrimbleCommented Jun 24, 2013 at 0:49
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
$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
answered Jun 19, 2013 at 18:31
-
$\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$ Commented 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$ Commented 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$ Commented Jun 24, 2013 at 18:08