Totients, Eulers Phi Function (Unlike Lightning, they always strike at least twice

 

The totient of an integer, N, is the number of integers Less than N which are relatively prime to N, that is, they share no common factors. The symbol for the Totient (by the way, the word is pronounced to rhyme with "quotient"... I didn't know that for a long time) of N is usually the Greek letter Φ. We would write Φ(10)=4, to indicate there are four numbers less than 10 which have no factor in common with the number ten. The four numbers 1,3,7, and 9 are called the totitives of 10. The image at top shows a graph of Φ(n) for each n.

The image above shows the first  thousand values of φ(n). The points on the top line represent φ(p) when p is a prime number, which is p − 1.

Euler showed that if a number n had prime factors p, q, and r; then the totient would equal N(1-1/p)(1-1/q)(1-1/r). It doesn't matter if it has some prime factors more than once, you only use each factor once in the calculation. As an example, 20 factors to 2x2x5, but the number of prime factors is found by 20 (1-1/2)(1-1/5) = 8; with totatives of 1, 3, 7, 9, 11, 13, 17, and 19. The word totient is drawn from the Latin root tot for "so much", and probably to the Greek tosos, "so great". The word tot is still used occasionally for a mark made beside a list to acknowledge receipt, and is sometimes called a "tot mark"(pronounced with a long o, like tote).  In England, and perhaps other English speaking countries, you may still here the phrase toting for the add of addition.  

Euler defined the rule for the number of totients around 1761 in proving what we now call the "Euler-Fermat" theorem. Euler didn't use the word totient. That term was introduced by J J Sylvester,  who had a habit of making up new words for math terms.( J. J. Sylvester (1879) "On certain ternary cubic-form equations," American Journal of Mathematics, 2 : 357–393; Sylvester coins the term "totient" on page 361: "(the so-called Φ function of any number I shall here and hereafter designate as its τ function and call its Totient)")

The name "PHI" for the function was created by Gauss in his Disquitiones arithmeticae .

Here is a list of the first few integers, their totients, and their totitives...

N_____Φ(N)______ totitives

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

The cototient of n is defined as n − φ(n). It counts the number of positive integers less than or equal to n that have at least one prime factor in common with n.

 
There is actually an interesting unproven math theorem about totients. It seems that any number that appears in the sequence of Φ(N) must appear at least twice. It has been proven that if there is an exception, it must have more than 10,000 digits. This is sometimes called the Carmichael Conjecture after R. D. Carmichael.