Solving Number Theory Problems: Totient & Primitive Roots

[Seiya]

Homework Statement

Hi guys, i have never taken number theory yet now I am forced to quickly understand it as it was required for a class i signed up. I need help with these problems and would greatly appreciate any hints or help in the right direction. Thanks.

1)Find with proof, all n such that totient function(n)=110

2) Suppose p is a prime and 2 and 3 are both primitive roots mod p . Prove that 6 is not primitive root mod p

Homework Equations

and

The Attempt at a Solution

I know that totient function (p) if p is a prime is p-1, but this doesn't apply here as 111 is not a prime.

I also know i can break up a number n into 2 distinct primes to get a solution but i am puzzled as to how that can help me here.


2)
I know i have to prove that 6 cannot have order of p-1 but don't know how, someone said jacubi number but the professor never mentioned that in the review so i don't think he meant it to be solved that way.

Any help appreciated, thanks.

 

[morphism]

1) It's easy to see that if m divides n, then phi(m) divides phi(n). In particular, for every prime divisor p of n, p-1 divides phi(n)=110. A similar trick applied to p^k (with k>1) will help you determine the only possible prime factorizations of n.

2) Well, we know that there are positive integers a,b,c,d each less than p-1 such that 2^a=3, 2^b=6, 3^c=2 and 3^d=6. Try playing around to see if this implies that it's impossible that the elements 6, 6^2, ..., 6^(p-1) are all distinct. [I haven't tried this.]