find Find all values of m for which = 2. Find four values of m for which = 6. Fi

Question

find

Find all values of m for which = 2. Find four values of m for which = 6. Find five values of m for which = 12. Proposition 1. If there exists a primitive root modulo m, the number of such primitive roots in the interval . Proof. Let the integer a be a primitive root modulo m. Hence a. a'; a3.... a?" are a system of representatives of the congruence classes modulo m that are relatively prime to m. It is not hard to check that among them, all powers a with 1 j (m) which are lower, and hence are not primitive roots. We have obtained (m)) primitive roots, and they all have different residues modulo m. Hence there are (( m)) different primitive roots b -a1(mod m) in the interval

Explanation / Answer

phi(m)=2

Let m = 2^a 3^b is the only possiblity here since in the decomposition we need p-1 | 2 for p a prime factor
Otherwise phi(2^a) = {1,1,2} phi(3^b)={1,2} for a=0,1,2 and b=0,1
So the solution are a=0,b=1, a=1,b=0, a=1,b=1: m=3 or m=4 or m=6

phi(m)=6
p-1 | 6 => p=2,3,7
So m = 2^a 3^b 7^c

phi(2^a) = {1,1,2,4,8} (a=0,1,2,3)
phi(3^b) = {2,6,9} (b=1,2,3)
phi(7^d) = {6} (d=1,2)

We see it works with a=0,a=1 and d=1 (m=7 and m=14) and a=0,a=1 and b=2 (m=9 and m=18)

Which leads to the solution : 7,9,14,18

phi(m)=12

If you decompose like before, you need the primes such that p-1 | 12 : p=3,5,7,13 are the only possiblity
13 is a solution as well as 13*2 and we are working with numbers m = 2^a 3^b 5^c 7^d
So phi(m) = phi(2^a) phi(3^b) phi(5^c) phi(7^d)
Let's do it by hand here for values of each <=12
phi(2^a) = {1,1,2,4,8} (a=0,1,2,3)
phi(3^b) = {1,2,6} (b=0,1,2)
phi(5^c) = {1,4} (c=0,1)
phi(7^d) = {1,6} (d=0,1)

We see the possibility are 2*6 which can be with a=2,b=2 or a=2,d=1 or b=1,d=1 which are :
2^2*7=28 or 2^2*3^2=36 or 3*7=21
Which leads to the solution : 13,21,26,28,36

I let you check i didn't forget one solution :-)

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.