User:Karsten Meyer/Fingerprint

The account of this former contributor was not re-activated after the server upgrade of March 2022.

"Fingerprints" of the numbers

Introduction

The Content of this subpage may Origin research, but it is important for me. Some readers may find it interesting. If you understand german, you find a similar content here: de.wikibooks.org/wiki/Pseudoprimzahlen:_Potenzen_und_Modulo.

Exponantiation

We want to create a table of numbers. In the first column, we write the sequence of natural numbers:

1

2

3

4

5

6

...

In every row, we write the exponatiation of each number:

	n	1	2	3	4	5	6	7	8	9	...
a
1		1	1	1	1	1	1	1	1	1	...
2		2	4	8	16	32	64	128	256	512	...
3		3	9	27	81	243	729	2187	6561	19683	...
4		4	16	64	256	1024	4096	16384	65536	262144	...
5		5	25	125	625	3125	15625	78125	390625	1953125	...
6		6	36	216	1296	7776	46656	279936	1679616	10077696	...
7		7	49	343	2401	16807	117649	823543	5764801	40353607	...
8		8	64	512	4096	32768	262144	2097152	16777216	134217728	...
9		9	81	729	6561	59049	531441	4782969	43046721	387420489	...
10		10	100	1000	10000	100000	1000000	10000000	100000000	1000000000	...
11		11	121	1331	14641	161051	1771561	19487171	214358881	2357947691	...
12		12	144	1728	20736	248832	2985984	35831808	429981696	5159780352	...
..		..	...	...	...	...	...	...	...	...	...

This is the base!

Modulo operation

If i use the Modulo operation, i will get a pattern. I will take two examples for this:

• Modul0 15

	n	1	2	3	4	5	6	7	8	9	10	11	12	...
a
1		1	1	1	1	1	1	1	1	1	1	1	1	...
2		2	4	8	1	2	4	8	1	2	4	8	1	...
3		3	9	12	3	9	12	3	9	12	3	9	12	...
4		4	1	4	1	4	1	4	1	4	1	4	1	...
5		5	10	5	10	5	10	5	10	5	10	5	10	...
6		6	6	6	6	6	6	6	6	6	6	6	6	...
7		7	4	13	7	4	13	7	4	13	7	4	13	...
8		8	4	2	1	8	4	2	1	8	4	2	1	...
9		9	6	9	6	9	6	9	6	9	6	9	6	...
10		10	10	10	10	10	10	10	10	10	10	10	10	...
11		11	1	11	1	11	1	11	1	11	1	11	1	...
12		12	9	3	6	12	9	3	6	12	9	3	6	...
13		13	4	7	1	13	4	7	1	13	4	7	1	...
14		14	1	14	1	14	1	14	1	14	1	14	1	...
15		0	0	0	0	0	0	0	0	0	0	0	0	...
16		1	1	1	1	1	1	1	1	1	1	1	1	...
17		2	4	8	1	2	4	8	1	2	4	8	1	...
18		3	9	12	3	9	12	3	9	12	3	9	12	...
19		4	1	4	1	4	1	4	1	4	1	4	1	...
20		5	10	5	10	5	10	5	10	5	10	5	10	...
21		6	6	6	6	6	6	6	6	6	6	6	6	...
22		7	4	13	7	4	13	7	4	13	7	4	13	...
23		8	4	2	1	8	4	2	1	8	4	2	1	...
24		9	6	9	6	9	6	9	6	9	6	9	6	...
25		10	10	10	10	10	10	10	10	10	10	10	10	...
26		11	1	11	1	11	1	11	1	11	1	11	1	...
27		12	9	3	6	12	9	3	6	12	9	3	6	...
28		13	4	7	1	13	4	7	1	13	4	7	1	...
29		14	1	14	1	14	1	14	1	14	1	14	1	...
30		0	0	0	0	0	0	0	0	0	0	0	0	...
31		1	1	1	1	1	1	1	1	1	1	1	1	...
32		2	4	8	1	2	4	8	1	2	4	8	1	...
33		3	9	12	3	9	12	3	9	12	3	9	12	...
34		4	1	4	1	4	1	4	1	4	1	4	1	...
35		5	10	5	10	5	10	5	10	5	10	5	10	...
36		6	6	6	6	6	6	6	6	6	6	6	6	...
37		7	4	13	7	4	13	7	4	13	7	4	13	...
38		8	4	2	1	8	4	2	1	8	4	2	1	...
39		9	6	9	6	9	6	9	6	9	6	9	6	...
40		10	10	10	10	10	10	10	10	10	10	10	10	...
41		11	1	11	1	11	1	11	1	11	1	11	1	...
42		12	9	3	6	12	9	3	6	12	9	3	6	...
43		13	4	7	1	13	4	7	1	13	4	7	1	...
44		14	1	14	1	14	1	14	1	14	1	14	1	...
45		0	0	0	0	0	0	0	0	0	0	0	0	...
...		...	...	...	...	...	...	...	...	...	...	...	...	...

