Question

Find all the values of n such that phi(phi(n)) = 1. How does this relate to primitive roots and what does this tell us?

Answer 1

suppose \(n\) has a primitive root, then what can you tell about the number of primitive roots of \(n\) ?

Answer 2

I'm not sure? It has at least 1?

Answer 3

it should be easy, just wok it using the result from previous problem

Answer 4

let \(r\) be a primitive root of \(n\), then all the positive integers less than \(n\) that are relatively prime to \(n\) are given by
\[r^1, r^2, r^3\ldots, r^{\phi(n)}\]

yes ?

Answer 5

Right that's just the def. of primitive root.

Answer 6

remember that a primitive root of \(n\) has order \(\phi(n)\)

Answer 7

how many integers in above list have order \(\phi(n)\) ?

Answer 8

you want to work out : \[\dfrac{\phi(n)}{\gcd(\phi(n), a)} = \phi(n)\]

Answer 9

which is same as \(\gcd(\phi(n),a) = 1\)

how many positive integers less than \(\phi(n)\) satisfy above relation ?

Answer 10

in other words, how many positive integers less than \(\phi(n)\) are relatively prime to \(\phi(n)\) ?

Answer 11

Okay, I'm following what you're saying, but not how it relates to this problem.

Answer 12

There are exactly \(\phi(\phi(n))\) positive integers less than \(\phi(n)\) that are relatively prime to \(\phi(n)\), yes ?

Answer 13

Right

Answer 14

that means there are exactly \(\phi(\phi(n))\) primitive roots for any given integer \(n\), if it has a primitive root.

Answer 15

Oh okay. I think I see

Answer 16

finding all the values of \(n\) such that \(\phi(\phi(n))=1\) is same as finding all the integers having exactly one and only one primitive root.

Answer 17

Right that makes sense. Thank you again for the help.

Answer 18

I have 1 other problem while you're still here if you wouldn't mind taking a look?

Answer 19

I'll try, post..

Answer 20

It's pretty similar to a problem in the book, and I followed the steps pretty closely, but when I plug the problem in to wolfram alpha it returns a different answer

Answer 21

So we're given this indice table

16,14,1,12,5,15,11,10,2,3,7,13,4,9,6,8

Answer 22

for 1-16 mod 17

Answer 23

and are asked to find all solutions to 9x^8 = 8 mod 17

Answer 24

is the primitive root 3 ?

Answer 25

Yes

Answer 26

Right

Answer 27

\[9x^8 \equiv 8 \pmod {17}\]

take discrete logarithm both sides

Answer 28

So I took the ind3 on both sides and got

ind3(9x^8) = 0 mod 16
14 + 8ind3x = 0 mod 16

Answer 29

But that doesn't yield what wolfram alhpa is giving for the original problem

Answer 30

how did u get 14 ?

Answer 31

(and it has the correct answers for the book problem similar to this one)

Answer 32

I used a theorem and broke ind3 (9x^8) in to
ind3(9) + ind3(x^8)

ind3(9) =14

Answer 33

index of 9 is 2 right ?
because 9 = 3^2

Answer 34

Oh wait. I think I was just reading the table backwards

Answer 35

14 is the index of 2 :

2 = 3^14

Answer 36

Wow I feel really dumb. Okay that was probably what the issue was, thank you.

Answer 37

remember

index = logarithm = exponent

Answer 38

2 is the index of 9 relative to primitive root 3 because
\[\large 9 \equiv 3^{\color{blue}{2}}\pmod{17}\]

Answer 39

Right. I'm not quite sure what I was thinking there, thank you.

Answer 40

Okay yeah, the problem is looking a lot nicer now that I'm going through and correcting it. Thanks a ton for all your help today.

Answer 41

np:)