deelbaarheid
Opgave - VWO 2001 vraag 1
Toon aan dat, voor elk natuurlijk getal $n>1$ geldt: $(n-1)^2 | n^{n-1}-1$.
- login om te reageren
Olympia
Nederlandstalig olympiadeproject
Zoeken
Random generator
Niveau
Wie is online
Er zijn momenteel 0 gebruikers en 0 gasten online.
Oplossing
Het volstaat te bewijzen dat $n^{n-2}+n^{n-1}+\cdots+n^2+n+1\equiv0\pmod{n-1}$. Nu weten we dat $n\equiv1\pmod{n-1}$ en dus ook $n^m\equiv1\pmod{n-1}$ en aangezien er $n-1$ termen in de uitdrukking staan sommen ze op naar $n-1\equiv0\pmod{n-1}$.
$n^{n-1}-1=(n-1)(n^{n-2}+n^{n-3}+...+n+1)$
$\Rightarrow$ het volstaat dus te bewijzen dat $n-1|n^{n-2}+n^{n-3}+...+n+1$ .
Als $n-1|n^{n-2}+n^{n-3}+...+n+1$
$\Leftrightarrow n-1|n^{n-2}+n^{n-3}+...+n+1 - (n-1)(n^{n-3})=2n^{n-3}+n^{n-4}...+n+1$
$\Leftrightarrow n-1|2n^{n-3}+n^{n-4}...+n+1 - 2\times (n-1)(n^{n-4})=3n^{n-4}+n^{n-5}...+n+1$
Inductiehypothese: we hebben te bewijzen dat
$ n-1|(x-1)n^{n-x}+n^{n-x-1}+n^{n-x-2}+\cdots +n+1$ en dit voor $x \le n-1.$
Inductiebasis: We hebben dit al aangetoond voor $x=1,2,3,4$
Inductiestap:
$$ n-1|(x-1)n^{n-x}+n^{n-x-1}+n^{n-x-2}+\cdots +n+1$$
$$ \Leftrightarrow n-1|(x-1)n^{n-x}+n^{n-x-1}+n^{n-x-2}+\cdots +n+1 - (x-1)\cdot(n-1)n^{n-x-1}
$$
$$\Leftrightarrow n-1|x \cdot n^{n-x-1}+n^{n-x-2}+n^{n-x-2}+\cdots +n+1 $$
Dat is exact de inductiehpothese voor $x+1.$
Met inductie geldt dus dat het equivalent is met de bijhorende formule voor $x=n-1$
$\Leftrightarrow n-1|(n-2)n+1=n^2-2n+1=(n-1)^2$ (triviaal...)