Homework Help

for any integer n greater or equal to one, establish the inequality tau(n) is less then...

user profile pic

skl191 | Student, Undergraduate | eNotes Newbie

Posted March 30, 2012 at 5:13 AM via web

dislike 0 like

for any integer n greater or equal to one, establish the inequality tau(n) is less then or equal to square root n

Tagged with math, number theory

1 Answer | Add Yours

user profile pic

academy633 | College Teacher | Salutatorian

Posted March 30, 2012 at 5:46 AM (Answer #1)

dislike 0 like

The tau function, for a number N, yields the total number of divisors of N.

Here are some examples:
Tau(6) = 4 The divisors of 6 are: 6, 3, 2, 1
Tau(9) = 3 The divisors of 9 are: 9, 3, 1
Tau(12) = 6 The divisors of 12 are: 12, 6, 4, 3, 2, 1

There is no easy way to relate tau(N) with N to determine if N is a perfect number as in the way sigma(N) = 2N implies N is a perfect number. However, it will later be shown that for a perfect number of the form (2^x - 1)*(2^(x -1)), tau((2^x - 1)*(2^(x -1))) = 2x.

Like the sigma function, you don't need to list the divisors of N in order to calculate tau(N). The following three properties of the tau function make it simple to calculate tau(N) for any natural number N.

-For a prime number P, tau(P) = 2
Again, by definition, any prime number only has two divisors: itself and one.
-For a prime number P raised to any power n, tau(P^n) = n + 1
This follows from observing the that the geometric sequence -- 1, P^1, …, P^(n-1), P^(n) -
Has 'n' terms with P as a factor and one term that is simply 1.
-For relatively prime numbers A and B, tau(A*B) = [tau(A)]*[tau(B)]
Tau is also a multiplicative function.

Thus, to find tau(N) for any natural number N, simply rewrite N in it's prime factored form and apply the previously stated properties of the tau function. For example:
Tau(36) = tau(4*9) = [tau(2^2)]*[tau(3^2)] = (2+1)*(2+1) = 9
Indeed, 36 has nine divisors: 36, 18, 12, 9, 6, 4, 3, 2, and 1.

If you factor a number into its prime power factors, then the total
number of factors is found by adding one to all the exponents and
multiplying those results together. Example: 108 = 2^2*3^3, so the total number of factors is (2+1)*(3+1) = 3*4 = 12. Sure enough, the factors of 108 are 1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54, and 108. This happens because to be a factor, a number must have the same primes, and raised to the same or lower powers. Each factor of 108 must be a power of 2 times a power of 3, and the exponent of 2 can be 0, 1, or 2, and the exponent of 3 can be 0, 1, 2, or 3. There are three choices for the exponent of 2 and 4 choices for the exponent of 3, for a total of 3*4 = 12 possible choices. Each gives a different factor, so there are 12 factors.

Since the number of factors of a natural number is less than or equal to the square root of the number, tau(n)<=sqrt(n).

 

Sources:

Join to answer this question

Join a community of thousands of dedicated teachers and students.

Join eNotes