The single Pattern of Modulo 15 is:

	n	1	2	3	4
a
1		1	1	1	1
2		2	4	8	1
3		3	9	12	3
4		4	1	4	1
5		5	10	5	10
6		6	6	6	6
7		7	4	13	7
8		8	4	2	1
9		9	6	9	6
10		10	10	10	10
11		11	1	11	1
12		12	9	3	6
13		13	4	7	1
14		14	1	14	1
15		0	0	0	0

This pattern will repeat vertical every $15\$ steps, and it will repeat horizontal every $\lambda (15)=4\$ steps. $\lambda (n)\$ means here the Carmichael function.

• Modulo 7

	n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	...
a
1		1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	...
2		2	4	1	2	4	1	2	4	1	2	4	1	2	4	1	2	4	1	...
3		3	2	6	4	5	1	3	2	6	4	5	1	3	2	6	4	5	1	...
4		4	2	1	4	2	1	4	2	1	4	2	1	4	2	1	4	2	1	...
5		5	4	6	2	3	1	5	4	6	2	3	1	5	4	6	2	3	1	...
6		6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	...
7		0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	...
8		1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	...
9		2	4	1	2	4	1	2	4	1	2	4	1	2	4	1	2	4	1	...
10		3	2	6	4	5	1	3	2	6	4	5	1	3	2	6	4	5	1	...
11		4	2	1	4	2	1	4	2	1	4	2	1	4	2	1	4	2	1	...
12		5	4	6	2	3	1	5	4	6	2	3	1	5	4	6	2	3	1	...
13		6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	...
14		0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	...
15		1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	...
16		2	4	1	2	4	1	2	4	1	2	4	1	2	4	1	2	4	1	...
17		3	2	6	4	5	1	3	2	6	4	5	1	3	2	6	4	5	1	...
18		4	2	1	4	2	1	4	2	1	4	2	1	4	2	1	4	2	1	...
19		5	4	6	2	3	1	5	4	6	2	3	1	5	4	6	2	3	1	...
20		6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	...
21		0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	...
22		1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	...
23		2	4	1	2	4	1	2	4	1	2	4	1	2	4	1	2	4	1	...
24		3	2	6	4	5	1	3	2	6	4	5	1	3	2	6	4	5	1	...
25		4	2	1	4	2	1	4	2	1	4	2	1	4	2	1	4	2	1	...
26		5	4	6	2	3	1	5	4	6	2	3	1	5	4	6	2	3	1	...
27		6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	6	1	...
28		0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	...
...		...	...	...	...	...	...	...	...	...	...	...	...	...	...	...	...	...	...	....

The single Pattern of Modulo 7 is:

	n	1	2	3	4	5	6
a
1		1	1	1	1	1	1
2		2	4	1	2	4	1
3		3	2	6	4	5	1
4		4	2	1	4	2	1
5		5	4	6	2	3	1
6		6	1	6	1	6	1
7		0	0	0	0	0	0

This pattern will repeat vertical every $7\$ steps, and it will repeat horizontal every $\lambda (7)=6\$ steps. $\lambda (n)\$ means here the Carmichael function. You will find, that the numbers of the 6th column, exept of the row 7, is 1. You will find also, that the numbers of the 3th column, exept of the row 7, inherit the numbers 1 or 6 (-1 mod 7).

Muster

Zu jeder natürlichen Zahl $n\$ gibt es ein individuelles Erscheinungsbild. Andererseits haben bestimmte Arten von Zahlen Gemeinsamkeiten. Um das, was Zahlen gemeinsam haben, geht es hier:

natural numbers

Natural numbers have a common pattern:

	1	2	3	4	5	6
1:	1	1	1	1	1	1
X:	X	X	X	X	X	X
X:	X	X	X	X	X	X
X:	X	X	X	X	X	X
X:	X	X	X	X	X	X
A:	A	1	A	1	A	1

In der obersten Zeile befinden sich immer Einsen und in der untersten Zeile befinden sich immer im Wechsel A und 1, wobei A für $n-1\$ steht. Dies ist also keine Charakteristik, die für Primzahlen typisch ist.

Primzahlen

Color	Formular
	$a^{\lambda (n)}\$
	$a^{\frac {\lambda (n)}{2}}$

