Zbadaj

[Artegor]

Zbadaj, czy dla każdego wykładnika nieparzystego \(k\) liczba \(n^k − n\) jest podzielna przez \(k\).

[panb]

Rozumiem, że ma to zachodzić dla każdego \(n\in \nn\).
Sprawdźmy jak to działa.
Dla k=1 nie ma co sprawdzać, bo wszystko jest podzielne przez 1, również \(0=n-n\).
Dla k=3 twierdzenie ma postać

• \(\forall {n\in \nn}: 3|(n^3-n)\)

Dowód (indukcyjny rzecz jasna) mógłby wyglądać tak

• \(3|0=1-1\), więc twierdzenie jest prawdziwe dla n=1

• Niech \(3|(n^3-n) \iff n^3-n=3p,\,\,\, p\in \nn\)

• \((n+1)^3-(n+1)=n^3+3n^2+3n+1-n-1=n^3-n+3(n^2+n)=3p+3(n^2+n) \iff \\ \iff 3|[(n+1)^3-(n+1)]\)
  co dowodzi prawdziwości twierdzenia dla każdego \(n\in \nn\)

Jak widać gwóźdź dowodu leży w tym, że dało się wyłączyć 3 przed nawias w rozwinięciu \((n+1)^3\).
Przyjrzyjmy się trójkątowi Pascala:
1
1 2 1
13 3 1 \(\longleftarrow\) widać podzielność przez 3
1 4 6 4 1
1 5 10 10 5 1 \(\longleftarrow\) widać podzielność przez 5
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1 \(\longleftarrow\) widać podzielność przez 7

Wobec tego, trzeba udowodnić następujący lemat

• Dla każdego \(n\in \nn: \,\,\,(2n+1)|{2n+1\choose k}\) dla \(k=1, 2, \ldots, 2n\)

Dowód (indukcyjny)

• \({3\choose 1}={3\choose 2}=3\), czyli \(3|{3\choose k}\) dla k=1,2 więc lemat jest prawdziwy dla n=1

• Niech \((2n+1)|{2n+1 \choose k}\) dla\(\,\,k=1, 2, \ldots 2n \iff {2n+1 \choose k}=p(2n+1)\) dla \(p\in \nn,\,\,\, k=1,2,\ldots, 2n\)

\({2n+3 \choose k}, \,\,\, \left( k=1,2,\ldots,2n+2\right) = \begin{cases} {2n+1\choose k}\cdot \frac{(2n+2)(2n+3)}{(2n+2-k)(2n+3-k)}= p\cdot\frac{(2n+1)(2n+2)}{(2n+2-k)(2n+3-k)}\cdot (2n+3) & k=1,2,\ldots,2n
\\ {2n+3\choose 2n+1}=(n+1)(2n+3) & k=2n+1 \\
{2n+3\choose 2n+2}=2n+3& k=2n+2\end{cases}\)

Istotnie

• Dla \(k=1,2,\ldots,2n,\,\,\,{2n+3 \choose k}= \frac{(2n+3)!}{k!(2n+3-k)!}= \frac{(2n+3)(2n+2)(2n+1)!}{k!(2n+1-k)!(2n+3-k)(2n+2-k)}=\frac{(2n+3)(2n+2)}{(2n+3-k)(2n+2-k)} \cdot {2n+1 \choose k}\)

[panb]

Dalej jakoś nie idzie - może inny sposób dowodzenia trzeba spróbować.

[Artegor]

Dziękuje za obszernie rozbudowaną odpowiedź

[Panko]

Wykładniki \(k \in \left\{3,5,7 \right\}\) nie są dobre do podania kontrprzykładu bo pozytywna odpowiedź idzie po zastosowaniu tw Eulera.

Weź za \(k=9\) .
Oraz \(\\) \(2^9-2 =56 \cdot 9+6\).