CHAPTER 14
On the history of searching for famous prime numbers and the factorizations of these numbers _{}
Some of the forms of numbers exist that verifying in them, was origin of important improvements in number theory. Some of them that had old record like figurate numbers, perfect numbers and amicable numbers that found favor not only because of their interesting Arithmetical properties, but also because of secret properties that had attributed to them, and others are Fermat's numbers, Mersenne's numbers, Fibonacci's numbers and lucka's numbers.
If "a" and "n" be two nonone natural numbers, in order to _{} be prime necessary conditions is that _{} and "n" be prime, but this conditions aren’t sufficient.
Proof. With suppositions, we suppose that (_{}) be prime number. If_{}, then _{}and _{}and this is paradox with being prime of (_{}), so_{}. For proving the assertion about "n", if "n" is not prime, natural numbers like "h" and "k" exists so that _{}, _{}and _{}.
Then in one side _{}and the other side _{}and therefore _{}and also it is paradox to primality of_{}. Proving the insufficiency of condition is by counter example, it means (_{}) has mentioned but it is equal to:
_{}
If _{} and_{}, in order to (_{}) be prime, necessary condition is that "a" be even and "n" be a power of "2", but these conditions aren’t sufficient.
If "p" be an odd prime number, every positive divisor of "_{}" is in "_{}" form, that "k" is a non–negative integer number.
Proof. It is clear that divisors of "_{}"are odd. So assertion is established bout odd prime divisor of "_{}". For finishing demonstration, it is enough to observe Firstly, "1" is in "_{}"form _{} and secondly multiplication of every two numbers which are in this form, is the same.
If _{}, then every odd prime factor of _{}is in _{}form that "k" is a natural number.
(Fermat in his letter to Fernikle in 1640), If "p" be a prime number and greater than "3", every non–one positive divisor of "_{}" is in "_{}" form that "k" is a natural number.
Proof. First because "_{}", so "N" is a natural number.
Now, we consider that dN and_{}. For proving the assertion, it is enough to prove that every prime factor of "d" is in _{}form. We consider that "q" be a prime number and qd. Because "N" is odd and_{}. At first, we prove that_{}. We consider that_{}, So, 3N and _{}and then_{}. Therefore, because order of "2" is "6" with module "9", so 62p and then 3p is opposite of thesis.
So, it is clear that_{}. Since qN, in the above mentioned way, it will be clear that_{}. Now we consider that "h" be order of "2" with module "q". Because none of _{}and _{}are divisible by "q" (Because _{}), _{} also _{} and _{}. So even numbers "2p" and (_{}) have common divisor greater than "2" and so_{}. So, because "p" is a prime number and _{}, then _{}. At last, because (_{}) is even and "p" is odd so _{}and then _{}.
For every_{}, we name the integer number _{}as Fermat’s number. If "_{}"be prime number, then we call "_{}"Fermat’s prime number or Fermat's prime.
If "n" be equal to one of "_{} and 4", then "_{}" are respectively "3, 5, 17, 257 and 65537 "that all of them are prime numbers. Maybe important, reason of renown and importance of these numbers is that in "1640", Fermat claimed in a letter to Fernikle that "_{}" are prime numbers for every _{}. And as usual, Fermat didn’t present a demonstration for it. But in "1658", he claimed that with infinite decreasing method, he proved it. In fact, this guess was false. Almost a century later, in "1732", Euler showed that "641" is a divisor for "_{}". In "1640", Fermat gave an answer to Fernickle in a letter and showed that "_{}" isn’t a prime number and "223" is a divisor of it. In fact, Fermat showed that divisors of "_{} " are in "_{}" form. In fact, we can present use the same Proof for _{} that if "p" be a prime divisor of "_{}", then "p" must aliquot _{}. We can prove that _{} that "k" is an integer number. First prime numbers of this form are 193, 257, 577, 641, … that 641 aliquot "_{}". In fact, this is such method that Euler showed that "_{}" isn’t prime and it is so strange that why Fermat couldn’t prove it himself and he didn’t use the method which was used for calculating the factors of "_{}", for factorization "_{}". With more attention, we can show that prime divisor of "_{}" are in "128k+1" form, not in "_{}" from.
We avoid proving of this subject in this book. In next subjects, we show that same results are established for prime divisors of Fermat's numbers "_{}".
Fermat’s numbers are very important not only for their interesting arithmetic properties, but also for their perfect dependence to dividing periphery of circle to equal members by compass and star.
(T. Pepin. 1877). If and only if "_{}" be prime number_{}then:
_{} _{}
Now, we explain these problems below:
How is it possible that we know compositing of a Fermat’s number without knowing a divisor of it?
Answer of this question will clear in explanation of using of Pepin theorem. If _{}be congruent with "1" by module "_{}", then "_{}" is prime. If not, it is composite.
Now, at first we choose simple example of "_{}". We must search that "_{}"is in "_{}"form or not, because_{}. Method of calculation is clear for reader. With module_{}, _{} ,_{}, _{},
_{},_{},_{}
So"_{}" is a prime number. As it seems, we just need to calculate of square of a number and changing to module "_{}" in above calculation. And this reduces, save us that we entangled with such a big number like"_{}".
Generally, _{} and we must calculate square of "3" of (_{}) times and after every times, reduce out come to module "_{}". If final result be congruent with "1" by module "_{}" then "_{}" is prime, if not, it is composite (attend that if "_{}" be composite it hasn’t any factor of it).
And for "_{}" we must repetition it action (_{}) times and after every times, changing to module _{}(This number has 39 digits). Therefore we must calculate square of a number with at least 39 digits, 127 times and we divide out come of every times by_{}, a 39digit number and calculate residual of division.
These calculations are very tedious, but possible and with this method, in 1905 Morehead and Western could prove compositing of "_{}" without they could present a divisor of it. Of course with new electronic computers, we can determine primality of greater numbers according to this principle.
According to previous theorem every prime factor of "_{}" is in form of "_{}"; this assertion was in one of Euler’s works (in 1747) and maybe he knew it in 1732 (when he prove compositing of "_{}"). In 1877, Luka proved stronger theorem.
Every non–one divisor of _{} is in _{}form. According to Luka’s theorem, divisors of _{}are in _{}form. For _{}, Tivial divisor "1" will be gained. Now, we search about prime divisors of _{}. Out come numbers aren’t prime for _{}and _{}, because _{} and _{}, and this number is divisible by _{}.
Out come number is also composite for_{}, because_{}:
_{}
So,_{} Also, out come number is composite for_{}. Now we test _{}that has 587 digits. We observe:
_{}
Is _{} divisible by "m" or not? Searching about it refers to searching about this that is _{}divisible by "m" or not? For finding "_{}", we must calculate square of 1944 number that every number has 587 digits at least, and after every action of square, we divide the out come number (that has 1175 digits at least) by "m" and calculate residual of division. Only new electronic computers can calculate these and so, Robinson could prove that _{}. Therefore _{} is a composite number, because _{}. Meantime, according to what we said at first about factors of _{} and about compositing of values of _{}for 1,2,3 and 4 values from "k" it clear that "m" is the less non–one positive divisor of _{}. So it is a prime number.
If "p" be a prime number in _{}form, then:
_{}
Proof. With testing, it clears that assertion is established for _{}. So, we consider that _{} and _{}. We show multiplication of _{}natural numbers which are devisable by 3, firstly from 3 to P. It is clear:
_{}. (1)
Now, we factorize "P" to_{}:
_{}.
It is clear:
_{}
_{}
_{}
So, _{}, and according to (1):
_{}
But"_{}"and "p" is coprime with_{}. So:
_{}
This is equal with congruence of assertion. (Specially the case of this lemma is Pepin’s theorem:_{}).
If "_{}", _{} relation _{} always is established.
Proof. For every integer number_{}, it is clear that _{} (Bernoulli’s inequality). Therefore _{}; so _{}and _{}so _{} that it results immediately_{}.
It is clear that Fermat’s numbers are pseudo–prime.
We can show that if for natural number "k", _{}adapts in condition_{}, then "m" is a Fermat’s number.
Here, we express some special problems which lead to some special results about "_{}" (Fermat’s numbers). Mentioned interesting special numbers are in _{} and _{}form.
Find all prime numbers in _{}form so that "n" is a natural number which hasn’t more than 300000 digits!
Solution. Only three prime numbers exist which adapt in conditions of problem:
_{}, _{}, _{}
In fact, if _{}be prime, it is obvious that "n" hasn’t odd divisor grater than "1". So, it must be in _{} form, that "k" is an integer number. But in this situation "_{}". We are sure that "k" hasn’t odd divisor greater that "1". Therefore, _{} that _{} is an integer number. Than _{}that for _{}, _{} and for _{}, _{} and for _{} and _{} , _{} and _{} are obtained respectively, that both of them are composite. For _{}, _{} is obtained that _{}and latest number has more than 300000 digits.
Find all prime numbers in _{}form that hasn’t more than _{}digits.
Solution. Only two numbers exist that are:
_{} , _{}
We use the same proof as we used in previous problem. At first, we prove that if _{} and "_{}" be prime, then _{}that "s" is a natural number.
Therefore:
_{}
For _{}are obtained that both of them are composite (_{} and_{}) for _{}, _{} is obtained that has more than _{}digits.
Now, we understand that if for every _{}, _{}be composite, then infinite Fermat’s numbers exist that are composite.
In a letter to Fernickle, Fermat’s guessed that if "a" be even then _{}is prime, except some "N" that are divisible by Fermat’s numbers. We reject this Fermat's guess.
Solution. We put _{} and _{}, then _{}. But 89 and 233 are prime number but none of them are Fermat’s numbers.
If "_{}" is an indicator of nth Fermat’s number, prove that infinite "n" exist so that _{} is a composite number.
Solution. We remember that _{}is square of "_{}". Therefore, if "n" change from "0" to_{}, then their values with module "7" are "2, 4, 2, 4, …". So if "n" be odd, then _{}.
Therefore, for every (odd)_{}, _{} is a composite number.
If _{}, prove that "_{}" finish to 7.
Solution. We prove that if _{}, then _{} (mod 5). And "_{}" is odd, so "_{}" finish to 7. If _{}, then _{}, we put _{}.
Therefore _{}.
Problem (14.3.4) is equal to that we prove infinite composite numbers exist between numbers in _{}form and _{} .
Solution. We want to prove that all numbers in _{} form and _{} are prime numbers .In fact, we know that for every natural number "k", _{} that "t" is a natural number. So:
_{}
But, since for every natural number "k", _{}so it is a composite number. Problem of existence of infinite prime numbers in form of "_{}" is also an open problem.
For every natural number "n", prove that _{} is a composite number.
Solution. All of this kind numbers are divisible by 3, so result is obtained.
Numbers in form of _{}and _{} can be decomposed by identity. Compositing of these two numbers can be proved by factorization.
(Guidance:_{})
If "_{}" be nth Fermat’s number, It is proved simply that _{} isn’t a prime number for _{}.
We can show that infinite composite numbers exist between numbers in _{} form. (Guidance: it is enough to calculate with module 11).
It is prove simply that if _{} then the Fermat’s number _{} is in _{} or _{}form. Now, we express some properties of Fermat’s numbers.
(I) _{}.
(II)_{}.
(III)_{}.
Lemma. For every natural number "n":
_{}
In other word, every Fermat’s number except "_{}", is in _{} form.
Proof. Assertion is established for_{}. We Consider n>1 and _{}. So_{}, then according to (I):
_{}
Every two different Fermat’s numbers are coprime.
Proof. We consider "_{}" and "_{}" are two different Fermat’s numbers and "d" is a positive common divisor of them. Without any disorder to generality, we consider that _{}. So, _{} and because of (III), _{}. But, according to definition of "d", _{}.
So_{} and _{} or _{} . But because "_{}" is odd, _{}, so _{}.
We suppose that there are only "r" prime numbers. We call them _{}. Because every one of _{} numbers of _{} has a prime factor, according to pigeonhole principle, it is necessary that one of "_{}" aliquot at least two numbers of these _{} numbers and this is paradoxical with theorem (14.3.12).
As it is clear from definition of Fermat’s numbers and also equality (I), Fermat’s numbers increase fast. For example, _{} has more than _{} digits.
How can we gain this result without logarithm tables? Simply, because: _{};_{}
Necessary and sufficient condition for dividing circle to equal "p" part by compass and star is that "p" be a Fermat’s primer number_{}.
It is necessary to say that solving the problem of scribing regular "m" goons in circle lead to drawing the angle_{}. In other word, if "k" and "t" be two natural coprime numbers, two correct numbers "u" and "v" exist that _{}, so:
_{}
For every two coprime nonone natural numbers, "k" and "t" if divide the circle to "k" equal members and "t" equal member be possible by compass and star, its dividing to "kt" equal members is also possible. For example, dividing the circle to "15" equal member is possible and manner of division is obvious with below relation:
_{}
Here, according to Gauss’s theorem and also division an arc to "_{}" equal members is possible by compass and star, it is clear that if natural number "m" be a multiplication of _{} in one or some different Fermat’s prime numbers, dividing the circle to "m" equal member is possible by compass and star.
Until Gauss’s time, dividing the circle was known only to _{}and _{}equal parts. Because "_{}" is a prime number, according to Gauss’s theorem, dividing the circle to "17" equal parts is possible by compass and star.
As we said, Euler was first person who proved falseness of Fermat’s guess by factorization "_{}" to multiplication of two prime factors (1732). In 1880 Fortune Landry in 82 years old, proved after some month attempts:
_{}
(Both factors of second side are prime number). In 1905, C. Morehead and A.E. Western independently, proved that "_{}" is composite without factorization it. Until 1971, none of "_{}" factors was known, but in 1971, John Brillhart and Michael Morrison with help of an electronic computer in California University (Los Angles) decomposed this number to multiplication of two prime factors and this is one of charming factorization that has been done till now:
_{}
In 1909, Morehead and Western proved untidily that "_{}" is also composite. Today we know that "_{}" is composite for below values of "n":
_{}
Mersenne’s numbers are important because of two reasons at least firstly because of their perfect dependence to perfect numbers and secondly because greatest known prime number is one of these numbers. In this discussion, we acquaint Mersenne’s numbers and also a short history of searching about these numbers will be expressed.
According to theorem, if "_{}":
_{} (1)
be prime number, it is necessary that "n" be a prime number. The ancient Greeks had known that _{} and _{} are prime number. In 1644, Mersenne said this assertion that "_{}":
_{} (2)
For below prime numbers is prime:
p = 2,3,5,7,13,17,19,31,67,127,257
And for other prime numbers of "p" that are smaller than "257", "_{}" is composite. On the occasion of it:
_{} and _{} are Composite and_{}, _{} and _{} are prime.
Now, we know that "_{}" is prime number for below 42 prime numbers (2005):
P =2,3,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281,3217,
4253, 4423, 9689, 9941, 11213, 19937, …, 25964951
And for the other prime numbers which are smaller than "_{}", they are Composite.
Still it isn’t clear that sequence of Mersenne’s prime numbers is finite or not.
A bout Mersenne’s numbers, below questions were proved:
1. If "p" and _{} be prime, only one of below relations is established:
_{} or _{}
2. With previous question, it is proved that _{} and _{} are composite.
3. If "n" be odd and pseudo–prime "_{}" is also pseudo–prime.
4. If "p" and "q" be two different prime numbers_{}.
5. "_{}" isn’t mth _{} power of any natural number_{}.
6. Every odd number aliquot a lot of terms of _{}sequence.
Natural number_{}
Is called as an perfect number when_{};
Is called as a imperfect number when _{};
Is called as a redundant number when _{}.
We consider that "a" be a natural number. We call a natural number "d" as a member of "a" "except itself" when _{} and _{}. For example, members of "6" which are "except itself", are 1, 2 and 3. According to above definition, natural number "a" is perfect, imperfect or redundant with respect to that is equal with Sum of "except itself" "a" member or be greater or smaller than this sum.
Numbers "6" and "28" are perfect:
6=1+2+3, _{}(6) =1+2+3+6=2.6; 28=1+2+4+7+14
Number "9" is nonperfect and 12 is redundant:
9>1+3, _{} (9) =1+3+9<2.9;
12<1+2+3+4+6, _{} (12) =28>2.12.
If "p" be prime number and "_{}" be a natural, "_{}" is an imperfect number, because:
_{}.
If "p" and "q" be two different odd prime numbers and "_{}" and "_{}" be two natural numbers, _{} is imperfect. So, set of odd imperfect numbers (even) is infinite.
Without any disorder to generality, we suppose that_{}. Like previous example, it is clear:
_{}
According to suppositions, _{} and _{}. So according to decreasing of _{}:
_{}
Between "1" to "100", only "22" redundant numbers exist and they are even:
12, 18, 20, 24, 30, 36, 40, 42, 48, 54, 56, 60, 66, 70,
72, 78, 80, 84, 88, 90, 96, 100
Between odd natural numbers smaller than 1000 only 945 redundant numbers exist. Immediate redundant number after it is 1575.
In theorem 36th, 9th article of "Principles" book, Euclid proved that if "_{}" be prime, even number of _{}is perfect.
2000 years after it, Euler proved that Euclid’s formula perfect obtained all of even perfect numbers.
If _{} be prime number:
_{} (1)
Is perfect (Euclid). Contrarily, If "a" be perfect and even number, there will be a natural number like "n" so that _{} is prime and equality (1) is established (Euler 1749). So, even perfect numbers are"_{}._{}" for every "p" prime number that "_{}" be a prime Mersenne’s number.
Proof of Euclid assertion. Suppose that _{}be prime number and _{} since_{}, then according to being multiplicative of "_{}" function:
_{}
Suppose that "a" be a perfect and even number. So _{} that _{} and_{},_{}. According to thesis, _{}. So since_{}:
(1) _{},
and also:
(2) _{}
So, because latest fraction is unchangeable and standard, for every natural number like "c":
(3) _{} , (4) _{}
Then, _{}. Because, if we consider that c >1, so "b" has divisors of "b", "_{}", "c" and "1", therefore:
_{}
So:
_{}
and it is opposite of (3). So _{} and according to (3) and (4), _{} and _{}, then, "b" is prime. So, if _{}, then _{} is prime and _{}.
This proof belongs to Dikson (1929) and it is branch of Euler’s proof. With considerations and symbols of Euler’s proof, according to (1) _{}. So, for natural number like, "c", (i) "_{}" and (ii) _{}. So, (iii) _{}. But, according to (ii), "_{} and _{}". Therefore, "b" has two divisor "b" and "c" and because of (iii), it hasn’t another divisor. Then _{}. So "b" is prime and according to (ii) _{}. Therefore _{}.
As it is clear from previous theorem, Problem of even perfect numbers definition has completely dependence to problem of prime Mersenne’s numbers definition, and since it isn't clear that sequence of even perfect numbers is finite or infinite.
14.10.11. Theorem. Every even perfect number is ended to "6" or "28" .In other word, for every even perfect number like "a" one of below congruencies is established:
_{} , _{}
Proof. Suppose that "p" is an add prime and _{} is a perfect number. If "p" be in _{}or _{} form, there is two case.
First case. _{}. Because natural powers of "16" finish to "_{}":
_{},_{} and _{}.
Second case. _{}. So _{}. Moreover, as it seemed past, it is clear that _{}. The gist of the matter _{} ended to "4" and it is divisible by "4", so, according to rule of divisibility by "4", _{}is finished to 04, 24, 44, 64 or 84. In every one of these cases, _{}that "t" is a correct number. Then, _{} and also:
_{}
Every where, mentioned "perfect number", its purpose is even perfect number.
Perfect numbers are mentioned in Plato’s works. Old Greeks had known that these numbers like regular polyhedron, maintained completely harmony as it was in the world, and considered these numbers as reflection of this harmony. And because of their effect, in ancient times and early Middle Ages, every where, had maintained for these numbers, hinted meaning.
We mentioned dependence of definition of even perfect numbers to definition of prime Mersenne’s numbers, before. Generally, problem of primality identification of _{} in general case is unsolvable and for big values of "p" has great difficulties. So, old mathematicians had false assertion about even perfect numbers. Old Greeks had known below numbers as prime numbers:
_{}, _{}, _{}, _{}
And Nicomachos (the 1th. century A.D), had known the like perfect numbers:
2.3 (=6), 2^{2}.7 (=28), 2^{4}.31(=496), 2^{6}.127(=8128)
And they supposed these numbers finished to "6" and "8" successively. Both of two suppositions are false. 5th perfect number is 33550336 that first clue is in a European manuscript in 1456. In other side, Successive even perfect numbers like p=19 and p=31 are:
2^{18}(2^{19}1) = 137438691328
2^{30}(2^{31}1) = 230584 3008139952128
that both of them are finished to 8.
We return to primality problem of_{}. Maybe the first person, who attended that it isn’t necessary for _{}to be prime number for every prime number of "p", was Hudalrichus Regius, who presented factorization of _{} in 1536.
In 1644, Mersenne’s assertion published and became origin of extensive researches. Euler (1772) verified that _{} is prime number. So, he calculated 8th prime number. Describing all of researches that has been done about primality of Mersenne’s number doesn’t Contained in this brief. We mentioned some of the important works.
Before electronic calculators, domain of research in number’s primality was very limited. Invention of normal calculators, facilitated calculations to some extent, But it was very weak in contrast of number’s greatness. In this time, wonderful speed and power of electronic computers had used and these computers, with help of some special criterion that scientists of number theory discovered them, could do excellent works and we mention some of them in next pages . Fore example, today we know that number _{} is a prime number, but it is estimated that If "80" persons calculate it primality with normal method; they must spend one thousand years. It mustn’t forget that power of electronic computers also is limited and for example, neither science and nor modern technology could clarity situation of _{}(from Fermat’s numbers) about its primality.
Attend to this point that in past it was possible that a number could keep its topic as "greatest known prime number" as below number with "39" digits:
2^{127}1=170141183460469231731687303715884105727
That in 1877 Lucka proved its primality. And because of it, this number is famous as Lucka's prime number. It was the greatest known prime number till 1951. In 1876, Lucka propounded that his long calculations proved "_{}" is composite[1]. In 1903, Cole decomposed this number to multiplication of two prime factors:
M_{67}=2^{67}1=193707721.761838257287
In 1883–87, "Pervusin", priest of "Perm" government (in Russia) and "Paul Seelhoff" from Germany, independently proved that inspire of Mersenne's assertion, "_{}" is prime. In 1911, "Powers" proved that "_{}" is prime number with use of a criterion which Lucka established. In 1914, Fauquembergue proved that "_{}" is prime number. In 1922 Kraitchik proved compositing of below number:
M_{257 }= 231584178474632390847141970017375815706539969331281128078915168015826259279871
And Lemmer test validity of his work (1931). Lemmer with help of a table–calculator spent more than 700 hours on this work. After 20 years (SWAC) an electronic computer in California university (American) did this calculation in "48" seconds. (Generally, every minutes of SWAC’s work is equal with one year work of human with table calculator).
This was a short history of discovering Mersenne's assertion errors. For positive aspect, we just mention this subject that in 1877 Lucka proved by his self formula that the "39" digits number of "_{}" is prime. This number was the greatest known prime number till 1951. For finishing the subject, we must say that in this year, "Ferrier" a French, calculated with a different method of Lucka’s method and by calculator that the "44" digits number _{}is prime. This is the greatest prime number (and probably it will be) that is calculated without using electronic calculators.
In 1947, situation of all of Mersenne’s numbers from primality aspect for _{} was determined with or without using calculators.
Searching in "_{}" for_{}, isn’t possible and because of it Lucka’s prime number (M_{127}) till 1951 kept its title as "greatest known prime number".
_{}
(Respectively have 157, 183, 376, 664 and 687 digits). The first known prime number has more than 1000 digits _{} that in 1961 by a kind of "IBM7090" calculator could prove its primality. In 1963, it is clears that _{} is prime number. (ILLIAC II) calculator of American university calculated this and it took long "2" hours and "15" minutes. _{} has 3375 digits and for sometimes, it was greatest known prime number. Till in 4th night of March in 1971, Tuckerman proved that _{} is prime number and calculated it by a kind of "IBM" calculator[2].
What we said in previous pages was about even perfect numbers. One of famous and unsolved problem of number theory is that odd perfect number exists or not?
If such a number exist, at least have three odd prime factors.
Proof of odd perfect numbers related to solving below equation:
_{}
That every thing is indeterminate except this point that "_{}" is odd prime numbers. Verifying in this equation is very complicated and till now, except some special condition of its possibility, we don’t know about existing answer.
Prove that every perfect number is ended to "6" or "8".
Solution. Every even perfect number "N" is in _{} form that "p" is prime number. If _{}, then _{}. Therefore, consider that "p" is an odd number. If_{}, then_{}.
Also _{}._{}. So, _{}.If _{}, then_{}and_{}.
Therefore _{}.
Consider that _{} be a perfect and even number. Prove that "N" is in "_{}" form.
Solution. Every even perfect number "N" is in _{}form that "p" is a prime number. Specially if _{}, then "p" is an odd number. For odd numbers "n", we show that _{}(mod 9). If "n" be an odd number 1, 3, 5,… then _{}is congruent with 1,4,7,1,4,7,… with module "9". Although_{}, for odd "n", is congruent with 1,7,4,1,7,4,... with module "9". By multiplying these numbers _{}is congruent with 1, 1, 1, 1, 1, 1, …with module "9". So:
_{}
Prove that if "p" be prime number, then "_{}" isn’t perfect number.
Solution. First method. According to definition of perfect number, sum of divisors of "_{}" must be equal with _{}, although, sum of divisors of _{} is equal with _{}. Of course, it isn’t equal with 2p^{k} and infact; it isn’t equal with any other coefficient of "p". So, it is obvious that "p" doesn’t aliquot _{}.
Second method. Because:
_{} So, _{}.
Therefore "_{}" can’t be a perfect number.
Prove that "n" is a perfect number, if and only if _{}.
Solution. If "d" change on positive divisors of "n", then _{}also take all of different divisors of "n".
Therefore, _{}so "n" is perfect, if and only if _{} that with dividing two side by "n" proved our problem.
With help of previous problem or every another method show that none of proper divisor of a perfect number, isn't a perfect number.
Solution. Consider that "n" be perfect and "k" be a proper divisor of "n". According to previous problem_{}, now, attend that every divisor of "k", is divisor of "n". But "n", at least has another divisor greater than "k", for example "n". Therefore, _{}. So "k" isn’t perfect.
If "p" and "q" be two odd different prime numbers, prove that "pq" isn’t perfect.
Solution. According to multiplicative property of "_{}":
_{}.
That it isn’t equal with _{}. Since for example _{} is divisible by "4", but _{} hasn’t such property.
14.14.6.1. Note. With same reasoning, we can show that multiplication of every the number of different prime numbers, isn’t perfect. Therefore, if an odd perfect number exists, it can’t be without square.
Show that _{} is a perfect number.
Solution. It is enough to show that _{} is a prime number. In order to this, it is enough, we verify its prime divisor smaller than _{}. Also prime factors of "_{}" must be in form of"_{}".
Therefore, it is enough that we test these prime numbers 103, 137, 239 and 307 that they don’t aliquot "_{}". Since none of these number doesn’t aliquot "_{}", so, "_{}" is a prime number.
Show that _{}is a prime number?
Solution. It is clear that every prime divisor of _{} is in _{} form. So, we verify only prime numbers smaller than _{}and are in upper form. Because such a number doesn’t exist, so 127 is a prime number.
Show that is _{} a prime number?
Solution. With help of problem (14.15.1), we verify only all of prime divisors of "q" that are in _{} form so that _{}.
But the only prime number that in such kind is _{} and _{} then _{} is composite.
Show that _{} is a prime number?
Solution. The only possible divisors must be in _{} form that are 59, 117, 175, 233, … it seem simply that 59 isn’t a divisor of it. And "117" and "175" also aren't prime number and it isn’t necessary to verify them. Because the smallest divisor of _{} must be prime and greater than "1". It seems simply that 233 is prime and a prime divisor of _{}. So _{} isn’t a prime number.
Solution. Every prime divisors of _{} must be in _{} form 47, 139, 277,… . It seems simply that_{}. So _{}is composite.
Consider "m" be an odd correct number. Prove that if "_{}" then "m" aliquot Mersenne number_{}. (Hint: use from Euler's theorem).
Solution. According to Euler's theorem_{}, so _{}_{ }that "k" is a positive correct number. Therefore "m", aliquots "_{}", if "n" be a positive coefficient of_{}.
Prove that _{}is a prime number.
Solution. We know that every prime divisor of "_{}" is in _{}form. We must verify all of prime numbers smaller than _{}and in above form. We only find "193". It seems simply that "193" isn't a divisor of "_{}". So "_{}" is a prime number.
Prove that_{}.
Solution. It is proved with induction and we use Just properties of highest common divisor of two numbers. Consider "d" be constant. We show, if for every "s" and "t", assertion be established that _{} and _{}, then assertion is established for every "s" and "t" that _{} and _{} also is established. If _{}, then assertion is obvious. So, consider _{}. According to relation _{}:
_{}
Since "s" and "_{}", both of them are smaller than "n" and also_{}, so according to thesis of induction_{}. So, _{}always is established.
With the same method, we can show that if _{}, then:
A. Suppose that "_{}" be kth Fermat’s number. Prove that if _{}, then _{}. (Guidance: Suppose _{}, then _{}).
B. With help of "A" propound another proof for infiniteness of the number of prime numbers.
Solution.
A. we can suppose _{}. Consider "p" be a prime divisor of "_{}", so _{}, since _{}is an extension to even powers of _{}, so _{}(mod p). Specially since "p" is odd, so "p" can’t aliquot "_{}".
B. Every "_{}", has a prime divisor like_{}(Probably "_{}" itself). Since, if _{}, then _{}, so _{} .If_{}, then infinite different values of "k", obtain infinite different values of "_{}". So, infinite Prime numbers exist.
We don’t need to know infinite "_{}" are prime. In fact, this result is still an open problem.
Suppose that _{} and _{}and_{}. Show that if _{}, then "_{}" and "_{}" are coprime. (Hint. you can consider that _{}, now show that if "p" aliquots "m", then "p" can’t aliquot _{},_{}, …)
Solution. With induction on "i", we show that if "p" aliquots "_{}", then for every_{}, _{}. We put_{}.
If i=1, then _{} Now consider_{}, So, _{}.
With this method of proof, you also can show that the number of prime numbers is infinite. Between this problem and previous problem there is a very close conceitedness. If "_{}", be nth Fermat’s number, simply can be showed that _{} that_{}. You can adapt conditions of previous problem with this problem and show that if "p" be a prime number that aliquots "_{}", then for every "i":
_{}
Because all of Fermat’s numbers are odd, so, every two different Fermat’s numbers are coprime. You can obtain the same results for quasi–Fermat numbers with some polynomial corresponding with them.
1. Always_{}. (So, every composite Fermat’s numbers is quasi–prime).
2. Every Fermat’s number, except_{}, is in _{} or _{} form.
3. Fermat’s numbers except "_{}" and "_{}" are ended to 17, 57, 37 and 97 regularly.
4. Calculate the number of digits of _{} in decimal.
5. Prove that Diophantine equation _{} exactly has an answer in natural numbers that _{}.
6. Prove that 2^{17}1 is prime number.
7. Calculate smallest possible prime factor of 2^{19}1.
8. Suppose that "p" and "_{}" two different odd prime numbers, _{} and _{}. Prove that every odd prime divisor of _{} that doesn’t aliquot "_{}", is in one of these form _{} or _{} or _{}.
9. With thesis of previous problem, we consider that _{}. Prove that _{} or "q" is in _{} form.
10. Prove that _{} is prime.
11. Prove or disprove: Number _{} exists so that n! is perfect.
12. What is the first even perfect number greater than 10^{16} ?
13. What are the two last digits of perfect number of_{}?
14. Prove or disprove: If _{}be prime number, then:
is a perfect number.
15. Prove that if last digit of a perfect number be "8", then two last digits of it, is "28".
16. Prove or disprove: if "r", "s" and "t" be even perfect number and different, then:
_{}
17. Show that _{}is a power of "2", if and only if "n" be in below form that _{}and "_{}" are Fermat's prime numbers and different:
18. Prove for every _{} ,"n" and "_{}" are coprime.
(Hint. using this result that every prime division of _{}is in _{}_{ }form).
19. We call correct number _{} as redundant, if_{}.
A. Find smallest redundant odd number (At first it seems that this number doesn’t exist).
B. If "n" be redundant, show that every positive coefficient of "n" also is redundant.
20. Find greatest common divisor of _{} and _{}.
14.16.1. Note. Let _{} and_{}. The list of all known primes p of which _{}is a Mersenne prime, Therefore _{} is a perfect numbers.
Table of Known Mersenne Primes and perfect numbers
## 
p (exponent) 
Digits in _{} 
digits in_{} 
year 

discoverer 
notes 
1 
2 
1 
1 
¾ 
¾ 


2 
3 
1 
2 
¾ 
¾ 


3 
5 
2 
3 
¾ 
¾ 


4 
7 
3 
4 
¾ 
¾ 


5 
13 
4 
8 
1456 
Anonymous 


6 
17 
6 
10 
1588 
Cataldi 


7 
19 
6 
12 
1588 
Cataldi 


8 
31 
10 
19 
1772 
Euler 


9 
61 
19 
37 
1883 
Pervushin 


10 
89 
27 
54 
1911 
Powers 


11 
107 
33 
65 
1914 
Powers 

note 
12 
127 
39 
77 
1876 
Lucas 


13 
521 
157 
314 
1952 
Robinson 


14 
607 
183 
366 
1952 
Robinson 


15 
1279 
386 
770 
1952 
Robinson 


16 
2203 
664 
1327 
1952 
Robinson 


17 
2281 
687 
1373 
1952 
Robinson 


18 
3217 
969 
1937 
1957 
Riesel 


19 
4253 
1281 
2561 
1961 
Hurwitz 


20 
4423 
1332 
2663 
1961 
Hurwitz 


21 
9689 
2917 
5834 
1963 
Gillies 


22 
9941 
2993 
5985 
1963 
Gillies 


23 
11213 
3376 
6751 
1963 
Gillies 


24 
19937 
6002 
12003 
1971 
Tuckerman 

Tuckerman71 
25 
21701 
6533 
13066 
1978 
Noll & Nickel 

NN80 
26 
23209 
6987 
13973 
1979 
Noll 

" 
27 
44497 
13395 
26790 
1979 
Nelson & Slowinski 

Slowinski79 
28 
86243 
25962 
51924 
1982 
Slowinski 

Ewing83 
29 
110503 
33265 
66530 
1988 
Colquitt & Welsh 

CW91 
30 
132049 
39751 
79502 
1983 
Slowinski 


31 
216091 
65050 
130100 
1985 
Slowinski 


32 
756839 
227832 
455663 
1992 
Slowinski & Gage 

Peterson92 
33 
859433 
258716 
517430 
1994 
Slowinski & Gage 


34 
1257787 
378632 
757263 
1996 
Slowinski & Gage 

(web page) 
35 
1398269 
420921 
841842 
1996 
Armengaud, Woltman, et. al. (GIMPS) 

(web page) 
36 
2976221 
895932 
1791864 
1997 
Spence, Woltman, et. al. (GIMPS) 

(web page) 
37 
3021377 
909526 
1819050 
1998 
Clarkson, Woltman, Kurowski et. al. (GIMPS, PrimeNet) 

(web page) 
38 
6972593 
2098960 
4197919 
1999 
Hajratwala,Woltman,Kurowski et. al. (GIMPS, PrimeNet) 

(web page) 
?? 
13466917 
4053946 
8107892 
2001 
Cameron,Woltman, urowski et. al. (GIMPS, PrimeNet) 

(web page) 
?? 
20996011 
6320430 
12640858 
2003 
Shafer, Woltman, Kurowski et. al. (GIMPS, PrimeNet) 

(web page) 
?? 
24036583 
7235733 
14471465 
2004 
Findley, Woltman, Kurowski et. al. (GIMPS, PrimeNet) 

(web page) 
?? 
25964951 
7816230 
15632458 
2005 
Nowak, GIMPS et. al. 

(web page) 
We put question marks instead of a number for the last of the Mersenne primes because it will not be known if there are other Mersenne's in between these until a check and double check has been completed by GIMPS. See the GIMPS Status Page for more information. Note all smaller exponents have been tested.
[1]. In assertion in October of 1903, in American mathematics society, "Cole" was going to deliver a lecture. Title of lecture was "decomposition of great numbers". After he invited to start the lecture, he went by the black board and without any speaking. He gave "2" to power "67" and subtracted one from out come. Then on other side of board, multiplied 761838257287 and 193707721 and result of two calculations was equal. Then he came back to his seat without any word later. He said to one of his friend that he spent "20" years of his life in every Sunday’s afternoon for finding the factors of "M_{67}".
[2] .For more information look at the table of known Mersenne prime and perfect numbers in the next pages.