Re: order of an element

In article <1138567184.210755.212700@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
"Chip Eastham" <hardmath@xxxxxxxxx> writes:
>
>alihandam@xxxxxxxxx wrote:
>> What is the order of 2 in the group U(p) ,where u(p)the group of units
>
>Hi, Alihandam:
>
>I think this is essentially the same question you posted over in
>sci.math.symbolic. Because of the slight change in wording and the
>context of your earlier post on knowing order in the multiplicative
>group of Z/(p^k)Z of an element with known order n in Z/pZ, p an odd
>prime, I thought you were asking simply if n = 2 is possible, ie.
>can an element have order 2. Thus I asked you to verify that 2 has
>order 2 mod 3.
>
>The question of what order residue 2 has in Z/pZ, p an odd prime,
>is not trivial in general. Special cases, like Mersenne & Fermat
>primes, are easily solved of course.

Well at least you appear to understand the question - I am not sure
that I do!

If we are talking about the difficulty of calculating the order, then,
I would guess that the difficulty is about the same as factorizing p-1.
If you can do that, then you calculate the order of 2, or of any other
residue mod p, in polynomial time.

Derek Holt.

>Here is one measure of difficulty in asking what the order of
>2 is for general primes p: When is the order p-1?
>If a 1927
>conjecture of Artin is true, this occurs a bit less than two
>out five times. However:
>
>It's a well-known open question as to whether residue 2 is a
>generator of this cyclic group for infinitely many odd primes p.
>I say it is open, because it has not been proven specifically
>that 2 is a primitive root for infinitely many primes p. However
>assuming the Generalized Riemann Hypothesis, Hooley showed in 1967
>that it is so (more generally Artin's conjecture, on the density
>of primes p for which non-square a > 1 is a primitive root). In
>1987 Heath-Brown showed, without dependence on GRH, that of any
>three distinct primes, at least one of them is a primitive root
>for infinitely many primes p. So it is unlikely, but conceivable,
>that here 2 is one of at most two exceptions to a general rule!
>
>If you wish to understand this material for yourself, you should
>perhaps master the theorem that says the multiplicative group
>of Z/(p^k)Z is cyclic when p is an odd prime.
>
>
>regards, chip
>


.

Relevant Pages

  • AP-Prime-Generator APPG Re: possible Riemann Hypothesis proof; #137;
    ... rather strange since Euclid's Number in Euclid's Infinitude of Primes ... have devised a Generator of primes, all the primes in that time period. ... So it looks ideal for the Moebius function ... of the Sieve of Eratosthenes. ...
    (sci.math)
  • Re: Group generator
    ... What is the generator of that group? ... A "primitive root g of a prime p is a number such that the residudue ... Hooley proved this assuming the extended Riemann ... many g. Heath-Brown proved that for at most two exceptional primes ...
    (sci.math)
  • Re: order of an element
    ... The question of what order residue 2 has in Z/pZ, p an odd prime, ... primes, ... generator of this cyclic group for infinitely many odd primes p. ... of primes p for which non-square a> 1 is a primitive root). ...
    (sci.math)
  • Re: algebraic question
    ... >Let p,q be large primes with p=2q+1. ... Let g be a generator of a group G ... that g is a generator of the multiplicative group of the ring Z_p. ...
    (sci.math)
  • Re: How can I speed up a script that iterates over a large range (600 billion)?
    ... "primes" generator checks to determine whether each number is prime is ... # odd multiple of p; p+p is the increment to get to the next ... # Mark odd nonprimes within each of the requested ranges. ...
    (comp.lang.python)