Skocz do zawartości

  •  
  • Mini kompendium
  • MimeTeX
  • Regulamin





- - - - -

Jakich dzielników więcej?

Napisane przez Ereinion, 22 February 2010 · 2187 wyświetleń

Teoria Liczb
Jest to już dziesiąty - jubileuszowy wpis na tym blogu, więc postaram się w końcu napisać coś ciekawego.

Tematem tego wpisu będzie następujące twierdzenie:

"Każda liczba naturalna ma co najmniej tyle dzielników postaci 4k+1 co dzielników postaci 4k+3." (*)

Twierdzenie to jest bardzo ogólne (dotyczy w końcu każdej liczby naturalnej, bez dodatkowych założeń) i może się wydawać, że jego dowód będzie trudny. Przekonamy się, że tak nie jest.

Zacznijmy od kilku prostych spostrzeżeń:

1. Iloczyn dwóch liczb postaci 4k+1 jest liczbą postaci 4k+1 (umawiamy się, że tu i dalej k nie oznacza konkretnej liczby naturalnej, ale dowolną, być może za każdym razem inną liczbę naturalną, mam nadzieję, że nie doprowadzi to do nieporozumień).
Dowód:


2. Iloczyn dwóch liczb postaci 4k+3 jest liczbą postaci 4k+1.
Dowód:


3. Iloczyn liczby postaci 4k+1 i liczby postaci 4k+3 jest liczbą postaci 4k+3.
Dowód:


4. Każda liczba parzysta jest postaci 4k albo 4k+2.
Dowód:


5. Tezę z twierdzenia (*) wystarczy udowodnić dla liczb nieparzystych.
Dowód:


Teraz możemy już przejść do dowodu twierdzenia (*).

Na mocy 5. każdą liczbę interesującą nas w tym dowodzie możemy zapisać jako m=p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot ... \cdot p_n^{\alpha_n} , gdzie p_i to różne nieparzyste liczby pierwsze, a \alpha_i to dodatnie liczby całkowite.

Dowód będzie indukcyjny ze względu na n.

Przypadek n=0 czyli m=1 jest trywialny, sprawdźmy więc n=1.

Mamy m=p^\alpha. Wszystkie dzielniki m to 1,\ p ,\ p^2,\ p^3,\ ... ,\ p^\alpha.

Zauważmy, że liczby 1,\ p^2,\ p^4,\ p^6,\ ... są zawsze postaci 4k+1, co wynika ze spostrzeżeń 1. oraz 2.

Tych liczb jest \[\frac{\alpha}{2}\] +1 ([x] to część całkowita liczby x).

Wobec tego dzielników m postaci 4k+3 jest co najwyżej \alpha + 1 - \(\[\frac{\alpha}{2}\] +1\)=\alpha-\[\frac{\alpha}{2}\].

Wykażemy teraz, że \[\frac{\alpha}{2}\] +1 \ \ge \ \alpha-\[\frac{\alpha}{2}\]. (**)

Dla \alpha parzystego mamy \[\frac{\alpha}{2}\]=\frac{\alpha}{2} i jak łatwo sprawdzić nierówność (**) zachodzi, natomiast dla \alpha nieparzystego mamy \[\frac{\alpha}{2}\]=\frac{\alpha-1}{2} i (**) staje się równością.

Załóżmy teraz, że twierdzenie (*) jest prawdziwe dla pewnego n. Pokażemy, że jest prawdziwe również, dla n+1.

Niech z=p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot ... \cdot p_n^{\alpha_n} oraz z'=z \cdot p_{n+1}^{\alpha_{n+1}} oraz niech x oznacza liczbę dzielników z mających postać 4k+1, a y liczbę dzielników z mających postać 4k+3.

Z założenia indukcyjnego x \ \ge \ y.

Wszystkie dzielniki z' to dzielniki z mnożone kolejno przez 1,\ p_{n+1},\ p_{n+1}^2,\ ...,\ p_{n+1}^{\alpha_{n+1}}.

Jeżeli p_{n+1} jest postaci 4k+1 to wszystkie z wypisanych liczb też, wobec czego z' ma (\alpha_{n+1}+1) \cdot x dzielników postaci 4k+1 oraz (\alpha_{n+1}+1) \cdot y dzielników postaci 4k+3.

Oczywiście (\alpha_{n+1}+1) \cdot x \ \ge \ (\alpha_{n+1}+1) \cdot y a to kończy dowód.

Jeśli natomiast p_{n+1} jest postaci 4k+3 to pamiętając o spostrzeżeniach 1., 2. i 3. oraz przypominając sobie rozumowanie z dowodu dla n=1 stwierdzamy, że liczba dzielników z' postaci 4k+1 to  \( \[\frac{\alpha_{n+1}}{2}\] +1\) \cdot x + \(\alpha_{n+1}-\[\frac{\alpha_{n+1}}{2}\]\) \cdot y

a dzielników postaci 4k+3 mamy \(\alpha_{n+1}-\[\frac{\alpha_{n+1}}{2}\]\) \cdot x + \( \[\frac{\alpha_{n+1}}{2}\] +1\) \cdot y.

Wystarczy zatem wykazać nierówność

\( \[\frac{\alpha_{n+1}}{2}\] +1\) \cdot x + \(\alpha_{n+1}-\[\frac{\alpha_{n+1}}{2}\]\) \cdot y \ \ge \ \(\alpha_{n+1}-\[\frac{\alpha_{n+1}}{2}\]\) \cdot x + \( \[\frac{\alpha_{n+1}}{2}\] +1\) \cdot y<br />

przekształcając równoważnie:

2 \cdot \[\frac{\alpha_{n+1}}{2}\] \cdot x - 2 \cdot \[\frac{\alpha_{n+1}}{2}\] \cdot y +x -y -\alpha_{n+1} x+\alpha_{n+1} y \ \ge \ 0

co po rozłożeniu na czynniki daje

(x-y)\(2 \cdot \[\frac{\alpha_{n+1}}{2}\] + 1 - \alpha\) \ \ge \ 0<br />

Jednak ta nierówność jest prawdziwa na mocy założenia indukcyjnego oraz nierówności (**). Tym samym dowód twierdzenia (*) został zakończony :)

Teraz może pojawić się chęć sprawdzenia jak się sprawa ma z innymi postaciami dzielników, np których jest więcej: tych postaci 5k+1 czy 5k+3. Okazuje się, że akurat tego przypadku nie można rozstrzygnąć, bo np. liczba 1 ma 1 dzielnik postaci 5k+1 oraz zero dzielników postaci 5k+3, a już liczba 39 ma 1 dzielnik postaci 5k+1 i 2 dzielniki postaci 5k+3.

Zachęcam do dalszego drążenia tematu. :)

Na koniec jeszcze kilka zadanek pasujących choć trochę tematycznie:

1. Udowodnić, że liczb pierwszych jest nieskończenie wiele.

2. Udowodnić, że liczb pierwszych postaci 4k+3 jest nieskończenie wiele.

3. Udowodnić, że liczb pierwszych postaci 3k+2 jest nieskończenie wiele.

(oczywiście w zadaniach 2. i 3. nie korzystamy z twierdzenie Dirichleta :) )


  • 0



Ostatni odwiedzający

Ostatnie komentarze

Buttony