# Number theory: primitive roots

• timjones007
In summary, to find a primitive root modulo 101, you must find an integer that is not congruent to 1 or -1 mod 101. To find integers modulo 101 that are 5th or 7th powers, you must find all m such that there exists x such that x^5 \equiv m \pmod{101} or x^7 \equiv m \pmod{101}.
timjones007
Find a primitive root modulo 101. What integers mod 101 are 5th powers? 7th powers?

-I tested 2.
-2 and 5 are the prime factors dividing phi(101)=100 so i calculated 2^50 is not congruent to 1 mod 101 and 2^20 is not congruent to 1 mod 101.
-Therefore 2 is a primitive root modulo 101

I guess this means to find find all m such that there exists x such that
x^5 = m (mod 101)

If this is the case, then how do I find these solutions?
I found that the congruence x^5 = 1 (mod 101) has gcd(5,100)=5 solutions. I also know that 2^100 = 1 (mod 101) so that ((2^20)^5) = 1 (mod 101).
I don't know where to go from there.

Last edited:
To ask what integers modulo 101 are 5th or 7th powers does not mean to find all $$x$$ such that $$x^5 \equiv 1 \pmod{101}$$ (or 7), but to find all $$m$$ such that there exists $$x$$ such that $$x^5 \equiv m \pmod{101}$$ (or 7).

## 1. What is a primitive root in number theory?

A primitive root in number theory is a number that, when raised to certain powers, generates all possible remainders modulo a prime number. In other words, it is a number that has no smaller number with the same property.

## 2. How do we find primitive roots?

There is no known formula or algorithm for finding primitive roots. However, there are some known methods, such as trial and error, to find primitive roots for small prime numbers.

## 3. What is the significance of primitive roots in number theory?

Primitive roots have many applications in number theory, such as in cryptography, coding theory, and prime factorization algorithms. They also play a crucial role in understanding the structure of the multiplicative group of integers modulo a prime number.

## 4. Can a number have more than one primitive root?

No, a prime number can only have one primitive root. However, composite numbers can have multiple primitive roots, but the number of primitive roots is always less than or equal to the number of distinct prime factors of the composite number.

## 5. Are primitive roots unique?

Yes, primitive roots are unique for a given prime number. This means that for a specific prime number, there can only be one primitive root that satisfies the necessary conditions.

Replies
2
Views
2K
Replies
4
Views
1K
Replies
3
Views
2K
Replies
1
Views
2K
Replies
2
Views
828
Replies
2
Views
1K
Replies
1
Views
5K
Replies
3
Views
1K
Replies
16
Views
1K
Replies
3
Views
1K