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.
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:
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.
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.
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:
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".
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.
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.
Suppose "m" and "n" are integer numbers that both of them aren’t "o" together. So, for every correct number:
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.
For every n>1, a prime number exists between "n" and "2n". Stronger result of Bertrand principle is:
If "n>5", then at least two different prime numbers
exist between "n" and "2n". Another obvious result is that
inequality "" results
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 k
n. 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.
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:
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.
Limit of doesn’t depend on choosing "b" until "a" and "b"
are coprime. Quotient tends to a limit that only depends on "a".
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
.
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.
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 ).
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.
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.
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 "
":
;
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.
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: