Prime number

“ We can prove that a number is a prime only by the purely indirect method of showing that it is not any of the numbers which have divisors, and the remarkable process known as Eratosthenes’ Sieve is the only mode by which we can select the prime numbers.‍72 It bears a strong analogy to the indirect method here to be described. ”

“ The problem really amounts to finding the smallest prime such that the next higher prime shall exceed it by 10 at least. If we write out a little list of primes, we shall not need to exceed 150 to discover what we require, for after 113 the next prime is 127. We can then form the square in the diagram, where every number is composite. This is the solution in the smallest numbers. We thus see that the answer is arrived at quite easily, in a square of the third order, by trial. ”

“ To apply the results obtained for the distribution of rational prime numbers to the theory of the distribution of ideal primes in a given number-field —a problem which looks toward the study of the function belonging to the field and defined by the series where the sum extends over all ideals of the given realm and denotes the norm of the ideal . ”

“ Form q from U by setting the most significant bit (the 2159 bit) and the least significant bit to 1. In terms of boolean operations, q = U OR 2159 OR 1. Note that 2159 < q < 2160. Step 4. Use a robust primality testing algorithm to test whether q is prime1. Step 5. If q is not prime, go to step 1. Step 6. Let counter = 0 and offset = 2. Step 7. For k = 0,...,n let Vk = SHA-1 [ (SEED + offset + k) mod 2g ] . 1 A robust primality test is one where the probability of a non-prime number passing the test is at most 2-80. 14 Step 8. Let W be the integer ”

“ In the language of ancient arithmeticians linear numbers, par excellence or properly so-called, were the prime numbers, measurable by unity only; plane numbers were the products of two such linear numbers or prime numbers; solid numbers were the products of three such. Understanding solid numbers in this restricted sense, it will be perfectly true that between any two of them you can never find any one solid number or any whole number which shall be a mean proportional, but you can always find two solid numbers which shall be mean proportionals. One mean proportional will never be sufficient. ”

“ But to form a table of prime numbers the process is theoretically simple and rapid, for we have only to range all the numbers in a line and strike out every second number beginning from 2, every third beginning from 3, and so on, those that remain being primes. Even when the tabular results are constructed separately, the method of differences or other methods connecting together different tabular results may afford valuable verifications. By having recourse to tables not only does the computer save time and labour, but he also obtains the certainty of accuracy. ”

“ It evolves from itself alone, often without appreciable influence from without, by means of logical combination, generalization, specialization, by separating and collecting ideas in fortunate ways, new and fruitful problems, and appears then itself as the real questioner. Thus arose the problem of prime numbers and the other problems of number theory, Galois's theory of equations, the theory of algebraic invariants, the theory of abelian and automorphic functions ”

“ Let the greatest common measure be k, and let a = kl, d = km. Then
is also in its lowest terms; but so is b/c; therefore we must have m = b, l = c, for otherwise a fraction in its lowest terms would be equal to another of lower terms. Therefore a = kc, or a is divisible by c. And from this it follows, that if a number be prime to two others, it [Pg 195] is prime to their product. Let a be prime to b and c, then no measure of a can measure either b or c, and no such measure can measure the product bc; for any measure of bc which is prime to one must measure the other. ”

“ After an exhaustive discussion of Riemann's prime number formula, perhaps we may sometime be in a position to attempt the rigorous solution of Goldbach's problem, [22] viz., whether every integer is expressible as the sum of two positive prime numbers; and further to attack the well-known question, whether there are an infinite number of pairs of prime numbers with the difference , or even the more general problem, whether the linear diophantine equation (with given integral coefficients each prime to the others) is always solvable in prime numbers and . ”

“ Secondly, if Y is a prime, it immediately follows that n cannot be the greatest prime, for Y is greater than n. Hence, however great may be any prime that we may assume, there will always be one that is greater, and even if we do not succeed in expressing it in figures, we see that it must certainly exist. Thus by studying carefully a particular case—the prime n, which was assumed to be the greatest possible one—we have arrived at a general theorem which states that there is no limit to the number of primes. Is not that, too, a triumph of intuition? ”

“ If two numbers have no factor in common (except 1) each is said to be prime to the other.
The multiples of 2 (including 1·2) are called even numbers; other numbers are odd numbers.
46. Greatest Common Divisor.—If we resolve two numbers into their prime factors, we can find their Greatest Common Divisor or Highest Common Factor (written G.C.D. or G.C.F. or H.C.F.) , i.e. the greatest number which is a factor of both. ”

“ Fermat died with the belief that he had found a long-sought-for law of prime numbers in the formula = a prime, but he admitted that he was unable to prove it rigorously. The law is not true, as was pointed out by Euler in the example = 4,294,967,297 = 6,700,417 times 641. The American lightning calculator Zerah Colburn, when a boy, readily found the factors, but was unable to explain the method by which he made his marvellous mental computation. ”

“ Any other origin is difficult to reconcile with observed facts, and still more difficult to reconcile with any rational theory of number system development. Dismissing from consideration the quinary scale, let us briefly examine once more the natural process of evolution through which the decimal and the vigesimal scales come into being. After the completion of one count of the fingers the savage announces his result in some form which definitely states to his mind the fact that the end of a well-marked series has been reached. ”

“ The division of the fingers into two sets of five each is still in his mind, but it is no longer the leading idea. As the count proceeds further, the quinary base may be retained, or it may be supplanted by a decimal or a vigesimal base. How readily the one or the other may predominate is seen by a glance at the following numerals:
By the time 20 is reached the savage has probably allowed his conception of any aggregate to be so far modified that this number does not present itself to his mind as 4 fives. ”

