Quersumme < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 13:10 So 06.05.2012 | | Autor: | hilbert |
Hallo,
ich soll die Quersumme der Quersumme von 1234^4321 mittels modulo Rechnung berechnen.
Leider weiß ich hier noch gar nicht, wie sich die Quersumme in Verbindung zur Modulo-Rechung verhält.
Wäre sehr dankbar für einen kleinen Anstupser in die richtige Richtung.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:08 Mo 07.05.2012 | | Autor: | felixf |
Moin!
> ich soll die Quersumme der Quersumme von 1234^4321 mittels
> modulo Rechnung berechnen.
Tipp: diese Quersumme ist zweistellig.
Das kann man wie folgt abschaetzen: die Zahl [mm] $1234^{4321}$ [/mm] hat [mm] $\lfloor \log_{10} 1234^{4321} \rfloor [/mm] + 1 = [mm] \lfloor [/mm] 4321 [mm] \cdot \log_{10} [/mm] 1234 [mm] \rfloor [/mm] + 1$ Dezimalstellen. Laut Taschenrechner sind das 13358. Damit ist die Quersumme hoechstens $9 [mm] \cdot [/mm] 13358 = 120222$. Die Quersumme hat also hoechstens 6 Dezimalstellen, und die Hunderttausender-Ziffer ist hoechstens 1, womit die Querusmme hoechstens $5 [mm] \cdot [/mm] 9 + 1 = 46$ sein kann.
> Leider weiß ich hier noch gar nicht, wie sich die
> Quersumme in Verbindung zur Modulo-Rechung verhält.
Da $10 [mm] \equiv [/mm] 1 [mm] \pmod{9}$ [/mm] gilt ist eine Zahl kongruent zu ihrer Quersumme modulo 9. Dieses Argument kannst du zweimal anwenden und somit die gesuchte Zahl modulo 9 bestimmen. Mit dem chinesischen Restsatz gibt es nun hoechtens 6 Moeglichkeiten. Diese kannst du explizit hinschreiben.
So, und jetzt gerade hat sich eine Idee die ich hatte verabschiedet. Ich werde nachher nochmal drueber weiter nachdenken...
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:53 Di 08.05.2012 | | Autor: | reverend |
Hallo,
> Tipp: diese Quersumme ist zweistellig.
>
> Das kann man wie folgt abschaetzen: die Zahl [mm]1234^{4321}[/mm]
> hat [mm]\lfloor \log_{10} 1234^{4321} \rfloor + 1 = \lfloor 4321 \cdot \log_{10} 1234 \rfloor + 1[/mm]
> Dezimalstellen. Laut Taschenrechner sind das 13358. Damit
> ist die Quersumme hoechstens [mm]9 \cdot 13358 = 120222[/mm]. Die
> Quersumme hat also hoechstens 6 Dezimalstellen, und die
> Hunderttausender-Ziffer ist hoechstens 1, womit die
> Querusmme hoechstens [mm]5 \cdot 9 + 1 = 46[/mm] sein kann.
Das lässt sich noch ganz wenig niedriger ansetzen, da ja die QS 199999 nicht in Frage kommt. Für n<120223 ist die höchste erreichbare Quersumme QS(99999)=45. Und da wir leicht [mm] \mod{10} [/mm] ermitteln können, dass die betrachtete Zahl [mm] 1234^{4321} [/mm] die Endziffer 4 hat, reduziert sich die maximale Quersumme sogar auf QS(99994)=40.
> > Leider weiß ich hier noch gar nicht, wie sich die
> > Quersumme in Verbindung zur Modulo-Rechung verhält.
>
> Da [mm]10 \equiv 1 \pmod{9}[/mm] gilt ist eine Zahl kongruent zu
> ihrer Quersumme modulo 9. Dieses Argument kannst du zweimal
> anwenden und somit die gesuchte Zahl modulo 9 bestimmen.
> Mit dem chinesischen Restsatz gibt es nun hoechtens 6
> Moeglichkeiten. Diese kannst du explizit hinschreiben.
Jetzt sind es "nur" noch 5 Möglichkeiten.
Noch eine lässt sich ausschließen, nämlich die 1. Das erfordert aber einigen Aufwand.
Aus Schreibfaulheit lege ich [mm] z=1234^{4321} [/mm] fest.
Damit QS(QS(z))=1 ist, muss [mm] QS(z)=10^k [/mm] sein, wobei [mm] 1\le k\le{6} [/mm] gilt, siehe die Abschätzung von Felix oben.
Nun ergibt sich aber ein Widerspruch aus folgendem.
Mit Euler-Fermat wissen wir außer [mm] z\equiv 1\mod{9} [/mm] auch noch [mm] z\equiv 2\mod{11}.
[/mm]
Als "Elfer-Test" gibt es ja die sog. alternierende Quersumme.
Dazu legen wir erst einmal [mm] S_u [/mm] als Summe aller Ziffern von z auf ungeraden Stellen (Zählung hinten angefangen) und [mm] S_g [/mm] als Summe aller Ziffern von z auf geraden Stellen fest.
Es gilt nun [mm] S_u-S_g\equiv z\mod{11}
[/mm]
Also muss gelten:
(1) [mm] S_u+S_g\equiv 1\mod{9}
[/mm]
(2) [mm] S_u-S_g\equiv 2\mod{11} [/mm] bzw. [mm] S_u-S_g=11n+2
[/mm]
Sei nun [mm] S_u+S_g=10^k, [/mm] also [mm] S_g=10^k-S_u
[/mm]
Dann folgt aus (2) [mm] 2S_u=11n+2-10^k
[/mm]
und damit [mm] n=\bruch{2S_u+10^k-2}{11}
[/mm]
Für ungerade k folgt [mm] S_u\equiv 7\mod{11}, [/mm] damit aus (2) [mm] S_g\equiv 5\mod{11} [/mm] und aus (1) [mm] S_u+S_g\equiv 1\not\equiv 10^k\mod{11}
[/mm]
Für gerade k folgt [mm] S_u\equiv 6\mod{11} [/mm] und [mm] S_g\equiv 4\mod{11} [/mm] und somit [mm] S_u+S_g\equiv -1\not\equiv 10^k\mod{11}
[/mm]
Es kann also kein k geben, so dass [mm] S_u+S_g=10^k [/mm] ist.
Damit ist also auch QS(QS(z))=1 ausgeschieden.
Bleiben noch die Möglichkeiten 10,19,28,37. Davon sind die beiden mittleren zwar am wahrscheinlichsten, aber das sagt ja leider nichts über den realen Wert aus.
Ich sehe hier nicht, wie man per Modulrechnung wirklich noch weiter kommt.
Wenns eine genauere Lösung gibt, wäre ich am Lösungsweg interessiert.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:56 Di 08.05.2012 | | Autor: | felixf |
Moin rev!
> Bleiben noch die Möglichkeiten 10,19,28,37. Davon sind die
> beiden mittleren zwar am wahrscheinlichsten, aber das sagt
> ja leider nichts über den realen Wert aus.
Das Ergebnis ist uebrigens 19, laut Maple.
Ich hatte die Tage (als ich die erste Antwort schrieb) noch etwas im Internet gesucht und zu einer aehnlichen Aufgabe (Quersumme der Quersumme von [mm] $4444^{4444}$) [/mm] eine "Loesung" gefunden, die aber falsch war (das Ergebnis war einstellig, laut Maple ist es allerdings zweistellig). Die dortige Argumentation passte auch eher zur Quersumme der Quersumme der Quersumme. (Die ist hier 10.)
> Ich sehe hier nicht, wie man per Modulrechnung wirklich
> noch weiter kommt.
>
> Wenns eine genauere Lösung gibt, wäre ich am Lösungsweg
> interessiert.
Same here...
Wenn ich die Tage nochmal Zeit habe werd ich weiter drueber nachdenken... Ist auf jeden Falle eine spannende Frage.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:20 Di 08.05.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
