Number Theory

  • Thread starter Seiya
  • Start date
  • #1
43
1

Homework Statement


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



Homework Equations

and

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.


2)
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.
 

Answers and Replies

  • #2
morphism
Science Advisor
Homework Helper
2,015
4
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.]
 

Related Threads on Number Theory

  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
4
Views
938
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
5
Views
862
  • Last Post
Replies
2
Views
965
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
762
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
4
Views
1K
Top