Solving Number Theory Problems: Totient & Primitive Roots

In summary, the student is seeking help with two number theory problems, one involving the totient function and the other involving primitive roots. The student is aware of some general properties of the totient function and is considering breaking the number n into two distinct primes to solve the first problem. For the second problem, the student is unsure how to approach it and is considering using Jacobi numbers, but is not confident in this method. The conversation ends with a suggestion to play around with the given elements to see if a solution can be found.
  • #1
Seiya
43
1

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.
 
Physics news on Phys.org
  • #2
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 to Solving Number Theory Problems: Totient & Primitive Roots

What is the purpose of studying Number Theory?

Number Theory is a branch of mathematics that deals with the properties of whole numbers. It has many practical applications in cryptography, computer science, and other fields. It also helps us understand the fundamental nature of numbers and patterns in the world around us.

What is the totient function and how is it calculated?

The totient function, denoted by φ(n), is a mathematical function that counts the number of positive integers less than or equal to n that are relatively prime to n. In other words, it gives the number of numbers that are coprime with n. It can be calculated using the formula φ(n) = n * (1-1/p1) * (1-1/p2) * ... * (1-1/pk), where p1, p2, ..., pk are the prime factors of n.

What is a primitive root and how is it related to the totient function?

A primitive root of a positive integer n is an integer g such that every positive integer coprime with n can be written as a power of g modulo n. In other words, g is a generator of the multiplicative group of integers modulo n. The totient function is related to primitive roots through Euler's theorem, which states that if g is a primitive root of n, then gφ(n) ≡ 1 (mod n).

How can solving number theory problems involving totient and primitive roots be useful?

Solving number theory problems involving totient and primitive roots can be useful in various fields such as cryptography, where these concepts are used to develop secure encryption algorithms. They also have applications in coding theory, where primitive roots are used to construct error-correcting codes. Additionally, studying these concepts can help improve problem-solving skills and develop a deeper understanding of the properties of numbers.

What are some common techniques for solving number theory problems involving totient and primitive roots?

Some common techniques for solving number theory problems involving totient and primitive roots include using Euler's theorem, Fermat's little theorem, and the Chinese remainder theorem. Other techniques include using modular arithmetic, prime factorization, and the properties of primitive roots such as order and index. It is also helpful to have a good understanding of basic number theory concepts and properties.

Similar threads

  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Science and Math Textbooks
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
Replies
5
Views
984
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
16
Views
2K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
3K
Back
Top