Małe Twierdzenia Fermata

[Nuna]

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

[Janusz Tracz]

Zauważmy, że założenie implikuje

\(\displaystyle{ (a+1)^p \equiv 1+a^p \bmod p }\)

skąd takie założenie:    

Samo założenie też łatwo zweryfikować. Zauważy, że dla dowolnego \(\displaystyle{ k\in \left\{ 1,...,p-1\right\} }\) zachodzi \(\displaystyle{ p\Bigg| {p \choose k} }\) zatem:

\(\displaystyle{ (a+1)^p = {p \choose 0}a^0+ {p \choose 1}a^1+ {p \choose 2}a^2\equiv 0+...{p \choose p-1}a^{p-1}+{p \choose p}a^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.

[Nuna]

Myślałam, że da się uniknąć jakoś indukcji, dziękuję za odpowiedź.

[Janusz Tracz]

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:

\(\displaystyle{ a^p= \sum_{k_1+k_2+...+k_a=p}^{} {p \choose k_1,k_2,...,k_a} }\)

kombinatoryczne interpretacje można pominąć:    

Można od razu skorzystać z

Kod: Zaznacz cały

https://en.wikipedia.org/wiki/Multinomial_theorem

tam mamy wzór który po położeniu \(\displaystyle{ x_i=1}\) da powyższą równość. Oznaczenia zgodnie z linkowaną stroną.

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:

\(\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.

[a4karo]

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\)