A prime number has a typical pattern:

	1	2	3	4	5	6
1:	1	1	1	1	1	1
X:	X	X	1	X	X	1
X:	X	X	A	X	X	1
X:	X	X	1	X	X	1
X:	X	X	A	X	X	1
A:	A	1	A	1	A	1

Zu der für jede natürliche Zahl typischen Zeilen kommen zwei Charaktaristika bei Primzahlen hinzu:

Erstens die geschlossene Einserspalte

1

1

1

...

in blau gefärbt. Die Einser sind die Werte, welche die Carmichael-Funktion $a^{\lambda (n)}$ zurückliefert.

Zweitens die, ebenfalls geschlossene, Zeile aus Einsern und Zahlen A die die Zahl (n-1) repräsentieren.

1

A

...

Hier sind es die Werte, die die nach der nach Euler modifizierten Funktion $a^{\frac {\lambda (n)}{2}}$ zurückgeliefert werden.

Differenting prime numbers in (4k-1)-form and (4k+1)-form

The structure of the fingerprint of prime numbers of the (4k-1)-form and the4(k+1)-form differ sich in one column:

1 2 3 4 5 6 7 8 9 10 1: 1 1 1 1 1 1 1 1 1 1 2: 2 4 8 5 10 9 7 3 6 1 3: 3 9 5 4 1 3 9 5 4 1 4: 4 5 9 3 1 4 5 9 3 1 5: 5 3 4 9 1 5 3 4 9 1 6: 6 3 7 9 10 5 8 4 2 1 7: 7 5 2 3 10 4 6 9 8 1 8: 8 9 6 4 10 3 2 5 7 1 9: 9 4 3 5 1 9 4 3 5 1 10: 10 1 10 1 10 1 10 1 10 1	1 2 3 4 5 6 7 8 9 10 11 12 1: 1 1 1 1 1 1 1 1 1 1 1 1 2: 2 4 8 3 6 12 11 9 5 10 7 1 3: 3 9 1 3 9 1 3 9 1 3 9 1 4: 4 3 12 9 10 1 4 3 12 9 10 1 5: 5 12 8 1 5 12 8 1 5 12 8 1 6: 6 10 8 9 2 12 7 3 5 4 11 1 7: 7 10 5 9 11 12 6 3 8 4 2 1 8: 8 12 5 1 8 12 5 1 8 12 5 1 9: 9 3 1 9 3 1 9 3 1 9 3 1 10: 10 9 12 3 4 1 10 9 12 3 4 1 11: 11 4 5 3 7 12 2 9 8 10 6 1 12: 12 1 12 1 12 1 12 1 12 1 12 1
Prime number of the (4k+3)-form	Prime number of the (4k+1)-form
Example 11	Example 13

The magenta column of (4k+1) prime numbers is symetric, the magenta column of (4k-1) prime numbers is complementary.

Wie ja schon bekannt ist, gilt für eine Primzahl $p\$, das für jede zu $p\$ teilerfremde Basis $a\$ $a^{p-1}\equiv 1\mod p$ gilt (Siehe blaue Spalte in der unteren Tabelle).

	1	2	3	4	5	6	7	8	9	10	11	12
1:	1	1	1	1	1	1	1	1	1	1	1	1
2:	2	4	8	3	6	12	11	9	5	10	7	1
3:	3	9	1	3	9	1	3	9	1	3	9	1
4:	4	3	12	9	10	1	4	3	12	9	10	1
5:	5	12	8	1	5	12	8	1	5	12	8	1
6:	6	10	8	9	2	12	7	3	5	4	11	1
7:	7	10	5	9	11	12	6	3	8	4	2	1
8:	8	12	5	1	8	12	5	1	8	12	5	1
9:	9	3	1	9	3	1	9	3	1	9	3	1
10:	10	9	12	3	4	1	10	9	12	3	4	1
11:	11	4	5	3	7	12	2	9	8	10	6	1
12:	12	1	12	1	12	1	12	1	12	1	12	1

Nun ist $p-1\$ aber keine Primzahl, sondern läßt sich in Faktoren zerlegen. So gilt für die unten stehende Tabelle für die Primzahl $p=13\$ das $(p-1)=12=2\cdot 2\cdot 3$ ist, sich also z.B. in $2\cdot 6$ und $3\cdot 4$ zerlegen läßt. Das bedeutet, wenn sich ein Exponent $n\$ in zwei Faktoren $r\$ uns $s\$ zerlegen läßt, das $(a^{r})^{s}=(a^{s})^{r}=a^{r\cdot s}=a^{n}$ gilt.

