Burt Kaliski Jr. (@modulomathy)

#math trivia for #February29: #60 shares a prime factor with 44 smaller integers. Which 16 smaller integers are relatively prime to 60?

The 16 smaller (positive) integers that don’t share a prime factor with 60 are:

1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 57 .

The list includes 1, all the primes less than 60 that don’t divide 60, and the one product of other primes on the list, 49.

The number of smaller integers relatively prime to a given number N is defined by Euler’s totient function, denoted phi(N). If N is a prime or prime power p^a, then phi(N) is (p-1)*p^(a-1). (The case where N is prime corresponds to a = 1, so the totient function evaluates to N-1.) And if N is the product of prime powers, then phi(N) is the product of the totient functions of each of the prime power factors. (The latter property relates to the **cyclic decomposition** of N: integers modulo N correspond to different possible combinations modulo the prime power factors.)

For N = 60, there are three prime power factors: 2^2, 3, and 5. Their totient functions are 1*2, 2 and 4, so phi(N) is 1*2*2*4 = 16 as expected.

### Like this:

Like Loading...

*Related*