Can composite numbers have primitive roots?

Not every composite number has a primitive root, but some, like 6 and 10, do.

What is the primitive root of a number?

A primitive root mod n is an integer g such that every integer relatively prime to n is congruent to a power of g mod n. That is, the integer g is a primitive root (mod n) if for every number a relatively prime to n there is an integer z such that. a \equiv \big(g^z \pmod{n}\big). a≡(gz(modn)).

How do you find the primitive roots?

1- Euler Totient Function phi = n-1 [Assuming n is prime] 1- Find all prime factors of phi. 2- Calculate all powers to be calculated further using (phi/prime-factors) one by one. 3- Check for all numbered for all powers from i=2 to n-1 i.e. (i^ powers) modulo n. 4- If it is 1 then ‘i’ is not a primitive root of n.

Does 12 have primitive roots?

Candidates for primitive roots are 1, 5, 7 and 11. ϕ(12)=ϕ(22)ϕ(3)=4. ord121=1,ord125=2,ord127=2,ord1211=2. None of these has ϕ(12)=4, thus number 12 has not primitive root.

What is the primitive root of 4?

primitive roots exist for the modulus 4. For m=4 we have ϕ(4)=2. If we suppose that gcd(a,m)=1 then a is any odd number. So we must show that a2≡1 (mod m) is possible and a1≡1 (mod m) is not.

Does 32 have primitive roots?

But the powers of 2 (n =16, 32, 64) do not have primitive roots; instead, the powers of 5 account for one-half of the odd numbers p modulo n, namely those which are p ≡ 5 or 1 (mod 8), and their negatives −p modulo n account for the other half.

How do you find the primitive root of 11?

The primitive roots are 2, 6, 7, 8 (mod 11). To check, we can simply compute the first φ(11) = 10 powers of each unit modulo 11, and check whether or not all units appear on the list.

What is the primitive root of 7?

Primitive Root

6	5
7	3, 5
9	2, 5
10	3, 7
11	2, 6, 7, 8

How do you find the primitive root of 25?

Find primitive roots of 4, 25, 18. For 4, the primitive root is 3. For 25, I would first try 2. The powers of 2 are 2, 4, 8, 16, 7, 14, 3, 6, 12, 24 = −1, so 210 ≡ −1 and ord25 2 = 20 = ϕ (25).

What are the primitive roots of 25?

Table of primitive roots