restart.'s blog

Primitive root modulo n
By restart., history, 9 years ago, In English

Given a number n as input how to find the (all the primitive roots of n) % n if n is prime. please give me some hint how can i calculate the primitive roots.. TIA.

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
9 years ago, # |
  Vote: I like it +22 Vote: I do not like it
  1. Find the smallest one. Let's call it g.
  2. gi will be a primitive root if and only if i and φ(n) are coprime.
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    in this spoj problem how can i find the (product all the primitive roots of n) % n without generating all the primitive roots of n ? any hint please...

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 3   Vote: I like it +3 Vote: I do not like it

      For your question: sum of numbers relatively prime and less than N is Nφ(N) / 2. (Because if gcd(x, N) = 1 then gcd(N - x, N) = 1). But since for any primitive root g, gi is primitive root if and only if gcd(i, φ(N)) = 1. So their product will be gφ(φ (N)) * φ (N) / 2 which is ( - 1)φ(φ(n)) since g is primitive root. For you particular case it is -1.

      → Reply