sprawdzenie podzielności

[112358]

Jak sprawdzić w oparciu o kongruencje, że np.

\(\displaystyle{ 30|n^5-n}\)?

[JakimPL]

Najpierw warto rozłożyć wielomian \(\displaystyle{ n^5-n}\):

\(\displaystyle{ n^5 - n = (n-1)(n^4+n^3+n^2+n+1)=(n-1)(n^2(n^2+n)+(n^2+n)) = (n-1)(n^2+1)(n^2+n)=\ldots}\)

Ciekawostka:    

\(\displaystyle{ N_5 = 30}\) (mianownik piątej liczby Bernoulliego) jest największą liczbą dzielącą wszystkie liczby postaci \(\displaystyle{ n^5 - n}\). Podobnie \(\displaystyle{ N_k}\) jest największą liczbą, dla której zachodzi \(\displaystyle{ N_k|n^k-n}\) dla wszystkich \(\displaystyle{ n}\) naturalnych. W szczególności dla \(\displaystyle{ k}\) parzystych \(\displaystyle{ N_k = 2}\).

[bakala12]

W oparciu o kongruencje:
Z małego twierdzenia Fermata:
\(\displaystyle{ n^{5} \equiv n \pmod{5} \\
n^{5} \equiv n^{3} \equiv n \pmod{3}}\)
Prosto mamy również \(\displaystyle{ n^{5} \equiv n \pmod{2}}\).
Stąd:
\(\displaystyle{ 2|n^{5}-n \\
3| n^{5}-n \\
5| n^{5}-n}\)
Zatem \(\displaystyle{ 30|n^{5}-n}\).