How to Calculate Totient

Bignum Euler developed the concept of the "totient," or the number of "coprimes" that a number has. "Coprimes" are integers less than a given integer "n" that share no factors in common with that integer. For example, the number 6 has 3 and 2 as factors. The only number less than 6 with no common factors is 5, so the totient of 6 would be 1. There is a formula for calculating the totient (shown by the Greek letter "phi") for any integer.

Instructions

    • 1

      Subtract 1 from the number "n" if "n" is prime to get the totient. A prime number will not share any factors with a number less than it, so all numbers lower than it will be coprimes.

    • 2

      Factor the number into its prime factors, if the number is not prime. For example, 8 = 2 * 2 * 2. 75 = 5 * 5 * 3.

    • 3

      Plug the distinct prime factors into this formula:

      phi(n) = n(1-1/p1)(1-1/p2)...(1-1/p(m)), where there are "m" prime factors of "n." For 64 (2*2*2*2*2), there is only one distinct prime factor (2). So the formula works like this:

      phi(64) = 64(1-1/2) or 64(1/2) or 32. There are 32 numbers less than 64 that share no common factors with it (all of the odd numbers).

      phi(60) works differently. 60 = 2 * 3 * 5, so the formula works like this:

      phi(60) = 60(1-1/2)(1-1/3)(1-1/5) = 60(1/2)(2/3)(4/5) = 480/60 = 8.

      With all of those prime factors, there are only eight integers less than 60 that share no common factors with it.

Learnify Hub © www.0685.com All Rights Reserved