Primfaktoren bestimmen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Gib möglichst viele Primfaktoren der Zahl $N = [mm] 11^{111} [/mm] + 1111$ an (jeweils mit Begründung)! |
Also ich habe $2$ als Faktor, da die Zahl gerade ist. Und $11$, da [mm] $11^{111}$ [/mm] und $1111$ jeweils durch $11$ teilbar sind. Mehr sehe ich aber nicht (für jeden Faktor bekommt man hier einen Punkt).
# Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:08 Mi 01.04.2009 | | Autor: | statler |
Hi ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
> Gib möglichst viele Primfaktoren der Zahl [mm]N = 11^{111} + 1111[/mm]
> an (jeweils mit Begründung)!
> Also ich habe [mm]2[/mm] als Faktor, da die Zahl gerade ist. Und
> [mm]11[/mm], da [mm]11^{111}[/mm] und [mm]1111[/mm] jeweils durch [mm]11[/mm] teilbar sind.
> Mehr sehe ich aber nicht (für jeden Faktor bekommt man hier
> einen Punkt).
Rechne mal modulo 3.
Gruß
Dieter
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:38 Mi 01.04.2009 | | Autor: | isi1 |
Das leuchtet mir nicht ein, Dieter,
könntest Du das bitte erläutern, denn m.E ist die Quersumme nicht durch 3 teilbar.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:46 Mi 01.04.2009 | | Autor: | statler |
Mahlzeit!
> Das leuchtet mir nicht ein, Dieter,
>
>
> könntest Du das bitte erläutern, denn m.E ist die Quersumme
> nicht durch 3 teilbar.
Gerne doch. Es ist 11 [mm] \equiv [/mm] -1, also auch [mm] 11^{111} \equiv [/mm] -1. Und eben wegen der Quersumme ist 1111 [mm] \equiv [/mm] 1. Also ist die Summe aus beiden [mm] \equiv [/mm] 0 mod 3, d. h. durch 3 teilbar.
Gruß aus HH-Harburg
Dieter
>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:02 Mi 01.04.2009 | | Autor: | isi1 |
Vielen Dank, Dieter, ich hatte vergessen, dass die Quersumme von Produkten gleich dem Produkt der Quersummen ist.
Die alte Regel: Ist die Quersumme des Ergebnisses gleich dem Produkt der Quersummen der Faktoren, so ist anzunehmen, dass man richtig gerechnet hat.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:27 Mi 01.04.2009 | | Autor: | isi1 |
37 hätte ich noch als Faktor anzubieten (gerechnet).
Also hätten wir jetzt die Faktoren: 2, 3, 11, 37
|
|
|
| |
|
> 37 hätte ich noch als Faktor anzubieten (gerechnet).
>
> Also hätten wir jetzt die Faktoren: 2, 3, 11, 37
Mathematica liefert noch drei weitere Primfaktoren:
zwei dreistellige, einen vierstelligen.
Wie man diese allerdings ohne mächtige Computer-
unterstützung auffinden sollte, ist mir nicht klar.
Deshalb gebe ich sie auch nicht explizit an.
Mathematica liefert ausserdem noch die Information,
dass dies dann noch nicht alle Primfaktoren sind,
denn der verbleibende Faktor
21963286212052936584987238799279057
22452376635303860490196328571224210
9408114230318959787651821564062223
ist nicht prim, aber doch zu gross, als dass ihn
Mathematica wirklich zerlegen könnte.
LG Al-Chw.
|
|
|
| |
|
Vielen Dank für die vielen Antworten. Ich habe mittlerweile einen Tipp bekommen, wie man 111 = 3*37 als Teiler nachweist:
[mm] $11^{111} [/mm] + 1111 = [mm] (11^3)^{37} [/mm] + 1111 = (111*12 - [mm] 1)^{37} [/mm] + 10*111 + 1 [mm] \equiv (-1)^{37} [/mm] + 1 [mm] \equiv [/mm] 0 [mm] \mod [/mm] 111$
Also habe ich 2, 3, 11, 37. Was ist mit den anderen Teilern? Kann man für die auch Beweise finden?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:47 Mi 01.04.2009 | | Autor: | reverend |
Hallo Klosterfrau,
da hatte ich einen Rechenfehler (genauer: Programmfehler im Langzahlenrechner) in der ersten - mithin bedeutungslosen - ersten Version dieses Beitrags.
Die drei Primfaktoren, die Al meint, habe ich jetzt auch ohne Mathematica. Zur Kontrolle: alle drei rückwärts gelesen und dann addiert ergeben 8254. Ich sehe auch keinen Weg, wie man sie anders findet als über die Primfaktorenzerlegung der gegebenen Zahl. Es ist schwer genug, sie zu überprüfen, wenn sie einmal gefunden sind.
Dafür sind die bisher von Dir gefundenen Faktoren sozusagen in einem Rutsch zu finden, wenn man folgende Zerlegungen betrachtet:
[mm] 11^3+1=2^2*3^2*37 [/mm] und 1111-1=2*3*5*37
Dagegen genügt es nicht, [mm] 11^3+1111=2442=2*3*11*37 [/mm] zu betrachten. Siehst Du, warum nicht?
Mehr wenig später. 
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 02:27 Do 02.04.2009 | | Autor: | reverend |
Hallo Al,
hallo Klosterfrau,
da hatte ich einen veritablen Fehler in meinem "mal eben" angelegten Langzahlenrechner. Den habe ich zwar schon kurz nach meinem ersten Beitrag hier entdeckt, aber seitdem läuft mein Rechner mit einem anderen Problem, siehe unten.
Mittlerweile habe ich die Faktoren, die Al hat, auch - ohne CAS-Programm. Zur Probe: man lese die drei "neuen" (drei- und vierstelligen) von hinten, addiere sie, und bekommt dann eine Summe, die vom nächstgelegenen Tausender 254 entfernt ist. Sie sind nicht schwer zu finden, aber den Nachweis zu führen, dass sie tatsächlich Teiler der gegebenen Zahl sind, ist nicht einfach.
Al's große Zahl (104 Dezimalstellen) kann ich nun bestätigen. Sie ist zwar definitiv nicht prim, aber dennoch nicht so leicht zu faktorisieren. Bisher kann ich nur sicher sagen, dass kein Primfaktor weniger als 25 Dezimalstellen hat, aber eine Zerlegung ist nicht in Sicht. Falls die Suche bis zu zwei ähnlich großen Faktoren fortschreitet, wird mein PC noch einige Jahre (sic!) brauchen, um diese anzugeben.
Dafür lassen sich die bisher gefundenen "kleinen" Faktoren auch leichter herleiten. Dafür ist es gut zu wissen, dass 1111-1=2*3*5*37 und [mm] 11^3+1=2^2*3^2*37.
[/mm]
Dagegen reicht es nicht, [mm] 11^3+1111=2442=2*3*11*37 [/mm] zu betrachten. Siehst Du, warum nicht?
Mal sehen, wie weit man mit der Rechenleistung zuhause kommt...
Wenn ich richtig abschätze, wäre (unter Zuhilfenahme meines Rechners erst Freitag Vormittag die Behauptung zu treffen, dass auch 30-stellige Faktoren nicht genügen. Naja.
Herzliche Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 07:32 Do 02.04.2009 | | Autor: | felixf |
Hallo zusammen
> > 37 hätte ich noch als Faktor anzubieten (gerechnet).
> >
> > Also hätten wir jetzt die Faktoren: 2, 3, 11, 37
>
>
> Mathematica liefert noch drei weitere Primfaktoren:
> zwei dreistellige, einen vierstelligen.
> Wie man diese allerdings ohne mächtige Computer-
> unterstützung auffinden sollte, ist mir nicht klar.
> Deshalb gebe ich sie auch nicht explizit an.
> Mathematica liefert ausserdem noch die Information,
> dass dies dann noch nicht alle Primfaktoren sind,
> denn der verbleibende Faktor
>
> 21963286212052936584987238799279057
> 22452376635303860490196328571224210
> 9408114230318959787651821564062223
>
> ist nicht prim, aber doch zu gross, als dass ihn
> Mathematica wirklich zerlegen könnte.
Ich hab mal MAGMA ein wenig rechnen lassen (oder auch ein wenig mehr), und damit die vollstaendige Faktorisierung von [mm] $11^{111} [/mm] + 1111$ bestimmt:
$2 * 3 * 11 * 37 * 181 * 431 * 9397 * 68795343387915425133234412996132133 * 319255419486880599005733002894499728886661935620306428304637893981731$
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:09 Do 02.04.2009 | | Autor: | felixf |
Hallo zusammen,
> Da läuft gerade noch dieses
> ![[]](/images/popup.gif) Programm.
die elliptische-Kurven-Methode hat in diesem Fall den Faktor gefunden; das allgemeine Zahlkoerpersieb war auch noch am laufen, war aber langsamer. (Was schneller ist ist auch immer etwas Glueckssache, da die Algorithmen randomisiert sind, allerdings haengt die Laufzeit der elliptische-Kurven-Methode hauptsaechlich vom kleinsten Primfaktor ab und nicht von der Zahl selber, weshalb es hier nicht so sehr ueberrascht dass sie zuerst einen Faktor gefunden hat.)
LG Felix
|
|
|
|
