Loading ...
Sorry, an error occurred while loading the content.

Help needed

Expand Messages
  • hl59126
    Let q a positive integer and 1
    Message 1 of 8 , Feb 4 9:05 AM
    • 0 Attachment
      Let q a positive integer and 1<=r<=q. Is there a theorem that tells
      us how many integers a, 1<=a<=q, verify a^r=1 mod(q)?

      I have found that:
      (1) if q is prime or a power of a prime p, i.e. q=p^x, then there
      are GCD(r,EulerPhi(q)) integers a that satisfy a^r=1 mod(q).
      (2) if q is a product of two powers of primes p' and p'', i.e.
      q=p'^x p''^y, then there are GCD(r,Carmichael(q))*GCD(r,Phi
      (q)/Carmichael(q)) integers a that satisfy a^r=1 mod(q).

      Are these results correct and can we generalize to any integer q?

      Thanks for your help
      Hervé
    Your message has been successfully submitted and would be delivered to recipients shortly.