Znajdz n dodatnie takie ze,
\(\displaystyle{ 2 ^{n-1} | n!}\)
\(\displaystyle{ n! \equiv 0 \mod { 2 ^{n-1}}}\).
Odpowiedz \(\displaystyle{ n = 2^{k}}\). ale dlaczego?
Dziekuje za pomoc. Bimb.
Udowodnij podzielność
-
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Udowodnij podzielność
Lemat
Liczba pierwsza \(\displaystyle{ p}\) występuje w rozkładzie liczby \(\displaystyle{ n!}\) na czynniki pierwsze z wykładnikiem:
\(\displaystyle{ \left[\frac{n}{p} \right] + ft[\frac{n}{p^2} \right] + ft[\frac{n}{p^3} \right] + \dots}\)
(\(\displaystyle{ \left[ x \right]}\) to część całkowita liczby \(\displaystyle{ x}\))
(suma jest skończona, bo od pewnego miejsca zawsze mamy same zera)
Dowód (nietrudny, pozostawiam jako ćwiczenie).
Zadanie właściwe
W myśl lematu szukamy takiego \(\displaystyle{ n}\), żeby
\(\displaystyle{ n-1 ft[\frac{n}{2} \right] + ft[\frac{n}{2^2} \right] + ft[\frac{n}{2^3} \right] + \dots}\)
Niech \(\displaystyle{ n=2^k+a}\) dla \(\displaystyle{ 0 a < 2^k}\). Po wstawieniu tego do powyższej nierówności dostaniemy (po drobnych przekształceniach):
\(\displaystyle{ a ft[\frac{a}{2} \right] + ft[\frac{a}{2^2} \right] + ft[\frac{a}{2^3} \right] + \dots}\)
Jeśli jednak \(\displaystyle{ a 0}\), to to jest (ostro) mniejsze od
\(\displaystyle{ \frac{a}{2} + \frac{a}{2^2} + \dots = a}\)
czyli sprzeczność.
Stąd wniosek, że \(\displaystyle{ a=0}\) i \(\displaystyle{ n=2^k}\), łatwo sprawdzić, że dla takiego \(\displaystyle{ n}\) istotnie żądana nierówność jest spełniona (a nawet jest wtedy równością).
Q.
Liczba pierwsza \(\displaystyle{ p}\) występuje w rozkładzie liczby \(\displaystyle{ n!}\) na czynniki pierwsze z wykładnikiem:
\(\displaystyle{ \left[\frac{n}{p} \right] + ft[\frac{n}{p^2} \right] + ft[\frac{n}{p^3} \right] + \dots}\)
(\(\displaystyle{ \left[ x \right]}\) to część całkowita liczby \(\displaystyle{ x}\))
(suma jest skończona, bo od pewnego miejsca zawsze mamy same zera)
Dowód (nietrudny, pozostawiam jako ćwiczenie).
Zadanie właściwe
W myśl lematu szukamy takiego \(\displaystyle{ n}\), żeby
\(\displaystyle{ n-1 ft[\frac{n}{2} \right] + ft[\frac{n}{2^2} \right] + ft[\frac{n}{2^3} \right] + \dots}\)
Niech \(\displaystyle{ n=2^k+a}\) dla \(\displaystyle{ 0 a < 2^k}\). Po wstawieniu tego do powyższej nierówności dostaniemy (po drobnych przekształceniach):
\(\displaystyle{ a ft[\frac{a}{2} \right] + ft[\frac{a}{2^2} \right] + ft[\frac{a}{2^3} \right] + \dots}\)
Jeśli jednak \(\displaystyle{ a 0}\), to to jest (ostro) mniejsze od
\(\displaystyle{ \frac{a}{2} + \frac{a}{2^2} + \dots = a}\)
czyli sprzeczność.
Stąd wniosek, że \(\displaystyle{ a=0}\) i \(\displaystyle{ n=2^k}\), łatwo sprawdzić, że dla takiego \(\displaystyle{ n}\) istotnie żądana nierówność jest spełniona (a nawet jest wtedy równością).
Q.