Proving Primitive Roots of Odd Numbers Modulo pm

In summary, the conversation discusses a question about proving that some odd numbers are primitive roots modulo pm for each odd prime p and each positive integer m. The participants express confusion over the wording of the question and discuss possible interpretations. They also mention a potential solution to the problem and thank each other for their input.
  • #1
Gear300
1,213
9
Hello friends from afar.

I ran into what I felt to be somewhat of an odd question:

Prove that some odd numbers are primitive roots modulo pm for each odd prime p and each positive integer m.

It feels dodgy given that any odd number n = p1p2 ⋅⋅⋅ ps cannot be a primitive root of a prime number involved in its prime factorization. I just needed to be sure. Many thanks.
 
Physics news on Phys.org
  • #2
The wording is quite disturbing and I stumbled upon the same argument as you. "some odd numbers" looks strange.
It would make more sense the other way around (or I didn't get the point either):

For each odd prime ##p## and each positive integer ##m## prove that some odd numbers are primitive roots modulo ##p^m.##
 
  • #3
Indeed. I'm guessing yours is how it's done, since it seems like the original could be semantically interpreted like that. Thanks.
 
  • #4
Gear300 said:
Hello friends from afar.

I ran into what I felt to be somewhat of an odd question:

Prove that some odd numbers are primitive roots modulo pm for each odd prime p and each positive integer m.

It feels dodgy given that any odd number n = p1p2 ⋅⋅⋅ ps cannot be a primitive root of a prime number involved in its prime factorization. I just needed to be sure. Many thanks.
In future posts, please don't delete the homework template...
 

Related to Proving Primitive Roots of Odd Numbers Modulo pm

What is a primitive root of an odd number modulo pm?

A primitive root of an odd number modulo pm is an integer g that, when raised to any power between 1 and p-1, never produces a number congruent to 1 modulo pm.

Why is it important to prove the existence of primitive roots of odd numbers modulo pm?

Proving the existence of primitive roots is important because it allows for the use of efficient algorithms in modular arithmetic, such as the discrete logarithm problem, which has important applications in cryptography.

What is the process for proving the existence of primitive roots of odd numbers modulo pm?

The process involves finding a value of g that satisfies certain conditions, such as being relatively prime to pm and having a certain order modulo pm. Once this value is found, it must be shown that it satisfies all the necessary conditions for being a primitive root.

Are there any specific techniques or methods used in proving primitive roots of odd numbers modulo pm?

Yes, there are several techniques and methods that can be used, such as the index calculus method, the Pohlig-Hellman algorithm, and the Tonelli-Shanks algorithm. These methods involve a combination of number theory, algebra, and computer science.

Is it possible for an odd number modulo pm to not have a primitive root?

Yes, it is possible for an odd number modulo pm to not have a primitive root. This is known as a non-primitive residue and can occur when p-1 has a large number of prime factors. In this case, it may be necessary to use a different approach in modular arithmetic.

Similar threads

Replies
5
Views
934
  • Science and Math Textbooks
Replies
1
Views
775
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
598
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Precalculus Mathematics Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
13
Views
2K
  • Calculus and Beyond Homework Help
Replies
16
Views
2K
Back
Top