1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Number Theory

  1. Feb 10, 2008 #1
    1. The problem statement, all variables and given/known data
    Hi guys, i have never taken number theory yet now im 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

    2. Relevant equations and 3. The attempt at a solution

    I know that totient function (p) if p is a prime is p-1, but this doesnt 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.

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

    Any help appreciated, thanks.
  2. jcsd
  3. Feb 11, 2008 #2


    User Avatar
    Science Advisor
    Homework Helper

    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.]
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook