Chapter 1 part B

 

1.8. Functions and

1.8.1. Definition

If "n" is integer and positive, then we show the number of positive divisors of "n" by and the sum of all of the positive divisors by.

In the following theorem, we obtain a formula for calculation  and by using the decomposition into the prime factors.

1.8.2. Theorem

Suppose , therefore:

And also:

Proof: suppose  is a positive divisor of "n". For each "i" we have , then, for all "", there are  different selections.
(In fact . Therefore, we can select the powers of  in different ways. Then:

For calculating , at first, note the following product:

This multiplication is equal to the sum of all possible products of so that .

But family of all of these products is exactly equal to the sum of all of the positive divisors of "n" therefore . For completing the proof, at first we consider:

(For prowling, it is enough to multiply  by )

Therefore, we have:

1.8.3. Remark

The function  and  are examples of number theory functions. They have common and very important qualities. Both of  and are multiplicative, it means for both of two coprime numbers "m" and "n", we have:

Generally, the function "f ", which is defined on set of positive integer number, is called multiplication if and only if for all "n" and "m" that:

For proving multiplicative of and, we can gain some results directly and with some calculations and with use of some formulas.

Function-Euler is another important multiplicative function that we acquaint it here.

1.8.4. Conclusion

 If "P" be a prime number:

 (: Euler's Function)

Proof. This assertion is clear for "k=1". Since if "P" be prime:

If , since "P" is prime, then the numbers which aren’t coprime with are as follow:

Therefore, the number of numbers aren’t coprime with "Pk"  is equal to "Pk-1" and the other numbers are coprime with to "Pk". The number of them is equal to ""or  that here, assertion is proved.

1.8.5. Result

We know that if (a, b, c,…) =1, then:

Therefore, we can write for (p, q, r, … are prime factors):

So:

For example, the number of numbers smaller than 100 that are coprime with it, is calculated with below method:

 


 

 

1.9. Perfect numbers

1.9.1. Definition

We call integer number n>0 as Perfect, if it equals to sum of divisors smaller than itself. Therefore, "n" is perfect if and only if  that  is sum of divisor of "n" (with itself). Mental principle of perfect numbers roots back to ancient Greece's times and we must search it in history. Greeks had a lot of secret properties for these numbers. Greeks mathematicians had very tendency to these numbers. Although they knew only 4 perfect numbers in Euclid themes that are: 6, 28, 496 and 8128.

In spite of this little and deficit information, they guessed even perfect numbers finish with 6 or 8 that 5th and 6th number of perfect numbers are 33550336 and 8589869056 that both of them finish to "6". Of course this result is correct that perfect number finish with 6 or 8. Euclid mentioned below method for calculating perfect numbers in book "preliminaries".

1.9.2. Theorem’s Euclid

Suppose  be prime, then  is a perfect number.

Proof. Suppose  that . Since "p" is prime, then divisors of  are in or  form clearly .

Therefore:

 

 

Therefore "N" is a perfect number.

Natural question that propounded is that we ask:

Is the inverse of this Euclid theorem established? Are all of perfect numbers, in mentioned form in (1.9.2)?

Almost, 2000 years after that, Euler answered it.

1.9.3. Remark

 Euclid algorithm isn’t an organized method for calculation of highest common divisor of two numbers. Euclid expressed and proved this algorithm in his book "Preliminaries". Of course, may be this algorithm was known before Euclid, below lemma is key of understanding Euclid algorithm.

1.9.4. Lemma

 Suppose "m" and "n" are integer numbers that both of them aren’t "o" together. So, for every correct number:

1.9.5. Theorem’s Euler

All of the even perfect numbers are in form which  is a prime number.

Proof. Suppose "N" is an even perfect number. At that rate .

Put , which  and "m" is a prime number.

Since and is a multiplicative function, we will have:

With solving the equivalence , with respect to  we will have:                                   

      (2)

Therefore, is a integer number. Then both "m" and   are divisors of "m". Because,, from this we know that "m" and  are only the positive divisors of "m". So, means   and in the result "m" is a prime number.

Here, we remember two problems about perfect numbers.

The first of them is this odd perfect number. So, we know if there is an odd perfect number, it must be greater than 10300 and therefore it has 8 distinctive prime factors at least.

With these descriptions, we can result that there isn’t odd perfect number.

The second problem is none response until now that, Are the number of perfect numbers infinite? In the primary ages they have known four perfect numbers which considered before.

But the fifth of these numbers hasn’t been discovering until 15th century, till now, we know 42 even perfect number (2005). The first, 21 of them have been discovered to 1900.

For example, the known perfect number 2859432 (2859433-1) is an ogre of mathematics with 517430 Digit almost. Then existing infinite perfect numbers remain an open problem till now. Now after determination the highest prime number of 21 century, in fact the highest perfect number calculates also:

The highest known perfect = 225964950(225964951-1) number of year 2005.

We finish this section with mention some important theorem about prime numbers like Bertrand’s principle. We know that Bertrand principle propound existing of prime numbers between numbers "n" and "2n".

Joseph Bertrand propounded his guess in 1845 and searched it for numbers between "1" and "3,000,000". But Russian mathematician Chebyshev solved it logically. Although its proof is easier than prime numbers but "1" remember.

Remember only its stronger results.

1.10. Bertrand’s principle and theorems of

Chebyshev, Dirichlet and Poisson 

1.10.1. Bertrand’s principle

For every n>1, a prime number exists between "n" and "2n". Stronger result of Bertrand principle is:

1.10.2. Result

If "n>5", then at least two different prime numbers exist between "n" and "2n". Another obvious result is that inequality "" results

1.10.3. Generalization

In 1892 Bertrand’s principle extended by James Joseph Sylvester in below from:

If "m" and "n" be two positive integer numbers and m>n, then at least, one of numbers m+1, m+2, …, m+n   has a prime divisor greater than "n". (With thesis that m=n+1, Bertrand’s principle is resulted)

Another important theorem about prime numbers is Dirichlet’s theorem that if "a" and "b" (a0) be coprime, then infinite prime numbers exist in "ak+b" form that kn. It is obvious that if "a" and "b" have common factor greater than "1", then for every integer number "k", "ak+b" is a compound number.

For example, existing of infinite prime numbers in "4k +3" and "4k +1" form is obvious.

1.10.4. Dirichlet’s theorem

Suppose "", "" and . Therefore infinite integer number "k" exists. So that "ak+b" is "a" prime number.

Dirichlet’s theorem is the first important application of analytic methods in number theory. In fact, Dirichlet’s theorem and prime numbers theorem are two important theorems of primary theory of numbers that are solved by analytic methods. For both of these two theorems, primary proofs exist that it doesn’t use deep theorems of functions theory. But expressing of their proof is so hard that it isn’t in frame of this book.

Now, we propound a combination of prime numbers theorem and Dirichlet’s theorem:

1.10.5. Poisson’s theorem

Suppose "a" is a positive number and (a, b) =1 and it defines is the number of prime numbers in ak+b form and smaller than "x". Then we can approach quotient of  sufficiently to, if "x" is great sufficiently.

1.10.6. Remark

Limit of doesn’t depend on choosing "b" until "a" and "b" are coprime. Quotient tends to a limit that only depends on "a".

1.10.7. Result of theorem (1.10.5)

If "" and "" are sets of digits so that en are odd and "", then there will be infinite prime numbers so that start with digits "" and finish to "". Theorem (1.10.5) has very beautiful interpolation that probably it doesn’t see obviously from above propositions.

Fore example, if "", then it is resulted from theorem (1.10.5) that (since "") half of prime numbers are in "4k+1" form and another half is in "4k+3" form. (Exactly, we can approach the ratio of "" to ½ for "x" that is sufficiently great). Therefore, we can find out from theorem (1.10.5) that if "", then a quarter of all prime numbers are in "8k+5" form and the last quarter in "8k+7" form. Generally, with supposing "", if "" (mod a) then "n" is in form if and only if "n" is in "" form.

So, we can only calculate different values for "n" So that "a" and "b" are coprime. Therefore, it is resulted from theorem (1.10.5), that for every permissible value of "b", sequence of the numbers "a, a+b, a+2b ..." includes the equal ratio of prime numbers, it means that the ratio of prime numbers is .


 

1.11. Lagrange’s theorem

Suppose "p" is a prime number and "n" a natural number then the greatest power of prime number "p" in "n!" is equal to:

(: Number integer part).

Proof. We want to count the number of prime factors of "p" in "n!".

The number of integer numbers among the numbers "1, 2, …, n" that "p"

aliquot them, is equal to .But some of these numbers are also divisible by "". Specially in the sequence 1, 2,..., n, the number of numbers divisible by "" are exactly equal to and etc.

Therefore, sum of is equal to the number of prime factors of "p" that exists in n! ; It is necessary to mention that this summation has always a finite number of non-zero terms. Because for supposed "n", there is "k", so that, therefore, .

On the other word:

We suppose numbers "n" and  as natural number and  as a prime number. It is clear that numbers of  sequence are divisible by must be in  form that  is a natural number and adapted in condition  in which. It is obvious that the number of   values is. In the other hand "t" ("p" power) that appear in factorization of "n!" to prime factors n is obtained from sum of numbers which are the number of  sequence’s terms divisible by  or or or ... .Therefore justification of relation (1) is verified.

1.11.1. Example

Calculate the greatest power of that aliquot "62!".

Solution. According to and considering this point that greatest power of "5" is smaller than the greatest power of "3" which aliquot "62!", it is enough to determine the greatest power of "5" which aliquot "62!":

It is obvious that the greatest power of "3" which aliquot 62!, is the least "14". So, the greatest power of "15" which aliquot "62!" is "14" (number ).

1.11.2. Example

How many zero the number 100! is ended to?

Solution. In fact, we must calculate he greatest power of in "100!". Since the greatest power of "5" is smaller that the greatest power of "2" which aliquot 100!. We determine only the greatest power of "5" that aliquot 100!:

Therefore, 100! is ended to "24" zero.

1.11.3. Example

How many zero the number  is ended to?

Solution. The greatest power of "10" that aliquot "340!" is:

And also, the greatest power of "10" that aliquot "170!" is:

Therefore, number is ended to "83-41=42" zero.

1.11.4. Example

Find natural number "n" in which "n!" is ended to "20" number of zero.

Solution. It is clear that number "n!" is ended to "20" number of zero if and only if the greatest power of "5" that aliquot "n!" is equal to "". On the other hand we want to find "n" that

 

If "", then and if , then "", therefore, it is clear that.

If , then, we can write:

If and, then:

   ; 

Therefore, values of "n" will be determined for  and "":

;

1.11.5. Example

If we suppose that "n!" finish to  the number of zero, show that is approach to  for great number of "n".

Solution. It is clear that is equal to the greatest power of "5" which aliquot "n!" (According to theorem 1.11):

          (1)

 

It is obvious that if , then  and it means that there isn’t more than "" nonzero terms in . Here, we consider below geometric progression:

                        (2) 

With comparing every term of (1) series with every term of (2) series:

In special case:

       (3)

The limit of infinite terms of geometric progression (2) is equal to , so, we have below relation with substituting this value instead of:

(In fact, if "n" be great infinitely,  is great infinitely)

             (4)

Since the rate of changing of logarithmic function is slower than "n", then if we choose "n" great enough, we can approach the quotient of  to so that is equal to "n/4" approximately.

1.11.6. Example

Whether number "n!" can finish to 48 number of zero?

Solution. It is clear that for solving this problem, it is enough to determine the greatest power of "5" which aliquot "n!" . For, we calculate: