Wyprowadź z własności \(\displaystyle{ (a+b)^{p} = a^{p} + b^{p} \bmod p}\) Małe Twierdzenie Fermata: jeśli \(\displaystyle{ p}\) jest liczbą pierwszą, to \(\displaystyle{ a^{p} = a \bmod p}\) dla dowolnego naturalnego \(\displaystyle{ a}\).
Niby trywialne, a jednak coś mi nie gra. Próbowałam podstawiać \(\displaystyle{ b=0}\), ale przecież to nie będzie działało...
Małe Twierdzenia Fermata
-
- Użytkownik
- Posty: 101
- Rejestracja: 7 gru 2019, o 19:36
- Płeć: Kobieta
- wiek: 19
- Podziękował: 58 razy
Małe Twierdzenia Fermata
Ostatnio zmieniony 19 mar 2020, o 15:25 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
- Janusz Tracz
- Użytkownik
- Posty: 4068
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 80 razy
- Pomógł: 1393 razy
Re: Małe Twierdzenia Fermata
Zauważmy, że założenie implikuje
\(\displaystyle{ (a+1)^p \equiv 1+a^p \bmod p }\)
równość ta skłania do indukcyjnego rozumowania. Wszak jeśli twierdzenie \(\displaystyle{ a^p \equiv a \bmod p}\) było by prawdziwe to z powyższej równości dostali byśmy jeszcze, że
\(\displaystyle{ (a+1)^p \equiv 1+a^p \equiv 1+a \bmod p }\)
czyli krok indukcyjny. Czyli okazuje się, że trzeba to domino (ładnie poukładane) jeszcze przewrócić co sprawdza się do sprawdzenia, że dla \(\displaystyle{ a=1}\) twierdzenie jest prawdziwe.
\(\displaystyle{ (a+1)^p \equiv 1+a^p \bmod p }\)
skąd takie założenie:
\(\displaystyle{ (a+1)^p \equiv 1+a^p \equiv 1+a \bmod p }\)
czyli krok indukcyjny. Czyli okazuje się, że trzeba to domino (ładnie poukładane) jeszcze przewrócić co sprawdza się do sprawdzenia, że dla \(\displaystyle{ a=1}\) twierdzenie jest prawdziwe.
- Janusz Tracz
- Użytkownik
- Posty: 4068
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 80 razy
- Pomógł: 1393 razy
Re: Małe Twierdzenia Fermata
Też myślałem, że uda się uniknąć indukcji dlatego rozwiązanie do ostatniego momentu nie korzysta z indukcji. Bez indukcji mogło by to wyglądać tak, że rozważamy liczbę rozmieszczeń \(\displaystyle{ a\in \NN}\) rozróżnialnych przedmiotów w \(\displaystyle{ p\in \mathbb{P}}\) rozróżnialnych urnach. Oczywiście takich rozmieszczeń jest \(\displaystyle{ a^p}\) z drugiej strony można rozważać poszczególne składowe takich rozmieszczeń gdzie w \(\displaystyle{ i}\) tej urnie znajdzie się \(\displaystyle{ k_i}\) przedmiotów wtedy mamy
\(\displaystyle{ {p \choose k_1,k_2,...,k_a} = \frac{p!}{k_1!k_2! \cdot ... \cdot k_a!} }\)
rozmieszczeń, przy czym \(\displaystyle{ k_1+k_2+...+k_a=p}\). Bo to tak jakby permutacje zbioru \(\displaystyle{ \left[ p\right] }\) dzielić na części \(\displaystyle{ k_1,k_2,...,k_a}\) elementowe i utożsamiać ze sobą takie rozkłady w których permutacyjny jedynie w urnie. Zatem:
jeśli zauważymy teraz (obserwacje tą nazwę lematem z którego niebawem skożystamy), że gdy co najmniej dwa \(\displaystyle{ k_i,k_j}\) w sumie \(\displaystyle{ k_1+k_2+...+k_a=p}\) są niezerowe to
\(\displaystyle{ {p \choose k_1,k_2,...,k_a} \equiv 0 \bmod p}\)
Zatem sumę \(\displaystyle{ \sum_{k_1+k_2+...+k_a=p}^{} {p \choose k_1,k_2,...,k_a} }\) można podzielić na dwie sumy:
gdzie:
\(\displaystyle{ \mathcal{A}= \left\{ \left\langle k_1,k_2,...,k_a \right\rangle : \text{istnieje dokładnie jedno takie } i \text{ że } k_i=p \text{ pozostałe zą zerowe} \right\} }\)
\(\displaystyle{ \mathcal{B}= \left\{ \left\langle k_1,k_2,...,k_a \right\rangle : \text{istnieje co najmniej dwa indeksy } i, j \text{ że } k_i,k_j \neq 0 \right\} }\)
Oczywiście zbiór \(\displaystyle{ \mathcal{A}}\) składa się z elementów postaci \(\displaystyle{ \left\langle p,0,0,...,0\right\rangle, \left\langle 0,p,0,...,0\right\rangle, ..., \left\langle 0,0,0,...,p\right\rangle }\) jest ich \(\displaystyle{ a}\) oraz dla każdego z nich element sumy wynosi \(\displaystyle{ 1}\) zatem cała suma po \(\displaystyle{ \mathcal{A}}\) wynosi \(\displaystyle{ a}\). Suma po \(\displaystyle{ \mathcal{B}}\) jest podzielna przez \(\displaystyle{ p}\) wszak każdy składnik sumy dzieli się przez \(\displaystyle{ p}\) co wynika ze wspomnianego wcześniej lematu. Zatem powyższe rozbici w kontekście \(\displaystyle{ \bmod p}\) to:
Udało się bez indukcji. Choć zarzucić możesz mi, że nie skorzystałem z \(\displaystyle{ (a+b)^{p} \equiv a^{p} + b^{p} \bmod p}\) to uznałem jednak, że założenie to jest tak mocno powiązane z lematem, że można uznać to za pomocne założenie nawet i w tym rozwiązaniu.
\(\displaystyle{ {p \choose k_1,k_2,...,k_a} = \frac{p!}{k_1!k_2! \cdot ... \cdot k_a!} }\)
rozmieszczeń, przy czym \(\displaystyle{ k_1+k_2+...+k_a=p}\). Bo to tak jakby permutacje zbioru \(\displaystyle{ \left[ p\right] }\) dzielić na części \(\displaystyle{ k_1,k_2,...,k_a}\) elementowe i utożsamiać ze sobą takie rozkłady w których permutacyjny jedynie w urnie. Zatem:
\(\displaystyle{ a^p= \sum_{k_1+k_2+...+k_a=p}^{} {p \choose k_1,k_2,...,k_a} }\)
kombinatoryczne interpretacje można pominąć:
\(\displaystyle{ {p \choose k_1,k_2,...,k_a} \equiv 0 \bmod p}\)
Zatem sumę \(\displaystyle{ \sum_{k_1+k_2+...+k_a=p}^{} {p \choose k_1,k_2,...,k_a} }\) można podzielić na dwie sumy:
\(\displaystyle{ \sum_{k_1+k_2+...+k_a=p}^{} {p \choose k_1,k_2,...,k_a} = \sum_{\left\langle k_1,k_2,...,k_a\right\rangle \in \mathcal{A}}^{} {p \choose k_1,k_2,...,k_a} + \sum_{\left\langle k_1,k_2,...,k_a\right\rangle \in \mathcal{B}}^{} {p \choose k_1,k_2,...,k_a} }\)
gdzie:
\(\displaystyle{ \mathcal{A}= \left\{ \left\langle k_1,k_2,...,k_a \right\rangle : \text{istnieje dokładnie jedno takie } i \text{ że } k_i=p \text{ pozostałe zą zerowe} \right\} }\)
\(\displaystyle{ \mathcal{B}= \left\{ \left\langle k_1,k_2,...,k_a \right\rangle : \text{istnieje co najmniej dwa indeksy } i, j \text{ że } k_i,k_j \neq 0 \right\} }\)
Oczywiście zbiór \(\displaystyle{ \mathcal{A}}\) składa się z elementów postaci \(\displaystyle{ \left\langle p,0,0,...,0\right\rangle, \left\langle 0,p,0,...,0\right\rangle, ..., \left\langle 0,0,0,...,p\right\rangle }\) jest ich \(\displaystyle{ a}\) oraz dla każdego z nich element sumy wynosi \(\displaystyle{ 1}\) zatem cała suma po \(\displaystyle{ \mathcal{A}}\) wynosi \(\displaystyle{ a}\). Suma po \(\displaystyle{ \mathcal{B}}\) jest podzielna przez \(\displaystyle{ p}\) wszak każdy składnik sumy dzieli się przez \(\displaystyle{ p}\) co wynika ze wspomnianego wcześniej lematu. Zatem powyższe rozbici w kontekście \(\displaystyle{ \bmod p}\) to:
\(\displaystyle{ \sum_{k_1+k_2+...+k_a=p}^{} {p \choose k_1,k_2,...,k_a} \equiv \sum_{\left\langle k_1,k_2,...,k_a\right\rangle \in \mathcal{A}}^{} {p \choose k_1,k_2,...,k_a} \ \ \ \ \ \bmod p}\)
czyli \(\displaystyle{ a^p \equiv a \bmod p}\)
Udało się bez indukcji. Choć zarzucić możesz mi, że nie skorzystałem z \(\displaystyle{ (a+b)^{p} \equiv a^{p} + b^{p} \bmod p}\) to uznałem jednak, że założenie to jest tak mocno powiązane z lematem, że można uznać to za pomocne założenie nawet i w tym rozwiązaniu.
-
- Użytkownik
- Posty: 22210
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3755 razy
Re: Małe Twierdzenia Fermata
To może tak
\(a^p=(a-1+1)^p\equiv (a-1)^p+1\\
(a-1)^p=(a-2+1)^p\equiv (a-2)^p+1\\
\dots\\
1^p\equiv 0^p+1\\
========================\\
a^p\equiv a\)
\(a^p=(a-1+1)^p\equiv (a-1)^p+1\\
(a-1)^p=(a-2+1)^p\equiv (a-2)^p+1\\
\dots\\
1^p\equiv 0^p+1\\
========================\\
a^p\equiv a\)