“ While considering the extent of the savage's arithmetical knowledge, of his ability to count and to grasp the meaning of number, it may not be amiss to ask ourselves the question, what is the extent of the development of our own number sense? To what limit can we absorb the idea of number, with a complete appreciation of the idea of the number of units involved in any written or spoken quantity? Our perfect system of numeration enables us to express without difficulty any desired number, no matter how great or how small it be. ”

“ But now the important fact, at present ignored, and to which I draw your attention, is that it is perfectly possible to have all the facilities which a method of notation like that of decimals gives, along with all the facilities which duodecimal division gives. It needs only to introduce two additional digits for 10 and 11 to unite the advantages of both systems. The methods of calculation which now go along with the decimal system of numeration would be equally available were 12 made the basic number instead of 10. ”

“ The process just indicated may be gone through with at 5, or at 20, thus giving us a quinary or a vigesimal, or, more probably, a mixed system; and, in rare instances, some other number may serve as the point of departure from simple into compound numeral terms. But the general idea is always the same, and only the details of formation are found to differ.
Without the establishment of some base any system of numbers is impossible. The savage has no means of keeping track of his count unless he can at each step refer himself to some well-defined milestone in his course. ”

“ It is a useful exercise to multiply and divide numbers represented in other scales of notation than the common or decimal one. The rules are in all respects the same for all systems, the number carried being always the radix of the system. Thus, in the quinary system we carry fives instead of tens. I now give an example of multiplication and division: [Pg 170]
Another way of turning a number from one scale into another is as follows: Multiply the first digit by the old radix in the new scale, and add the next digit ”

“ In order to generate the primes p and q, a primality test is required.
There are several fast probabilistic algorithms available. The following algorithm is a simplified version of a procedure due to M.O. Rabin, based in part on ideas of Gary L. Miller. [See Knuth, The Art of Computer Programming, Vol. 2, Addison-Wesley, 1981, Algorithm P, page 379.] If this algorithm is iterated n times, it will produce a false prime with probability no greater than 1/4n. Therefore, n ≥ 50 will give an acceptable probability of error. To test whether an integer is prime:
Step 1. Set i = 1 and n ≥ 50. ”

“ In the selection of a base,—of a number from which he makes a fresh start, and to which he refers the next steps in his count,—the savage simply follows nature when he chooses 10, or perhaps 5 or 20. But it is a matter of the greatest interest to find that other numbers have, in exceptional cases, been used for this purpose. Two centuries ago the distinguished philosopher and mathematician, Leibnitz, proposed a binary system of numeration. ”

“ Still another instance of quaternary counting, this time carrying with it a suggestion of binary influence, is furnished by the Mocobi207 of the Parana region. Their scale is exceedingly rude, and they use the fingers and toes almost exclusively in counting; only using their spoken numerals when, for any reason, they wish to dispense with the aid of their hands and feet. Their first eight numerals are:
There is probably no recorded instance of a number system formed on 6, 7, 8, or 9 as a base. ”

“ Other tribes of northern Africa have borrowed the decimal notation from their civilized neighbors.
Without a single exception the ancient civilized peoples of all the world—Egyptians, Babylonians, Hebrews, Chinese, Greeks, Romans, Hindus—all used the decimal systems. Such striking uniformity among all the races of the earth requires a natural origin for the decimal number base. As Herodotus first suggested, man counts by tens because he has ten fingers. While there may be logical grounds for the advocates of a duo-decimal system, the ten system is too deep-rooted to be dislodged. ”

“ A most inviting field for research is, however, furnished by the primitive methods of counting and of giving visible expression to the idea of number. Our starting-point must, of course, be the sign language, which always precedes intelligible speech; and which is so convenient and so expressive a method of communication that the human family, even in its most highly developed branches, never wholly lays it aside. It may, indeed, be stated as a universal law, that some practical method of numeration has, in the childhood of every nation or tribe, preceded the formation of numeral words. ”

“ The £1 is termed the unit. A numerical quantity, therefore, represents a certain unit, taken a certain number of times. If we take £3 twice, we get £6; and if we take 3s. twice, we get 6s., i.e. 6 times 1s. Thus arithmetical processes deal with numerical quantities by dealing with numbers, provided the unit is the same throughout. If we retain the unit, the arithmetic is concrete; if we ignore it, the arithmetic is abstract. But in the latter case it must always be understood that there is some unit concerned, and the results have no meaning until the unit is reintroduced. ”

“ It is such a Number, as divided by the rest of the Divisors, or their Product, the Remainder is 0; but divided by its own Divisor, the Remainder is an Unit. We require the Divisors proposed to be Primitive each to other, i.e. that no two or more of them can be reduced to lesser terms by any common Divisor: For if so, the Question may be possible in it self, but not revolvable by help of such Multipliers, such being impossible to be found. The reason is, because the Product of an Odd and Even Number is always Even, and that divided by an Even Number, leaves either Nothing, or an Even Number. ”

“ This is so only because we have become conditioned to the decimal system, which was even more hopeless to us as youngsters. We may have forgotten, with the contempt of familiarity, that our number system is built on the idea of powers. In grade school we learned that starting at the right we had units, tens, hundreds, thousands, and so on. In the decimal number 111, for example, we mean 1 times 102, plus 1 times 101, plus 1. We have handled so many numbers so many times we have usually forgotten just what we are doing, and how. ”