Beispiele:

• $(5^{3})^{4}=5^{3\cdot 4}=5^{12}$
• $(9^{2})^{6}=9^{2\cdot 6}=9^{12}$

	1	2	3	4	5	6	7	8	9	10	11	12
1:	1	1	1	1	1	1	1	1	1	1	1	1
2:	2	4	8	3	6	12	11	9	5	10	7	1
3:	3	9	1	3	9	1	3	9	1	3	9	1
4:	4	3	12	9	10	1	4	3	12	9	10	1
5:	5	12	8	1	5	12	8	1	5	12	8	1
6:	6	10	8	9	2	12	7	3	5	4	11	1
7:	7	10	5	9	11	12	6	3	8	4	2	1
8:	8	12	5	1	8	12	5	1	8	12	5	1
9:	9	3	1	9	3	1	9	3	1	9	3	1
10:	10	9	12	3	4	1	10	9	12	3	4	1
11:	11	4	5	3	7	12	2	9	8	10	6	1
12:	12	1	12	1	12	1	12	1	12	1	12	1

• $(5^{3})^{4}=8^{4}=1\$
• $(9^{2})^{6}=3^{6}=1\$

Pseudoprimes

What differs Prime numbers from all other natural numbers

In the pattern of Prime numbers $p\$, the $(p-1)\$.th and the ${\frac {p-1}{2}}\$.th columns are closed. That means, that every value of the $(p-1)\$.th column is $1\$ and every value of the ${\frac {p-1}{2}}\$.th is $1\$ or $p-1\$.

For every non prime number the $(p-1)\$.th and the ${\frac {p-1}{2}}\$.th columns are not closed, and in some cases the ${\frac {p-1}{2}}\$.th column is not existence, which means, that no value of the ${\frac {p-1}{2}}\$.th column is $1\$ or $p-1\$.

1 2 3 4 5 6 1: 1 1 1 1 1 1 2: 2 4 8 7 5 1 3: 3 0 0 0 0 0 4: 4 7 1 4 7 1 5: 5 7 8 4 2 1 6: 6 0 0 0 0 0 7: 7 4 1 7 4 1 8: 8 1 8 1 8 1	1 2 3 4 1: 1 1 1 1 2: 2 4 8 1 3: 3 9 2 6 4: 4 1 4 1 5: 5 10 5 10 6: 6 6 6 6 7: 7 4 13 1 8: 8 4 2 1 9: 9 6 9 6 10: 10 10 10 10 11: 11 1 11 1 12: 12 9 3 6 13: 13 4 7 1 14: 14 1 14 1
Neun	Fünfzehn

Wie man bei der Neun sehen kann, ist der Mittelbalken noch, wenn auch unterbrochen, vorhanden. Bei der 15 fehlt er vollständig.

Carmichael-Zahlen

Nachdem was bisher geschrieben worden ist, müßte die Neun, und damit alle Quadrate einer Primzahl, eine perfekte Fast-Primzahl sein. Dem ist aber nicht so. Damit eine Nichtprimzahl eine gute Fast-Primzahl sein kann, muß eines zutreffen: $n-1\$ muß durch $\lambda (n)\$ teilbar sein. Nichtprimzahlen mit dieser Eigenschaft nennt man Carmichael-Zahlen.

Was stimmt nun also an der Neun nicht? Die Einser liegen auf der blauen und, mit den Achten, auf der violetten Spalte.

Sie müßten allerdings auf der grünen Spalte liegen, und zusammen mit Achten auf der cyanen Spalte. Da ist aber weder eine Eins, noch eine Acht vorhanden. Einsen auf der grünen Spalte sind typisch für fermatsche Pseudoprimzahlen, und Einsen, bzw. (n-1) auf der cyanen Spalte sind typisch für eulersche Pseudoprimzahlen.

	1	2	3	4	5	6
1:	1	1	1	1	1	1
2:	2	4	8	7	5	1
3:	3	0	0	0	0	0
4:	4	7	1	4	7	1
5:	5	7	8	4	2	1
6:	6	0	0	0	0	0
7:	7	4	1	7	4	1
8:	8	1	8	1	8	1

Die weiter oben abgebildete 15 ist eine fermatsche Pseudoprimzahl zu den Basen 4 und 11.

Folgerichtig muß man die Struktur für eine typische Primzahl ergänzen:

	1	2	3	4	5	6
1:	1	1	1	1	1	1
X:	X	X	1	X	X	1
X:	X	X	A	X	X	1
X:	X	X	1	X	X	1
X:	X	X	A	X	X	1
A:	A	1	A	1	A	1

