Блог пользователя restart.

Primitive root modulo n
Автор restart., история, 9 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится
  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.
→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

      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.

      → Ответить