MY DIGITAL NOTEBOOK

A Personal Blog On Mathematical Sciences and Technology

Home » Posts tagged 'Leonhard Euler'

Tag Archives: Leonhard Euler

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.

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.