pure eulersche Pseudoprimzahl

Mit der puren eulerschen Pseudoprimzahl ist eine fermatsche Pseudoprimzahl gemeint, bei der jede Basis, zu der die Zahl eine fermatsche Pseuodoprimzahl ist, auch gilt, das die Zahl zu der gleichen Basis auch eine eulersche Pseudoprimzahl ist.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2: 2 4 8 16 7 14 3 6 12 24 23 21 17 9 18 11 22 19 13 1 3: 3 9 2 6 18 4 12 11 8 24 22 16 23 19 7 21 13 14 17 1 4: 4 16 14 6 24 21 9 11 19 1 4 16 14 6 24 21 9 11 19 1 5: 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6: 6 11 16 21 1 6 11 16 21 1 6 11 16 21 1 6 11 16 21 1 7: 7 24 18 1 7 24 18 1 7 24 18 1 7 24 18 1 7 24 18 1 8: 8 14 12 21 18 19 2 16 3 24 17 11 13 4 7 6 23 9 22 1 9: 9 6 4 11 24 16 19 21 14 1 9 6 4 11 24 16 19 21 14 1 10: 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11: 11 21 6 16 1 11 21 6 16 1 11 21 6 16 1 11 21 6 16 1 12: 12 19 3 11 7 9 8 21 2 24 13 6 22 14 18 16 17 4 23 1 13: 13 19 22 11 18 9 17 21 23 24 12 6 3 14 7 16 8 4 2 1 14: 14 21 19 16 24 11 4 6 9 1 14 21 19 16 24 11 4 6 9 1 15: 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16: 16 6 21 11 1 16 6 21 11 1 16 6 21 11 1 16 6 21 11 1 17: 17 14 13 21 7 19 23 16 22 24 8 11 12 4 18 6 2 9 3 1 18: 18 24 7 1 18 24 7 1 18 24 7 1 18 24 7 1 18 24 7 1 19: 19 11 9 21 24 6 14 16 4 1 19 11 9 21 24 6 14 16 4 1 20: 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 21: 21 16 11 6 1 21 16 11 6 1 21 16 11 6 1 21 16 11 6 1 22: 22 9 23 6 7 4 13 11 17 24 3 16 2 19 18 21 12 14 8 1 23: 23 4 17 16 18 14 22 6 13 24 2 21 8 9 7 11 3 19 12 1 24: 24 1 24 1 24 1 24 1 24 1 24 1 24 1 24 1 24 1 24 1

1 2 3 4 5 6 7 8 9 10 1: 1 1 1 1 1 1 1 1 1 1 2: 2 4 8 16 32 31 29 25 17 1 3: 3 9 27 15 12 3 9 27 15 12 4: 4 16 31 25 1 4 16 31 25 1 5: 5 25 26 31 23 16 14 4 20 1 6: 6 3 18 9 21 27 30 15 24 12 7: 7 16 13 25 10 4 28 31 19 1 8: 8 31 17 4 32 25 2 16 29 1 9: 9 15 3 27 12 9 15 3 27 12 10: 10 1 10 1 10 1 10 1 10 1 11: 11 22 11 22 11 22 11 22 11 22 12: 12 12 12 12 12 12 12 12 12 12 13: 13 4 19 16 10 31 7 25 28 1 14: 14 31 5 4 23 25 20 16 26 1 15: 15 27 9 3 12 15 27 9 3 12 16: 16 25 4 31 1 16 25 4 31 1 17: 17 25 29 31 32 16 8 4 2 1 18: 18 27 24 3 21 15 6 9 30 12 19: 19 31 28 4 10 25 13 16 7 1 20: 20 4 14 16 23 31 26 25 5 1 21: 21 12 21 12 21 12 21 12 21 12 22: 22 22 22 22 22 22 22 22 22 22 23: 23 1 23 1 23 1 23 1 23 1 24: 24 15 30 27 21 9 18 3 6 12 25: 25 31 16 4 1 25 31 16 4 1 26: 26 16 20 25 23 4 5 31 14 1 27: 27 3 15 9 12 27 3 15 9 12 28: 28 25 7 31 10 16 19 4 13 1 29: 29 16 2 25 32 4 17 31 8 1 30: 30 9 6 15 21 3 24 27 18 12 31: 31 4 25 16 1 31 4 25 16 1 32: 32 1 32 1 32 1 32 1 32 1

Es gibt auch fermatsche Pseudoprimzahlen, bei denen die Pseudoprimzahl keine eulersche Pseudoprimzahl ist. Zu diesen fermatschen Pseudoprimzahlen zählen u.a. die 45, 91 und 153.