Differenzen von Quadraten < Analysis < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 11:08 Mo 20.09.2004 | | Autor: | blubli89 |
Das Produkt zweier Zahlen
Differenzen von Quadraten als Primzahltest
Das Produkt zweier Zahlen entspricht der Hälfte der Summe quadriert , abzüglich der Hälfte der Differenz quadriert . Also :
a*b =[ [mm] (a+b)/2]^2 [/mm] [mm] [(a-b)/2]^2
[/mm]
Beweis:
a*b = [(a+b)/2]*[(a+b)/2] [(a-b)/2]*[(a-b)/2]
a*b = [mm] [(a^2+2ab+b^2)/4 [/mm] [mm] (a^2-2ab+b^2)/4]
[/mm]
Der letzte Teil der Gleichung lässt sich kürzen :
[ [mm] (a^2+2ab+b^2)/4 [/mm] [mm] (a^2 [/mm] 2ab + [mm] b^2)/4]
[/mm]
=[ [mm] (a^2+2ab+b^2)-(a^2-2ab+b^2)] [/mm] / 4
= [mm] (a^2+2ab+b^2-a^2+2ab-b^2)/4
[/mm]
= (4ab)/4
=a*b
Was zu beweisen war.
Jedes Produkt lässt sich also als Differenz zweier Quadrate ausdrücken.
.......................................................................................................................
Jetzt ist es möglich , zusammengesetzte Zahlen als Differenz von Quadraten zu identifizieren
Uns interessieren im Augenblick nur die Produkte quasiprimer teilbarer Zahlen , also z.b. teilbare 6n+-1 , die meist sehr viel schwerer als teilbar zu identifizieren sind als Produkte von 2 , 3 , und 5.
Beispiel teilbare 6n+ - 1:
Alle Produkte der 6n+-1 untereinander , sind ebenfalls Vielfache der 6 , vermindert oder vermehrt um 1.
Das ist eigentlich klar , ein Beweis lässt sich hier sparen.
Allgemein gilt : 1. (6p+1)*(6m+1) = 36pm+6p+6m+1 => entspricht 6n+1
2. (6p 1)*(6m 1) = 36pm 6p 6m+1 => entspricht 6n+1
3. (6p+1)*(6m 1) = 36pm 6p+6m 1 => entspricht 6n 1
4. (6p 1)*6m+1) = 36pm+6p 6m 1 => entspricht 6n 1
Um festzustellen welche Form , zusammengesetzte 6n+-1 , als Differenz von Quadraten besitzen ; muss man sie nur in die zu Anfang gezeigte Gleichung einsetzen.
a*b = [(a + [mm] b)/2]^2 [/mm] [(a [mm] b)/2]^2
[/mm]
=>
1. (6p + 1)*(6m + 1) = [(6p + 1)+ (6m + [mm] 1)/2]^2 [/mm] [(6p + 1) (6m + [mm] 1)/2]^2 [/mm]
= {[6(p + m) [mm] +2]/2}^2 [/mm] [6(p [mm] m)/2]^2 [/mm]
= [3(p + m) [mm] +1]^2 [/mm] [3(p [mm] m)]^2 [/mm]
...................................................................
2. (6p 1)*(6m 1) = [(6p 1)+ (6m [mm] 1)/2]^2 [/mm] [(6p 1) (6m [mm] 1)/2]^2 [/mm]
= {[6(p + m) [mm] 2]/2}^2 [/mm] [6(p [mm] m)/2]^2 [/mm]
= [3(p + m) [mm] 1]^2 [/mm] [3(p [mm] m)]^2 [/mm]
.....................................................................
3. (6p + 1)*(6m 1) = [(6p + 1)+ (6m [mm] 1)/2]^2 [/mm] [(6p + 1) (6m [mm] 1)/2]^2
[/mm]
= [6(p + [mm] m)/2]^2 [/mm] {[6(p m) [mm] +2]/2}^2
[/mm]
=[3(p + [mm] m)]^2 [/mm] [3(p m) [mm] +1]^2
[/mm]
........................................................................
4. (6p 1)*(6m+1) = [(6p 1)+( [mm] 6m+1)/2]^2 [/mm] [(6p 1) [mm] (6m+1)/2]^2
[/mm]
= [6(p + [mm] m)/2]^2 [/mm] {[6(p m) [mm] 2]/2}^2
[/mm]
=[3(p + [mm] m)]^2 [/mm] [3(p m) [mm] 1]^2
[/mm]
..................................................................................
Verallgemeinert kann man sagen :
Alle teilbaren 6n+1 können als : [mm] (3p+-1)^2 [/mm] [mm] (3m)^2 [/mm] betrachtet werden
Alle teilbaren 6n 1 können als : [mm] (3m)^2 [/mm] [mm] (3p+-1)^2 [/mm] betrachtet werden
Dasselbe kann man natürlich auch mit anderen Primzahlausdrücken machen , z.b. 4n+-1.
Wird der Rest grösser als 1 (wie bei 10n+-r , 14n+-r , 30n+-r) , wird leider alles etwas komplizierter.
Man kann die aus den verschiedenen Ausdrücken gewonnenen Formeln dann in der Art eines Siebes (des Eratosthenes) benutzen und damit alle teilbaren Zahlen der Form4n+-1 , 6n+-1 usw.... durch einsetzen generieren .
Man kann es auch als Primzahltest einsetzen . Es ist eine brauchbare Alternative zum Probeteilen.
Im Gegensatz zum Probeteilen , das bei weit auseinander liegenden Primfaktoren schnell ist , funktioniert es hier genau entgegengesetzt , Primfaktoren nahe der Wurzel werden zuerst gefunden.
...Faktorisierung von zusammengesetzten 6n+-1 mit der Differenz von Quadraten...
6n 1:
Alle zusammengesetzten 6n 1 können als : 6n 1 = [mm] (3m)^2 [/mm] [mm] (3p+-1)^2 [/mm] , betrachtet werden.
Stellt man um auf : [mm] (3m)^2 [/mm] 6n 1= [mm] (3p+-1)^2 [/mm] erkennt man , das für jede 6n 1 eine [mm] (3m)^2 [/mm] existiert , mit der sie eine Differenz bildet die ebenfalls ein Quadrat ist .
Um eine teilbare 6n 1 zu faktorisieren muss man nur solange die Differenz mit [mm] (3m)^2 [/mm] oberhalb der Wurzel bilden , bis die Differenz ebenfalls ein Quadrat ist .
Beispiele : 35 = 6n 1 , sqrt = 5,......
[mm] (3m)^2 [/mm] > [mm] 5^2 [/mm] = [mm] 6^2 [/mm] , [mm] 9^2 [/mm] , [mm] 12^2 [/mm] , usw...
[mm] 6^2 [/mm] 35 = [mm] 1^2 [/mm] => 6+-1 = 5;7 => 35 = 5*7
..............................................................................................
: 263.147 = 6n 1 , sqrt = 512,......
[mm] (3m)^2 [/mm] > [mm] 512^2 [/mm] = [mm] 513^2 [/mm] , [mm] 516^2 [/mm] , [mm] 519^2 [/mm] , usw...
[mm] 513^2 [/mm] 263.147 = 22
[mm] 516^2 [/mm] 263.147 = 3109
[mm] 519^2 [/mm] 263.147 = 6214
[mm] 522^2 [/mm] 263.147 = 9337
[mm] 525^2 [/mm] 263.147 = 12478
[mm] 528^2 [/mm] 263.147 = 15637
[mm] 531^2 [/mm] 263.147 = 18814
[mm] 534^2 [/mm] 263.147 = 22009
[mm] 537^2 [/mm] 263.147 = 25222
........................................
.......................................
[mm] 546^2 [/mm] 263147 = 34969 = [mm] 187^2 [/mm] => 546 +- 187 = 359;733 => 263147 = 359*733
6n+1: Alle zusammengesetzten 6n+1 können als : [mm] (3p+-1)^2 [/mm] [mm] (3m)^2 [/mm] betrachtet werden .
Stellt man um auf : [mm] (3p+-1)^2 [/mm] 6n+1 = [mm] (3m)^2 [/mm] erkennt man , das für jede 6n+1 eine [mm] (3p+-1)^2 [/mm] existiert , mit der sie eine Differenz bildet , die ebenfalls ein Quadrat ist .
Um eine teilbare 6n+1 zu faktorisieren , muss man nur solange die Differenz mit [mm] (3p+-1)^2 [/mm] oberhalb der Wurzel bilden , bis die Differenz ebenfalls ein Quadrat ist .
Beispiele : 55 = 6n+1 , sqrt = 7,....
[mm] (3p+-1)^2 [/mm] > [mm] 7^2 [/mm] = ???
Tja , was wären die [mm] (3p+-1)^2 [/mm] > [mm] 7^2 [/mm] ? Vielleicht alle Zahlen die nicht [mm] (3m)^2 [/mm] sind , also [mm] 8^2 [/mm] , [mm] 10^2 [/mm] , [mm] 11^2 [/mm] , [mm] 13^2 [/mm] , usw....soviel Aufwand muss man aber nicht betreiben.
Da alle [mm] (3m)^2 [/mm] immer die Quersumme 9 besitzen , besitzt eine 6n+1 , die = [mm] (3p+-1)^2 [/mm] [mm] (3m)^2 [/mm] entspricht , immer die gleiche Quersumme wie : [mm] (3p+-1)^2 [/mm] ; bildet man die Differenz mit einer Quersumme=9 Zahl , besitzen verminderte Zahl und Differenz die gleiche Quersumme !
Man muss also nur [mm] (3p+-1)^2 [/mm] testen die die gleiche Quersumme besitzen wie unsere 55 .
Da [mm] 8^2 [/mm] = 64 = Quersumme 1, wäre [mm] 8^2 [/mm] die erste zu testende Zahl .
[mm] (3p+-1)^2 [/mm] > [mm] 7^2 [/mm] = [mm] 8^2 [/mm] , [mm] 10^2 [/mm] , [mm] 17^2 [/mm] , [mm] 19^2 [/mm] .............usw.
[mm] 8^2 [/mm] 55 = 9 = [mm] 3^2 [/mm] => 8+-3 = 5;11 => 55 = 5*11
..............................................................................................................................
: 2.285.503 = 6n+1 , sqrt = 1511,..... Quersumme = 7
[mm] (3p+-1)^2 [/mm] > [mm] 1511^2 [/mm] mit Q = 7 : [mm] 1516^2 [/mm] , [mm] 1517^2 [/mm] , [mm] 1525^2 [/mm] , [mm] 1526^2 [/mm] , ............usw.
[mm] 1516^2 [/mm] 2.285.503 = 12.753
[mm] 1517^2 [/mm] 2.285.503 = 15.786
.................................................
.................................................
.................................................
.................................................
[mm] 1552^2 [/mm] 2.285.503 = 123.201 = [mm] 351^2 [/mm] => 1552+-351 = 1201;1903 => 2.285.503 = 1201*1903
Meiner Meinung nach stellt das Verfahren eine brauchbare Alternative zum Probeteilen dar,
wenn der Abstand der Primfaktoren nicht zu gross ist.
Ein Programm das mit beiden Verfahren arbeitet wäre optimal .
Durch Optimierung , kann man die Menge der zu testenden Quadrate nochmal um 83,3 % senken .
Vielleicht hätte jemand von euch Lust ein Programm zu schreiben , falls ja meldet euch doch bei mir , oder direkt hier im Forum , das würde mich wirklich freuen .
Ich bin des Programmierens leider nicht mächtig .
Liebe Grüsse , Gerold
P.S.: Bitte entschuldigt den etwas merkwürdigen SATZ , aber ich musste alles von Diskette abkopieren.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:46 Do 23.09.2004 | | Autor: | Stefan |
Lieber Gerold!
Hast du denn noch selber Fragen dazu oder wolltest du einfach dazu auffordern die Sache zu programmieren?
Liebe Grüße
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:10 Fr 24.09.2004 | | Autor: | blubli89 |
Hallo Stefan ,
entschuldigung für die verspätete Rückmeldung , aber die Seite liess sich zeitweilig nicht öffnen.
Ja ich wollte eigentlich nur dazu auffordern etwas zu programmieren.
Es müsste ein Programm sein das sowohl probeteilt , als auch mit Quadratdifferenzen arbeitet.
Man muss nur beide Vorgänge miteinander koppeln , so das beide Unterprogramme "wissen" bis zu welcher Zahlengrösse das jeweils andere Programm schon fortgeschritten ist.
Meine Hoffnung ist , das dabei etwas herauskommt das eine Zahl schneller
faktorisiert als beim normalen Probeteilen.
Liebe Grüsse , Gerold
|
|
|
|
