define Euler's function
Answers
Answer:
The Euler's totient function, or phi (φ) function is a very important number theoretic function having a deep relationship to prime numbers and the so-called order of integers. The totient φ(n) of a positive integer n greater than 1 is defined to be the number of positive integers less than n that are coprime to n. φ(1) is defined to be 1. The following table shows the function values for the first several natural numbers:
n φ(n) numbers coprime to n
1 1 1
2 1 1
3 2 1, 2
4 2 1,3
5 4 1,2,3,4
6 2 1,5
7 6 1,2,3,4,5,6
8 4 1,3,5,7
9 6 1,2,4,5,7,8
10 4 1,3,7,9
11 10 1,2,3,4,5,6,7,8,9,10
12 4 1,5,7,11
13 12 1,2,3,4,5,6,7,8,9,10,11,12
14 6 1,3,5,9,11,13
15 8 1,2,4,7,8,11,13,14
Can you find some relationships between n and φ(n)? One thing you may have noticed is that