What is the role of the prime number in the Euler totient Function? Find the GCD of 12 and 16 using the Euclidean algorithm.

Question

Suresh Chand · Accepted Answer

Euler’s Totient function Φ (n) for an input n is the count of numbers in {1, 2, 3, …, n-1} that are relatively prime to n, i.e., the numbers whose GCD (Greatest Common Divisor) with n is 1. It is also called an arithmetic function. Two things are important for an application or use of Euler's totient function. One is that the gcd formed from the given integer 'n' should be multiplicative. The other is that the numbers of gcd should be the prime numbers only. The integer 'n' in this case should be more than 1. Calculating the Euler's totient function from a negative integer is impossible. The principle, in this case, is that for Φ(n), the multiplicators called m and n should be greater than 1. Hence, denoted by 1 < m < n and gcd (m, n) = 1. Sign Φ is the sign used to denote the totient function. Euclidean algorithm for GCD: a = q0 x b + r0 or, b = q1 x r0 + r1 and so on Here, a = 16 and b = 12 or, 16 = 1 x 12 + 4 or, 12 = 3 x 4 + 0 Hence, the GCD of 12 and 16 using the Euclidean algorithm is 4.

What is the role of the prime number in the Euler totient Function? Find the GCD of 12 and 16 using the Euclidean algorithm.

Leave your Answer:

Hits Counter

Question

What is the role of the prime number in the Euler totient Function? Find the GCD of 12 and 16 using the Euclidean algorithm.

Leave your Answer: