Home » Posts tagged 'Prime Numbers'

Tag Archives: Prime Numbers

Euler’s (Prime to) Prime Generating Equation

Tuesday, March 26th, 2013 09:35 / Leave a Comment

The greatest number theorist in mathematical universe, Leonhard Euler had discovered some formulas and relations in number theory, which were based on practices and were correct to limited extent. The prime generating equation by Euler is a binomial which is actually very specific and yields more primes than any other relations out there in number theory. Euler told that the equation $f(x)=x^2+x+k$ yields many prime numbers with the values of x being input from x=0 to x=k-2; k being a prime.

Let’s see how many primes we can get by using different values of k and x:

Serial Number	Value of k (prime)	Value of x (from x=0 to x=k-2)	Value of f(x)=(x^2+x)+k	Not a Prime?
1	2	0	2
2	3	0	3
3		1	5
4	5	0	5
5		1	7
6		2	11
7		3	17
8	7	0	7
9		1	9	No
10		2	13
11		3	19
12		4	27	No
13		5	37
14	11	0	11
15		1	13
16		2	17
17		3	23
18		4	31
19		5	41
20		6	53
21		7	67
22		8	83
23		9	101
24	13	0	13
25		1	15	No
26		2	19
27		3	25	No
28		4	33	No
29		5	43
30		6	55	No
31		7	69	No
32		8	85	NO
33		9	103
34		10	123	No
35		11	145	No
36	17	0	17
37		1	19
38		2	23
39		3	29
40		4	37
41		5	47
42		6	59
43		7	73
44		8	89
45		9	107
46		10	127
47		11	149
48		12	173
49		13	199
50		14	227
51		15	257
52	19	0	19
53		1	21
54		2	25	No
55		3	31
56		4	39	No
57		5	49
58		6	61
59		7	75	No
60		8	91	No
61		9	109
62		10	129	No
63		11	151
64		12	175	No
65		13	201	No
66		14	229
67		15	259
68		16	291
69		17	325	No
70	23	0	23
71		1	25	No
72		2	29
73		3	35	No
74		4	43
75		5	53
76		6	65	No
77		7	79
78		8	95	No
79		9	113
80		10.	133
81		11	155	No
82		12	179
83		13	205	No
84		14	233
85		15	263
86
87		16	295	No
88		17	329
89		18	365	No
90		19	403
91		20	443
92		21	485	No

The above table yields many prime numbers, which again can be put at the place of k and so on the table can be progressed.

According to Euler, 41 was the most appropriate value of k yielding more prime numbers than any other k. In the list below, each value of f(x) is a prime for k=41:

k 41	x 0	f(x) 41
	1	43
	2	47
	3	53
	4	61
	5	71
	6	83
	7	97
	8	113
	9	131
	10	151
	11	173
	12	197
	13	223
	14	251
	15	281
	16	313
	17	347
	18	383
	19	421
	20	461
	21	503
	22	547
	23	593
	24	641
	25	691
	26	743
	27	797
	28	853
	29	911
	30	971
	31	1033
	32	1097
	33	1163
	34	1231
	35	1301
	36	1373
	37	1447
	38	1523
	39	1601

So, the Euler’s Prime Generating Equation can be written as
$f(x) = x^2+x+41$ ; where x is an integer ranging from 0 to 39.

Wait. What if we increase the value of x beyond the limit of 39? What will we get?

The next values of f(x) in this series would be 1681, 1763, 1847, 1933, 2021, 2111, 2203, 2297, 2393, … .
Are all these prime numbers too? The answer is no. 1681 is not a prime number, neither are 1763 and 2021. Though all others are prime numbers.

A Trip to Mathematics: Part IV Numbers

Monday, November 21st, 2011 16:07 / Leave a Comment

If logic is the language of mathematics, Numbers are the alphabet. There are many kinds of number we use in mathematics, but at a broader aspect we may categorize them in two categories:
1. Countable Numbers
2. Uncountable Numbers
The names are enough to explain the properties of above numbers. The numbers which can be counted in nature are called Countable Numbers and the numbers which can not be counted are called Uncountable Numbers.

Well, this is not the correct way to classify the bunch of types of numbers. We have some formal names for special types of numbers, like Real numbers, Complex Numbers, Rational Numbers, Irrational Numbers etc.. We shall discuss these non-interesting numbers (let me say them non-interesting) at first and then some interesting numbers(those numbers are really interesting to learn). Although in this post I have concisely described the classification, I will rigorously discuss them later.
Let me start this discussion with the memorable quote by Leopold Kronecker:

“God created the natural numbers, and all the rest is the work of man.”

What does it mean? What did Kronecker think when he made this quote? Why is this quote true? —First part of this article is based on this discussion.
Actually, he meant to say that all numbers, like Real Numbers, Complex Numbers, Fractions, Integers, Non-integers etc. are made up of the numbers given by God to the human. These God Gifted numbers are actually called Natural Numbers. Natural Numbers are the numbers which are used to count things in nature.

Eight pens, Eighteen trees, Three Thousands people etc. are measure of natural things and thus ‘Eight’, ‘Eighteen’, ‘Three Thousands’ etc. are called natural numbers and we represent them numerically as ’8′, ’18′, ’3000′ respectively. So, if 8, 18, 3000 are used in counting natural things, are natural numbers. Similarly, 1, 2, 3, 4, and other numbers are also used in counting things —thus these are also Natural Numbers.

Let we try to form a set of Natural Numbers. What will we include in this set?

1?    (yes!).
2?    (yes).
3? (yes).
….
1785?    (yes)
…and so on.

This way, after including all elements we get a set of natural numbers {1, 2, 3, 4, 5, …1785, …, 2011,….}. This set includes infinite number of elements. We represent this set by Borbouki’s capital letter N, which looks like $\mathbb{N}$ or bold capital letter N ( $\mathbf{N}$ where N stands for NATURAL. We will define the set of all natural numbers as:

$\mathbb{N} := \{ 1, 2, 3, 4, \ldots, n \ldots \}$ .

It is clear from above set-theoretic notation that $n$ -th element of the set of natural numbers is $n$ .
In general, if a number $n$ is a natural number, we right that $n \in \mathbb{N}$ .
Please note that some mathematicians (and Wolfram Research) treat ’0′ as a natural number and state the set as $\mathbb{N} :=\{0, 1, 2, \ldots, n-1, \ldots \}$ , where $n-1$ is the nth element of the set of natural numbers; but we will use first notion since it is broadly accepted.

Now we shall try to define Integers in form of natural numbers, as Kronecker’s quote demands. Integers (or Whole numbers) are the numbers which may be either positives or negatives of natural numbers including 0.
Few examples are 1, -1, 8, 0, -37, 5943 etc.
The set of integers is denoted by $\mathbb{Z}$ or $\mathbf{Z}$ (here Z stands for ‘Zahlen‘, the German alternative of integers). It is defined by
$\mathbb{Z} := \{ \pm n: n \in \mathbb{N} \} \cup \{0\}$
i.e., $\mathbb{Z} := \{\ldots -3, -2, -1, 0, 1, 2, 3 \ldots \}$ .

Now, if we again consider the statement of Kronecker, we might ask that how could we prepare the integer set $\mathbb{Z}$ by the set $\mathbb{N}$ of natural numbers? The construction of $\mathbb{Z}$ from $\mathbb{N}$ is motivated from the requirement that every integer can be expressed as difference of two positive integers (i.e., Natural Numbers). Let $a,b,c,d \in \mathbb{N}$ and a relation ρ is defined on $\mathbb{N} \times \mathbb{N}$ by $(a,b) \rho (c,d)$ if and only if $a+d = b+c$ . The relation ρ is an equivalence relation and the equivalence classes under ρ are called integers and defined as $\mathbb{Z} := \mathbb{N} \times \mathbb{N} /\rho$ . Now we can define set of integers by an easier way, as $\mathbb{Z}:= \{a-b; \ a,b \in \mathbb{N}\}$ . Thus an integer is a number which can be produced by difference of two or more natural numbers. And similarly as converse defintion, positive integers are called Natural Numbers.
After Integers, we head to rational numbers. Say it again– ‘ratio-nal numbers‘ –numbers of ratio.

Image via Wikipedia

A rational number $\frac{p}{q}$ is defined as a ratio of an integer p and a non-zero integer q. (Well that is not a perfect definition, but as an introduction it is great for understanding.) The set of rational numbers is defined by $\mathbb{Q}$ .
Once integers are formed, we can form Rational (and Irrational numbers: numbers which are not rational ) using integers.
We consider an ordered pair $(p,q):=\mathbb{Z} \times (\mathbb{Z} \setminus \{0 \})$ and another ordered pair $(r,s):=\mathbb{Z} \times (\mathbb{Z} \setminus \{0\})$ and define a relation ρ by $(p,q) \rho (r,s) \iff ps=qr$ for $p,q,r,s \in \mathbb{Z}, \ q, r \ne 0$ . Then ρ is an equivalence relation of rationality, class (p,q). The set $\mathbb{Z} \times (\mathbb{Z} \setminus \{0\})/\rho$ is denoted by $\mathbb{Q}$ (and the elements of this set are called rational numbers).
In practical understandings, the ratio of integers is a phrase which will always help you to define the rational numbers. Examples are $\frac{6}{19}, \ \frac{-1}{2}=\frac{-7}{14}, \ 3\frac{2}{3}, \ 5=\frac{5}{1} \ldots$ . Set of rational numbers includes Natural Numbers and Integers as subsets.
Consequently, irrational numbers are those numbers which can not be represented as the ratio of two integers. For example $\pi, \sqrt{3}, e, \sqrt{11}$ are irrationals.
The set of Real Numbers is a relatively larger set, including the sets of Rational and Irrational Numbers as subsets. Numbers which exist in real and thus can be represented on a number line are called real numbers. As we formed Integers from Natural Numbers; Rational Numbers from Integers, we’ll form the Real numbers by Rational numbers.
The construction of set $\mathbb{R}$ of real numbers from $\mathbb{Q}$ is motivated by the requirement that every real number is uniquely determined by the set of rational numbers less than it. A subset $L$ of $\mathbb{Q}$ is a real number if L is non-empty, bounded above, has no maximum element and has the property that for all $x, y \in \mathbb{Q}, x < y$ and $y \in L$ implies that $x \in L$ . Real numbers are the base of Real Analysis and detail study about them is case of study of Real Anlaysis.
Examples of real numbers include both Rational (which also contains integers) and Irrational Numbers.

The square root of a negative number is undefined in one dimensional number line (which includes real numbers only) and is treated to be imaginary. The numbers containing or not containing an imaginary number are called complex numbers.
Some very familiar examples are $3+\sqrt{-1}, \sqrt{-1} =i, \ i^i$ etc. We should assume that every number (in lay approach) is an element of a complex number. The set of complex numbers is denoted by $\mathbb{C}$ . In constructive approach, a complex number is defined as an ordered pair of real numbers, i.e., an element of $\mathbb{R} \times \mathbb{R}$ [i.e., $\mathbb{R}^2$ ] and the set as $\mathbb{C} :=\{a+ib; \ a,b \in \mathbb{R}$ . Complex numbers will be discussed in Complex Analysis more debately.
We verified Kronecker’s quote and shew that every number is sub-product of postive integers (natural numbers) as we formed Complex Numbers from Real Numbers; Real Numbers from Rational Numbers; Rational Numbers from Integers and Integers from Natural Numbers. //
Now we reach to explore some interesting kind of numbers. There are millions in name but few are the follow:
Even Numbers: Even numbers are those integers which are integral multiple of 2. $0, \pm 2, \pm 4, \pm 6 \ldots \pm 2n \ldots$ are even numbers.

Odd Numbers: Odd numbers are those integers which are not integrally divisible by 2. $\pm 1, \pm 3, \pm 5 \ldots \pm (2n+1) \ldots$ are all odd numbers.

Prime Numbers: Any number $p$ greater than 1 is called a prime number if and only if its positive factors are 1 and the number $p$ itself.
In other words, numbers which are completely divisible by either 1 or themselves only are called prime numbers. $2, 3, 5, 7, 11, 13, 17, 19, 23, 29 \ldots$ etc. are prime numbers or Primes. The numbers greater than 1, which are not prime are called Composite numbers.
Twin Primes: Consecutive prime numbers differing by 2 are called twin primes. For example 5,7; 11,13; 17,19; 29,31; … are twin primes.

Pseudoprimes: Chinese mathematicians claimed thousands years ago that a number $n$ is prime if and only if it divides $2^n -2$ . In fact this conjecture is true for $n \le 340$ and false for upper numbers because first successor to 340, 341 is not a prime ( $31 \times 11$ ) but it divides $2^{341}-2$ . This kind of numbers are now called Pseudoprimes. Thus, if n is not a prime (composite) then it is pseudoprime $\iff n | 2^n-2$ (read as ‘n divides 2 powered n minus 2‘). There are infinitely many pseudoprimes including 341, 561, 645, 1105.

Carmichael Numbers or Absolute Pseudoprimes: There exists some pseudoprimes that are pseudoprime to every base $a$ , i.e., $n | a^n -a$ for all integers $a$ . The first Carmichael number is 561. Others are 1105, 2821, 15841, 16046641 etc.

e-Primes: An even positive integer is called an e-prime if it is not the product of two other even integers. Thus 2, 6, 10, 14 …etc. are e-primes.

Germain Primes: An odd prime p such that 2p+1 is also a prime is called a Germain Prime. For example, 3 is a Germain Prime since $2\times 3 +1=7$ is also a prime.
Relatively Prime: Two numbers are called relatively prime if and only their greatest common divisor is 1. In other words, if two numbers are such that no integer, except 1, is common between them when factorizing. For example: 7 and 9 are relatively primes and same are 15, 49.

Perfect Numbers: A positive integer n is said to be perfect if n equals to the sum of all its positive divisors, excluding n itself. For example 6 is a perfect number because its divisors are 1, 2, 3 and 6 and it is obvious that 1+2+3=6. Similarly 28 is a perfect number having 1, 2, 4, 7, 14 (and 28) as its divisors such that 1+2+4+7+14=28. Consecutive perfect numbers are 6, 28, 496, 8128, 33550336, 8589869056 etc.

Mersenne Numbers and Mersenne Primes: Numbers of type $M_n=2^n-1; \ n \ge 1$ are called Mersenne Numbers and those Mersenne Numbers which happen to be Prime are called Mersenne Primes. Consecutive Mersenne numbers are 1, 3 (prime), 7(prime), 15, 31(prime), 63, 127.. etc.

Catalan Numbers: The Catalan mumbers, defined by $C_n = \dfrac{1}{n+1} \binom{2n}{n} = \dfrac{(2n)!}{n! (n+1)!} \ n =0, 1, 2, 3 \ldots$ form the sequence of numbers 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …

Triangular Number: A number of form $\dfrac{n(n+1)}{2} \ n \in \mathbb{N}$ represents a number which is the sum of n consecutive integers, beginning with 1. This kind of number is called a Triangular number. Examples of triangular numbers are 1 (1), 3 (1+2), 6 (1+2+3), 10(1+2+3+4), 15(1+2+3+4+5) …etc.

Square Number: A number of form $n^2 \ n \in \mathbb{N}$ is called a sqaure number.
For example 1 ( $1^2$ ), 4 ( $2^2$ ), 9( $3^2$ ), 16 ( $4^2$ )..etc are Square Numbers.

Palindrome: A palindrome or palindromic number is a number that reads the same backwards as forwards. For example, 121 is read same when read from left to right or right to left. Thus 121 is a palindrome. Other examples of palindromes are 343, 521125, 999999 etc.

A Trip To Mathematics: Part II Set(Basics) (wpgaurav.wordpress.com)
Do complex numbers really exist? (math.stackexchange.com)
Definitions (gowers.wordpress.com)

Fermat Numbers

Wednesday, September 28th, 2011 06:00 / Leave a Comment

Fermat Number, a class of numbers, is an integer of the form $F_n=2^{2^n} +1 \ \ n \ge 0$ .

For example: Putting $n := 0,1,2 \ldots$ in $F_n=2^{2^n}$ we get $F_0=3$ , $F_1=5$ , $F_2=17$ , $F_3=257$ etc.

Fermat observed that all the integers $F_0, F_1, F_2, F_3, \ldots$ were prime numbers and announced that $F_n$ is a prime for each natural value of $n$ .

In writing to Prof. Mersenne, Fermat confidently announced:

I have found that numbers of the form $2^{2^n}+1$ are always prime numbers and have long since signified to analysts the truth of this theorem.

However, he also accepted that he was unable to prove it theoretically. Euler in 1732 negated Fermat’s fact and told that $F_1 -F_4$ are primes but $F_5=2^{2^5} =4294967297$ is not a prime since it is divisible by 641.
Euler also stated that all Fermat numbers are not necessarily primes and the Fermat number which is a prime, might be called a Fermat Prime. Euler used division to prove the fact that $F_5$ is not a prime. The elementary proof of Euler’s negation is due to G. Bennett.

Theorem:

The Fermat number $F_5$ is divisible by $641$ i.e., $641|F_5$ .

Proof:

As defined $F_5 :=2^{2^5}+1=2^{32}+1 \ \ldots (1)$

Factorising $641$ in such a way that $641=640+1 =5 \times 128+1 \\ =5 \times 2^7 +1$
Assuming $a=5 \bigwedge b=2^7$ we have $ab+1=641$ .

Subtracting $a^4=5^4=625$ from 641, we get $ab+1-a^4=641-625=16=2^4 \ \ldots (2)$ .

Now again, equation (1) could be written as
$F_5=2^{32}+1 \\ \ =2^4 \times {(2^7)}^4+1 \\ \ =2^4 b^4 +1 \\ \ =(1+ab-a^4)b^4 +1 \\ \ =(1+ab)[a^4+(1-ab)(1+a^2b^2)] \\ \ =641 \times \mathrm{an \, Integer}$
Which gives that $641|F_n$ .

Mathematics is on its progression and well developed now but it is yet not confirmed that whether there are infinitely many Fermat primes or, for that matter, whether there is at least one Fermat prime beyond $F_4$ . The best guess is that all Fermat numbers $F_n>F_4$ are composite (non-prime).
A useful property of Fermat numbers is that they are relatively prime to each other; i.e., for Fermat numbers $F_n, F_m \ m > n \ge 0$ , $\mathrm{gcd}(F_m, F_n) =1$ .

Following two theorems are very useful in determining the primality of Fermat numbers:

Pepin Test:

For $n \ge 1$ , the Fermat number $F_n$ is prime $\iff 3^{(F_n-1)/2} \equiv -1 \pmod {F_n}$

Euler- Lucas Theorem

Any prime divisor $p$ of $F_n$ , where $n \ge 2$ , is of form $p=k \cdot 2^{n+2}+1$ .

Fermat numbers ( $F_n$ ) with $n=0, 1, 2, 3, 4$ are prime; with $n=5,6,7,8,9,10,11$ have completely been factored; with $n=12, 13, 15, 16, 18, 19, 25, 27, 30$ have two or more prime factors known; with $n=17, 21, 23, 26, 28, 29, 31, 32$ have only one prime factor known; with $n=14,20,22,24$ have no factors known but proved composites. $F_{33}$ has not yet been proved either prime or composite.