Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
[Matx]#669: Anzahl der Nullen
9 views
Skip to first unread message
GJ Woeginger
May 17, 2012, 10:13:00 AM5/17/12
to
Mit wievielen Nullen endet die Dezimaldarstellung
der Zahl n= 4^(5^6) + 6^(5^4) ?
___________________________________________________________
Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/
der Zahl n= 4^(5^6) + 6^(5^4) ?
___________________________________________________________
Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/
Thomas Nordhaus
May 18, 2012, 9:24:22 AM5/18/12
to
Am 17.05.2012 16:13, schrieb GJ Woeginger:
> Mit wievielen Nullen endet die Dezimaldarstellung
> der Zahl n= 4^(5^6) + 6^(5^4) ?
Nicht ganz vollständig:
> Mit wievielen Nullen endet die Dezimaldarstellung
> der Zahl n= 4^(5^6) + 6^(5^4) ?
s
p
o
i
l
e
r
s
p
o
i
l
e
r
n=4^(5^6)+ 6^(5^4) = N*2^(5^4), wobei N = 3^(5^4) + 2^(2*5^6 - 5^4) =
3^(5^4) + 2^(49*5^4) ist. N ist ungerade. n kann also maximal in 2^(5^4)
Nullen enden. Entscheidend ist jetzt, wie oft N durch 5 teilbar ist.
Behauptung: N ist durch 5^5, nicht aber durch 5^6 teilbar.
Daraus folgt, dass n durch 10^5, nicht aber durch 10^6 teilbar ist, d.h.
die Dezimaldarstellung von n endet in 5 Nullen.
Beweis (Behauptung): Es ist phi(5^5) = 5^5 - 5^4 = 4*5^4, wobei phi die
Eulersche phi-Funktion sei. Nach dem Satz von Euler-Fermat gilt dann
2^(49*5^4) =2^(12*(4*5^4)+5^4) = 2^(5^4) mod 5^5. Daher ist
(*) N = 2^(5^4) + 3^(5^4) mod 5^5.
Hilfssatz (Beweis per Induktion und bin. Lehrsatz): Sei p Primzahl und
sei a=b mod p. Dann gilt a^(p^n) = b^(p^n) mod p^(n+1) für alle
positiven ganzen Zahlen n.
Da 2 = -3 mod 5 folgt 2^(5^4) = (-3)^5^(4) = -3^(5^4) mod 5^5, da
(-1)^(5^4)=-1. Also ist 2^(5^4) + 3^(5^4) = 0 mod 5^5. Der erste Teil
der Behauptung ist damit bewiesen.
Daraus folgt dass N mindestens durch 5^5 teilbar ist. D.h n ist
mindestens durch 10^5 teilbar. Der letzten Schritt (d.h. zu zeigen dass
N nicht durch 5^6 und n damit nicht durch 10^6 teilbar ist) fehlt noch.
Laut pari ist aber N/5^5 = 3 mod 5, d.h. N ist nicht durch 5^6 teilbar.
--
Thomas Nordhaus
Thomas Nordhaus
May 23, 2012, 10:26:56 AM5/23/12
to
Etwas vollständiger:
Am 18.05.2012 15:24, schrieb Thomas Nordhaus:
> Am 17.05.2012 16:13, schrieb GJ Woeginger:
>> Mit wievielen Nullen endet die Dezimaldarstellung
>> der Zahl n= 4^(5^6) + 6^(5^4) ?
>
> Nicht ganz vollständig:
>
>
>
>
>
>
>
>
>
>
>
>
> s
> p
> o
> i
> l
> e
> r
>
>
>
>
>
>
>
>
>
> s
> p
> o
> i
> l
> e
> r
>
> n=4^(5^6)+ 6^(5^4) = N*2^(5^4), wobei N = 3^(5^4) + 2^(2*5^6 - 5^4) =
> 3^(5^4) + 2^(49*5^4) ist. N ist ungerade. n kann also maximal in 2^(5^4)
^^^^^
Oops! Das sollte: 5^4 heißen. D.h. N endet maximal in 5^4=625 Nullen.
> Nullen enden. Entscheidend ist jetzt, wie oft N durch 5 teilbar ist.
>
> Behauptung: N ist durch 5^5, nicht aber durch 5^6 teilbar.
>
> Daraus folgt, dass n durch 10^5, nicht aber durch 10^6 teilbar ist, d.h.
> die Dezimaldarstellung von n endet in 5 Nullen.
>
> Beweis (Behauptung): Es ist phi(5^5) = 5^5 - 5^4 = 4*5^4, wobei phi die
> Eulersche phi-Funktion sei. Nach dem Satz von Euler-Fermat gilt dann
> 2^(49*5^4) =2^(12*(4*5^4)+5^4) = 2^(5^4) mod 5^5. Daher ist
>
> (*) N = 2^(5^4) + 3^(5^4) mod 5^5.
>
> Hilfssatz (Beweis per Induktion und bin. Lehrsatz): Sei p Primzahl und
> sei a=b mod p. Dann gilt a^(p^n) = b^(p^n) mod p^(n+1) für alle
> positiven ganzen Zahlen n.
>
> Da 2 = -3 mod 5 folgt 2^(5^4) = (-3)^5^(4) = -3^(5^4) mod 5^5, da
> (-1)^(5^4)=-1. Also ist 2^(5^4) + 3^(5^4) = 0 mod 5^5. Der erste Teil
> der Behauptung ist damit bewiesen.
>
> Daraus folgt dass N mindestens durch 5^5 teilbar ist. D.h n ist
> mindestens durch 10^5 teilbar. Der letzten Schritt (d.h. zu zeigen dass
> N nicht durch 5^6 und n damit nicht durch 10^6 teilbar ist) fehlt noch.
> Laut pari ist aber N/5^5 = 3 mod 5, d.h. N ist nicht durch 5^6 teilbar.
Zu zeigen ist, dass N=3^(5^4)+2^(49*5^4) != 0 mod 5^6. N ist von der
Form N(m) = 3^(5^4)+2^[(4m+1)*5^4] mit m=12=2 mod 5.
N(m) nimmt laut Pari folgende Werte mod 5^6 an:
m | N(m) mod 5^6
------------------
0 | 5^5
1 | 2*5^5
2 | 3*5^5
3 | 4*5^5
4 | 0
usw. modulo 5. Die Behauptung ist also dass N(m) = (m+1)*5^5 mod 5^6 und
daher N(m) = 0 mod 5^6 genau dann wenn m = 4 mod 5. In unserem Fall ist
m=2 mod 5, d.h. N(m) != 0 mod 5^6.
P.S.
Nimmt man N(m)= 2^(5^4)+3^[(4m+1)*5^4] ergibt sich folgendes Schema:
m | N(m) mod 5^6
------------------
0 | 5^5
1 | 4*5^5
2 | 2*5^5
3 | 0
4 | 3*5^5
usw. d.h. N(m) = (3m+1)*5^5 mod 5^6
--
Thomas Nordhaus
Am 18.05.2012 15:24, schrieb Thomas Nordhaus:
> Am 17.05.2012 16:13, schrieb GJ Woeginger:
>> Mit wievielen Nullen endet die Dezimaldarstellung
>> der Zahl n= 4^(5^6) + 6^(5^4) ?
>
> Nicht ganz vollständig:
>
>
>
>
>
>
>
>
>
>
>
>
> s
> p
> o
> i
> l
> e
> r
>
>
>
>
>
>
>
>
>
> s
> p
> o
> i
> l
> e
> r
>
> n=4^(5^6)+ 6^(5^4) = N*2^(5^4), wobei N = 3^(5^4) + 2^(2*5^6 - 5^4) =
> 3^(5^4) + 2^(49*5^4) ist. N ist ungerade. n kann also maximal in 2^(5^4)
Oops! Das sollte: 5^4 heißen. D.h. N endet maximal in 5^4=625 Nullen.
> Nullen enden. Entscheidend ist jetzt, wie oft N durch 5 teilbar ist.
>
> Behauptung: N ist durch 5^5, nicht aber durch 5^6 teilbar.
>
> Daraus folgt, dass n durch 10^5, nicht aber durch 10^6 teilbar ist, d.h.
> die Dezimaldarstellung von n endet in 5 Nullen.
>
> Beweis (Behauptung): Es ist phi(5^5) = 5^5 - 5^4 = 4*5^4, wobei phi die
> Eulersche phi-Funktion sei. Nach dem Satz von Euler-Fermat gilt dann
> 2^(49*5^4) =2^(12*(4*5^4)+5^4) = 2^(5^4) mod 5^5. Daher ist
>
> (*) N = 2^(5^4) + 3^(5^4) mod 5^5.
>
> Hilfssatz (Beweis per Induktion und bin. Lehrsatz): Sei p Primzahl und
> sei a=b mod p. Dann gilt a^(p^n) = b^(p^n) mod p^(n+1) für alle
> positiven ganzen Zahlen n.
>
> Da 2 = -3 mod 5 folgt 2^(5^4) = (-3)^5^(4) = -3^(5^4) mod 5^5, da
> (-1)^(5^4)=-1. Also ist 2^(5^4) + 3^(5^4) = 0 mod 5^5. Der erste Teil
> der Behauptung ist damit bewiesen.
>
> Daraus folgt dass N mindestens durch 5^5 teilbar ist. D.h n ist
> mindestens durch 10^5 teilbar. Der letzten Schritt (d.h. zu zeigen dass
> N nicht durch 5^6 und n damit nicht durch 10^6 teilbar ist) fehlt noch.
> Laut pari ist aber N/5^5 = 3 mod 5, d.h. N ist nicht durch 5^6 teilbar.
Form N(m) = 3^(5^4)+2^[(4m+1)*5^4] mit m=12=2 mod 5.
N(m) nimmt laut Pari folgende Werte mod 5^6 an:
m | N(m) mod 5^6
------------------
0 | 5^5
1 | 2*5^5
2 | 3*5^5
3 | 4*5^5
4 | 0
usw. modulo 5. Die Behauptung ist also dass N(m) = (m+1)*5^5 mod 5^6 und
daher N(m) = 0 mod 5^6 genau dann wenn m = 4 mod 5. In unserem Fall ist
m=2 mod 5, d.h. N(m) != 0 mod 5^6.
P.S.
Nimmt man N(m)= 2^(5^4)+3^[(4m+1)*5^4] ergibt sich folgendes Schema:
m | N(m) mod 5^6
------------------
0 | 5^5
1 | 4*5^5
2 | 2*5^5
3 | 0
4 | 3*5^5
usw. d.h. N(m) = (3m+1)*5^5 mod 5^6
--
Thomas Nordhaus
0 new messages