Wykazać podzielność

[Undre]

\(\displaystyle{ p \ | \ n^p - n}\)

czy przy sprawdzaniu tego dla (n+1) muszę to rozpisać na dwumiany ?

[soliter]

Tak, rozpisz na dwumiany.
\(\displaystyle{ (n+1)^p}\)
Zauważysz, że dla wszystkich k (w rozwinięciu mam na myśli \(\displaystyle{ {p\choose k}}\)
oprócz k=0 i k=p współczynniki będą podzielne przez p i wyjdzie mniej więcej cos takiego (tak pamiętam)
\(\displaystyle{ (n+1)^p-(p+1)=cp +(n^p+1)-(p+1)}\)
Wszystko ładnie wyjdzie na mocy założenia indukcyjnego.
Powiem więcej, możesz to też udowodnić w tył, czyli dla wszystkich całkowitych.

[Undre]

No luz właśnie mi tak wychodzi ... ale jako jednostka z natury leniwa miałem nadzieję że da się to zrobić używając mniej długopisu pozdrawiam

[soliter]

Ja też nie lubię pisać i znięchęcam się łatwo przy "byczych" nierównościach.

[Tomasz Rużycki]

Alternatywny dowód:

Weźmy takie \(\displaystyle{ a}\) i \(\displaystyle{ p}\), że \(\displaystyle{ \gcd(a,p)=1}\). Niech \(\displaystyle{ r_1,\ldots r_{p-1}}\) będą resztami z dzielenia liczb \(\displaystyle{ a,2a,\ldots,(p-1)a}\) przez \(\displaystyle{ p}\).

\(\displaystyle{ r_i\in \{1,\ldots,p-1\}}\).

Niech
\(\displaystyle{ a\equiv r_1 {\pmod p}}\),
...
\(\displaystyle{ (p-1)a\equiv r_{p-1}{\pmod p}}\).

Oczywiście \(\displaystyle{ 1\cdot 2\cdot\ldots \cdot (p-1) = r_1\cdot\ldots \cdot r_{p-1}}\).

Mnożąc tamte kongruencje stronami, dostajemy:

\(\displaystyle{ 1\cdot\ldots\cdot (p-1) a^{p-1} \equiv r_1\cdot\ldots r_{p-1}=1\cdot \ldots (p-1) {\pmod p}}\).

Możemy sobie podzielić obie strony kongruencji przez jej prawą strone, gdyż nie jest ona podzielna przez \(\displaystyle{ p}\), więc

\(\displaystyle{ a^{p-1}\equiv 1 {\pmod p}}\), a to już kończy dowód.


Dodam, że dla \(\displaystyle{ a}\) i \(\displaystyle{ n}\) takich, że \(\displaystyle{ \gcd(a,n)=1}\) zachodzi \(\displaystyle{ a^{\varphi(n)}\equiv 1 {\pmod n}}\), gdzie \(\displaystyle{ \varphi(n)}\) to ilość liczb nie wiekszych niż \(\displaystyle{ n}\) i względnie pierwszych z \(\displaystyle{ n}\), \(\displaystyle{ n>1}\). Jest to twierdzenie Eulera.


Ups... Dopiero teraz zauważyłem, że napisałeś posta w dziale indukcja: Przepraszam... Zostawie tego posta, może komuś się przyda.


Pozdrawiam,
--
Tomek Rużycki