Udowodnij podzielność

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
bimber
Użytkownik
Użytkownik
Posty: 7
Rejestracja: 20 mar 2008, o 18:23
Płeć: Mężczyzna
Lokalizacja: kanada
Podziękował: 5 razy

Udowodnij podzielność

Post autor: bimber »

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.
Ostatnio zmieniony 26 lis 2008, o 19:00 przez bimber, łącznie zmieniany 1 raz.
Użytkownik
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ść

Post autor: »

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.
ODPOWIEDZ