Notes on Prime Numbers
Factors of an integer
By definition, an integer b is a factor of an integer a, different from zero, iff there exists an integer q such that a = bq.
For instance, 17 is a factor of 102; in this case, q = 6.
Using an appropriate computer program, it can be obtained all of the factors of a given integer.
Examples: the factors of 384 are 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192, 384. The factors of 497 are 1, 7, 71, 497. The factors of 499 are 1, 499.
The restriction about a in above definition is convenient to prevent problems with the theory of quotient between integers. For the same reason zero cannot be a factor of any integer.
From above definition it follows that if integer b is a factor of a, then b is a factor of -a, also -b is a factor of a and -b is a factor of -a.
Using an appropriate computer program, it can be obtained all of the factors of a given integer.
Examples: the factors of 384 are 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192, 384. The factors of 497 are 1, 7, 71, 497. The factors of 499 are 1, 499.
The restriction about a in above definition is convenient to prevent problems with the theory of quotient between integers. For the same reason zero cannot be a factor of any integer.
From above definition it follows that if integer b is a factor of a, then b is a factor of -a, also -b is a factor of a and -b is a factor of -a.
Example: 96 is a factor of 384 (96 × 4 = 384), 96 is a factor of -384 (96 × (-4) = -384), -96 is a factor of 384 (-96 × (-4) = 384) and -96 is a factor of -384 ((-96) × 4 = -384).
For any two positive integers a, b such that b ≤ a it can be done a list of multiples of b not greater than a. If bq is the greatest in that list then r = a – bq, the reminder, is a nonegative integer and r < b.
Example: a = 38, b = 9. Multiples of 9 not grater than 38 = {9, 18, 27, 36}. The greatest of them is 36 = 9 × 4. In this case, r = 38 – (9 × 4) = 2.
Example: a = 38, b = 9. Multiples of 9 not grater than 38 = {9, 18, 27, 36}. The greatest of them is 36 = 9 × 4. In this case, r = 38 – (9 × 4) = 2.
The following schemas show a way to present graphically the relation between numbers a, b, q, r in r = a – bq
a = 38, b = -9. In this case, 2 = 38 – (-9) × (-4)
a = -38, b = -9. In this case, -2 = -38 – (-9) × 4
a = -38, b = 9. In this case, -2 = -38 – 9 × (-4)
From now on, only positive integers will be considered.
A property to look at
If r = 0 in r = a – bq, it means that b is a factor of a. If a = bq then a + 1 = bq + 1
Then, 1 = (a + 1) – bq. This means that 1 is the remainder for a + 1 divided by b.
A conclusion from above considerations is: if a = bq then b is not a factor of a + 1.
If b is a factor of a then b is not a factor of a + 1.
A property to look at
If r = 0 in r = a – bq, it means that b is a factor of a. If a = bq then a + 1 = bq + 1
Then, 1 = (a + 1) – bq. This means that 1 is the remainder for a + 1 divided by b.
A conclusion from above considerations is: if a = bq then b is not a factor of a + 1.
If b is a factor of a then b is not a factor of a + 1.
Order and factors
If b is a factor of a then b ≤ a. The converse, of course, is not true.
Effectively, b ≤ a means that b + h = a for a no negative integer h. If b is a factor of a then bq = a where q is a positive integer.
If b = a also b ≤ a; in this case, q = 1, h = 0.
If b ≠ a, then bq = a can be written as b + b(q -1) = a which means that b ≤ a.
In this case, h = b(q -1), where q > 1.
Example: 71 is a factor of 497 (71 × 7 = 497) and 71 + 71 × (7 – 1) = 497. Therefore 71 ≤ 497.
Concept of prime number
In above examples about the factors of integers it can be seen that the list of factors of a number includes 1 and the number itself.
This happen for any positive integer n: 1 is a factor of n since 1 × n = n. Also n is a factor of n since n × 1 = n.
1 and n are called trivial factors of a positive integer n.
A number p is prime iff their factors are 1 and p only.
A number p is prime iff their factors are 1 and p only.
In above examples, 499 is prime.
The sieve of Eratostenes
A method to obtain a list of succesive prime numbers consists in writing a list of positive integers from 2 on, as large as desired. Next, croos out all the multiples of 2, all the multiples of 3, all the multiples of 5, and so on, continuing with the next number not crossed. The remaining numbers constitute a list of primes.
The following is a sieve for integers between 2 and 30. The excluded numbers are in color, different of black.
2, 3,4, 5, 6, 7, 8, 9 10 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
There are in red the multiples of 2; in blue, the multiples of 3 which are not multiples of 2; in purple, the multiples of 5 which are not multiples of 2 or 3.In black, the prime numbers, from 2 not greater than 30: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}.
{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97}.
For such a set of data it can be done a frequency table like the following:
The following is a sieve for integers between 2 and 30. The excluded numbers are in color, different of black.
2, 3,
There are in red the multiples of 2; in blue, the multiples of 3 which are not multiples of 2; in purple, the multiples of 5 which are not multiples of 2 or 3.In black, the prime numbers, from 2 not greater than 30: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}.
Frequencies and histograms
The set of prime numbers not greater than 100 is{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97}.
For such a set of data it can be done a frequency table like the following:
Interval
|
Frecuency
|
1 a 20
|
8
|
20 a 40
|
4
|
40 a 60
|
5
|
60-80
|
5
|
80-100
|
3
|
And the information can be presented as an histogram like the following:
In the following list (obtained from Wolfram Mathematica) are included the first 420primes between 1 and 3000.
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601,1607,1609,1613,1619,1621,1627,1637,1657,1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,1741,1747,1753,1759,1777,1783,1787,1789,1801,1811,1823,1831,1847,1861,1867,1871,1873,1877,1879,1889,1901,1907,1913,1931,1933,1949,1951,1973,1979,1987,1993,1997,1999,2003,2011,2017,2027,2029,2039,2053,2063,2069,2081,2083,2087,2089,2099,2111,2113,2129,2131,2137,2141,2143,2153,2161,2179,2203,2207,2213,2221,2237,2239,2243,2251,2267,2269,2273,2281,2287,2293,2297,2309,2311,2333,2339,2341,2347,2351,2357,2371,2377,2381,2383,2389,2393,2399,2411,2417,2423,2437,2441,2447,2459,2467,2473,2477,2503,2521,2531,2539,2543,2549,2551,2557,2579,2591,2593,2609,2617,2621,2633,2647,2657,2659,2663,2671,2677,2683,2687,2689,2693,2699,2707,2711,2713,2719,2729,2731,2741,2749,2753,2767,2777,2789,2791,2797,2801,2803,2819,2833,2837,2843,2851,2857,2861,2879,2887,2897
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601,1607,1609,1613,1619,1621,1627,1637,1657,1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,1741,1747,1753,1759,1777,1783,1787,1789,1801,1811,1823,1831,1847,1861,1867,1871,1873,1877,1879,1889,1901,1907,1913,1931,1933,1949,1951,1973,1979,1987,1993,1997,1999,2003,2011,2017,2027,2029,2039,2053,2063,2069,2081,2083,2087,2089,2099,2111,2113,2129,2131,2137,2141,2143,2153,2161,2179,2203,2207,2213,2221,2237,2239,2243,2251,2267,2269,2273,2281,2287,2293,2297,2309,2311,2333,2339,2341,2347,2351,2357,2371,2377,2381,2383,2389,2393,2399,2411,2417,2423,2437,2441,2447,2459,2467,2473,2477,2503,2521,2531,2539,2543,2549,2551,2557,2579,2591,2593,2609,2617,2621,2633,2647,2657,2659,2663,2671,2677,2683,2687,2689,2693,2699,2707,2711,2713,2719,2729,2731,2741,2749,2753,2767,2777,2789,2791,2797,2801,2803,2819,2833,2837,2843,2851,2857,2861,2879,2887,2897
From this list it can be registered the frequency with which prime numbers appear in successive intervals of 100 integers as it can be seen in the following table.
Interval
|
Frecuency
|
1 a 100
|
25
|
100 a 200
|
21
|
200 a 300
|
16
|
300 a 400
|
16
|
400 a 500
|
17
|
500 a 600
|
14
|
600 a 700
|
16
|
700 a 800
|
14
|
800 a 900
|
15
|
900 a 1000
|
14
|
1000 a 1100
|
16
|
1100 a 1200
|
12
|
1200 a 1300
|
15
|
1300 a 1400
|
11
|
1400 a 1500
|
17
|
1500 a 1600
|
12
|
1600 a 1700
|
15
|
1700 a 1800
|
12
|
1800 a 1900
|
12
|
1900 a 2000
|
13
|
2000 a 2100
|
14
|
2100 a 2200
|
10
|
2200 a 2300
|
15
|
2300 a 2400
|
15
|
2400 a 2500
|
10
|
2500 a 2600
|
11
|
2600 a 2700
|
15
|
2700 a 2800
|
14
|
2800 a 2900
|
12
|
A corresponding hystogram is the following:
It can be seen certain regularity if one observe them with an elastic criterion not enough however to predict a general behavior.
It can be perceived nevertheless a light tendency to decrease in the number of prime items as the sequence advance.
Distance between two consecutive prime numbers
Experimentally it can be studied another chatacteristic, consisting in determine the differences between each two consecutive prime numbers from a given list. For prime numbers not grater than 100 a greatest distance of 8 places is obtained. It is produced between 89 and 97. It follows a list of named distances.
1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8
For the first 420 prime numbers the corresponding distances are:
1,2,2,4,2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,14,4,6,2,10,2,6,6,4,6,6,2,10,2,4,2,12,12,4,2,4,6,2,10,6,6,6,2,6,4,2,10,14,4,2,4,14,6,10,2,4,6,8,6,6,4,6,8,4,8,10,2,10,2,6,4,6,8,4,2,4,12,8,4,8,4,6,12,2,18,6,10,6,6,2,6,10,6,6,2,6,6,4,2,12,10,2,4,6,6,2,12,4,6,8,10,8,10,8,6,6,4,8,6,4,8,4,14,10,12,2,10,2,4,2,10,14,4,2,4,14,4,2,4,20,4,8,10,8,4,6,6,14,4,6,6,8,6,12,4,6,2,10,2,6,10,2,10,2,6,18,4,2,4,6,6,8,6,6,22,2,10,8,10,6,6,8,12,4,6,6,2,6,12,10,18,2,4,6,2,6,4,2,4,12,2,6,34,6,6,8,18,10,14,4,2,4,6,8,4,2,6,12,10,2,4,2,4,6,12,12,8,12,6,4,6,8,4,8,4,14,4,6,2,4,6,2,6,10,20,6,4,2,24,4,2,10,12,2,10,8,6,6,6,18,6,4,2,12,10,12,8,16,14,6,4,2,4,2,10,12,6,6,18,2,16,2,22,6,8,6,4,2,4,8,6,10,2,10,14,10,6,12,2,4,2,10,12,2,16,2,6,4,2,10,8,18,24,4,6,8,16,2,4,8,16,2,4,8,6,6,4,12,2,22,6,2,6,4,6,14,6,4,2,6,4,6,12,6,6,14,4,6,12,8,6,4,26,18,10,8,4,6,2,6,22,12,2,16,8,4,12,14,10,2,4,8,6,6,4,2,4,6,8,4,2,6,10,2,10,8,4,14,10,12,2,6,4,2,16,14,4,6,8,6,4,18,8,10
A corresponding histogram is the following:
In above list it can be observed notable variations in studied distances. For instance, the distances not greater than 5 are the ones with more frequency, followed by the ones between 5 and 10, between 10 and 15,and so on.
The named distance is 1, only for the first two numbers in the list, because in the remaining cases if 1 is added an even number is obtained. The number 2 is the only even number which is prime.
The distances, or number of places separating a prime to the next prime in the above sequence, varie between 1 and 34. The distance 34 corresponds to consecutive prime numbers 1327 and 1361, printed in red in above sequence.
These investigations, with statistic flavor, have the aim of finding some regularity which allows to predict the behavior of the sequence of prime numbers and, may be, to find a formula to generate prime numbers or determine how many primes are there which are less than any given integer.
Finite or infinite number of primes?
In “Introduction to Number Theory”, T. Nagell states that there are not primes between 1327 and 1361. A jump of 34 places, as we have seen before. Also he finds the same jump for 8467 and 8501.
Starting with the above list of 420 primes, it cannot be predicted a lot about the behavior of this sequence, except that it is increasing and it seems that the number of items decrease as the numbers in the natural sequence increase. In lists that have been obtained, with or without computers, it can be seen the tendency to scarcity for greater values. One of those lists, with 10.000 items was done in 1657. Another, in 1770 had 102.000 elements (Taken from “Recreations in the theory of Numbers” by A. H. Beiler.) .
Powerful computers have produced millions of prime numbers. Nevertheless the named scarcity persists. For instance, there are not prime numbers between 396733 and 396833, a 100 places jump. This could induce to think that for a sufficiently great number there are not primes at all.
However, a theorem included in Euclid's Elements, book IX, states that the number of primes is infinite.
To be proved: given any prime number p, it is always feasible to find at least one prime number greater than p.
The proof is by contradiction.
The prime numbers can be listed as follows: p1 = 2, p2 = 3, p3 = 5, …, pt .
Let pt be the gratest prime number.
Construct the number m such that p1 × p2 × p3 × … × pt = m.
That is, 2 × 3 × 5 × … × pt = m.
It follows that every prime in the list p1 , p2 , p3 , … , pt is a factor of m. But no item of that list can be a factor of m + 1 (remainder would be 1).
If it happens that m + 1 is prime, then at least a prime greater than pt (the supposed greatest prime in the list) have been found.
In each of above situations a contradiction with the fact that pt is the greatest prime number in the list is obtained.
The conclusion is that the number of primes is infinite.
To be proved: given any prime number p, it is always feasible to find at least one prime number greater than p.
The proof is by contradiction.
The prime numbers can be listed as follows: p1 = 2, p2 = 3, p3 = 5, …, pt .
Let pt be the gratest prime number.
Construct the number m such that p1 × p2 × p3 × … × pt = m.
That is, 2 × 3 × 5 × … × pt = m.
It follows that every prime in the list p1 , p2 , p3 , … , pt is a factor of m. But no item of that list can be a factor of m + 1 (remainder would be 1).
If it happens that m + 1 is prime, then at least a prime greater than pt (the supposed greatest prime in the list) have been found.
If it happens that m + 1 is not prime then it must exist a prime factor pv of m + 1, different from each of p1, p2, p3, …, pt which necessarily had to be greater than pt (the supposed greatest prime in the list).
In each of above situations a contradiction with the fact that pt is the greatest prime number in the list is obtained.
The conclusion is that the number of primes is infinite.
For a better undersatanding of above reasoning, suppose that pt = 7 is the greatest of all the primes. The product 2 × 3 × 5 × 7 (i.e. 210) has 2, 3, 5, 7 as factors. None of them is factor of 211. As 211 resulted to be prime, there is a situation in which has been found a prime greater than the supposed gratest prime, in this case 7.
For pt = 13 as the greatest of all the primes, the corresponding product is
2 × 3 × 5 × 7 × 11 × 13 (i.e. m =30030) . The number 3031 is not prime; its factors are 1, 59, 509, 30031. The number 59 is prime and is grater than 13.
2 × 3 × 5 × 7 × 11 × 13 (i.e. m =30030) . The number 3031 is not prime; its factors are 1, 59, 509, 30031. The number 59 is prime and is grater than 13.
Formulae to obtain prime numbers
There have been many intends to find formulas to generate prime numbers some of them are useful to certain extent. One of them is n2 + n + 17 which produces primes for values uf n from 1 to 16: the primes obtained are, 19, 23, 29, 37, 47, 59, 73, 89, 107, 127, 149, 173, 199, 227, 257, 289. For n = 17 the formula gives 323 which is not prime; their factors are 1, 17, 19, 323. But for n = 18 the formula gives 359, which is prime. Also for n = 50 it gives 2657, which is prime. For n = 25 the formula gives 667 which is not prime; its factors are 1, 23, 29, 667. The formula is unsure.
Euler's formula n2 + n + 41 gives prime numbers for n not greater than 40:
43, 47, 53, 61, 71, 83, 97, 113, 131, 151, 173, 197, 223, 251, 281, 313, 347, 383, 421, 461, 503,
547, 593, 641, 691, 743, 797, 853, 911, 971, 1033, 1097, 1163, 1231, 1301, 1373, 1447, 1523,
1601.
For n = 41 the formula gives 1763, which is not prime; its factors are 1, 41, 43, 1763.
For n = 41 the formula gives 1763, which is not prime; its factors are 1, 41, 43, 1763.
The function π(n)
For a positive integer n this function gives the number of primes not greater than n. The following table gives some values of π(n) for certain values of n. They can be obtained directly from the above list of 420 prime numbers.
n
|
10
|
100
|
1000
|
2000
|
2900
|
π(n)
|
4
|
25
|
168
|
303
|
420
|
The use of the grrek character π is traditional. It has not relation with the numeric value associated with a circle for instance.
Legendre stated a good approximation: π(n) ~ n/ln n
The following table gives rational approximations for considered instances. L is useful only for large values of n.
n
|
10
|
100
|
1000
|
2000
|
2900
|
π(n)
|
4
|
25
|
168
|
303
|
420
|
L
|
4.343
|
21.715
|
144.765
|
263.127
|
363.72
|
Gauss used a more precise approximation with a formula involving a logarithmic integral
Modern technology faccilitates to obtain precise and fast results like the former or determine if a number is prime and identify the next prime in a given list.
The fundamental theorem of arithmetic
This theorem states that each integer grater than 1 either is prime or composite. In the last case it can be expressed uniquely as the product of their prime factors.
In the named product a factor can appear one or more times. The uniqueness of factoring does not refer to the order in which factors appear. This means that each integer is completely characterized by the set of its prime factors.
For instance, {2, 3, 2, 7, 5} characterizes the integer 420. Te set {5, 7, 7, 11, 5, 2, 7} characterizes the integer 188650.
A question to be asked could be: are there any rare number which is not prime and cannot be expresed as a product of primes?
The answer is no, and this can be sustained by contradiction.
Suppose that m is the least of such rare numbers. Not being prime, it has at least two factors a, b, other than 1. The numbers a, b are smaller than m; so, they are not rare. If both of a, b are not primes, then at least one of them can be factored in primes. This means tha m is not rare. With this contradiction it has been proved that rare numbers do not exist.
Symbolically, if n is an integer greater than 1, then n can be expressed with the next product formula:
Where p1, p2, …, pr are the prime factors of n and αi are natural numbers which indicate the number of times of appearing of each pi.
For example, 188650 = 21 × 52 × 73 × 111.
Conjectures
Some important conjectures aboutprime numbers have been formulated:
Every even integer n, greater of equal to 6 can be expressed as the sum of two odd primes
Example: 36 = 7 + 29 (also 13 + 23, 17 + 19)
Every odd number n greater or equal to 9 can be expressed as the sum of three odd primes.
Example: 35 = 3 + 13 + 19 (also 7 + 11 + 17)
There are many pair of primes which differ in two units. For instance, (5, 7), (29, 31), (1019,1021), (2591, 2593). They are called twin primes. A
Another conjecture is: there are infinite twin primes.
A final conjecture for now: there are infinite palindrome primes. Examples: 11, 101, 131, 797, 3113.
Prime numbers and numeric congruences
Fermat stated the following theorem: if p is a prime number, then xp is congruent to x modulo p, for any positive integer x.
This means that p is a factor of xp – x.
For instance, 3 is a factor of 83 – 8. (3 is a factor of 504). In other words, 83 is congruent to 8, modulo 3.
Congruence modulo 3 allows to classify the set of positive integers in three classes, namely,
class of 0 = {0, 3, 6, 9, 12, 15,…}
class of 1 = {1, 4, 7, 10, 13, …}
class of 2 = {2, 5, 8, 11, 14, …}
To know in which of these classes is,for instance, the number 7435, it is enough to divide 7435 by 3 and obtain the reminder; in this case, the remainter is 1. So, 7435 is congruent with 1, modulo3.
Para saber a cuál de estas clases pertenece, por ejemplo, el número 7435, basta dividir a este número por 3 y observar cuál es el residuo. En este caso, el residuo es 1. Por lo tanto, se puede asegurar que 7435 está en la clase del 1. Dicho de otro modo, 7435 es congruente con 1, modulo 3.
Another example: 5 must be a factor of 125 - 12. (5is a factor of 248820) This means that 125is congruent with 12, modulo 5.
Congruence modulo 5 allows to classify the set of positive integers in five classes. To know in which of these classes is, for instance, the number 7435, it is enough to divide by 5 and obtain the reminder. In this case is 0: {0, 5, 10, 15, ...}.
Another example: 5 must be a factor of 125 - 12. (5is a factor of 248820) This means that 125is congruent with 12, modulo 5.
Congruence modulo 5 allows to classify the set of positive integers in five classes. To know in which of these classes is, for instance, the number 7435, it is enough to divide by 5 and obtain the reminder. In this case is 0: {0, 5, 10, 15, ...}.
A secret code
A way to make a secret code is to assign a numeric code without giving the (prime) number which acts as modulo. For instance, the number 43617 is in the class 0 (or 3), if the modulo is 3. But is in the class 2, if the modulo is 5.The modulo may be a number with many figures which might turn difficult to guess the class to which a given number belongs. For instance, if the number acting like modulo is 1033 then the number 487938 is in the class of 362, one of the 1033 classes of the partition.
Modern strategies are more sophisticate, but they are relation with numeric properties as the former.
Merssenne and Fermat numbers
A Mersenne number is a prime of the form 2p – 1, where p is a prime. With values 2, 3, 5, 7, can be obtained Mersenne's primes. For p = 11 the formula gives 2047 which is not prime (23 and 89 are factors of it). For p = 13 the number obtained is 8191, which is prime.Another conjecture is: there are infinite Mersenne's primes.
If 2n + 1 is a prime number, then n is a power of 2 and the number obtained is a Fermat's prime number. examples: for n = 4 = 22 the result is 17. For n = 8 = 23 the result is 257. For n = 16 = 24 the result is 257, which is prime. For n = 16 = 24 the result is 131073, not prime (3 and 43691 are factors of it).
No hay comentarios:
Publicar un comentario