Def :
For n>=1 , let Q(n) denote the number of positive integers not exceeding n that are relatively prime to n .
Examples :
Q(1) = 1
Q(2) = 1
Q(3) = 2
Q(4) = 2
Q(5) = 4
Q(6) = 2
Q(20) = 8
Q(100) = 40
Theorem :
Let n belongs natural numbers except 1 . Then n is prime if and only if Q(n) = n-1 .
Ex : Q(19) = 18
Theorem :
Let p be prime , n belongs natural numbers . Then
Q(p^n) = p^n - p^n-1
Ex : Q(9) = Q(3^2) = 3^2 - 3^1 = 6
Theorem :
Let m,n belongs natural numbers with GCD(m,n) = 1 .
Then Q(m*n) = Q(m) * Q(n)
Ex : Q(10) = Q(2) Q(5)
= (2^1 -2^0)*(5^1 - 5^0)
= (2-1)*(5-1)
= 1*4
= 4
Theorem :
If n is odd then Q(n) = Q(2n)
Tags:
Other