Question

How to use induction to prove \(\large 19\) divides \(\large a^{19}-a\)

Answer 1

base case : a=0
19|0^19-0

assuming 19|a^19-a, need to prove 19|(a+1)^19-(a+1)

Answer 2

My solution is kind of ugly but...
\[ (a+1)^{19}-(a+1) = \sum_{k=0}^{19} \left(\begin{matrix}19 \\ k\end{matrix}\right) x^{19-k} - (a+1)\]
Taking out the first and last terms of the sum,
\[a^{19} + \left( \sum_{k=1}^{18} \left(\begin{matrix}19 \\ k\end{matrix}\right) x^{19-k} \right) +1 - (a+1)\]
Now you see your induction hypothesis:
\[(a^{19} -a) + \left( \sum_{k=1}^{18} \left(\begin{matrix}19 \\ k\end{matrix}\right) x^{19-k} \right) \]

So you know 19 divides the first term. Because of the 19 Choose k, you know 19 decides all the following terms too.

Answer 3

**change all those x's to a's

Answer 4

nice :) so are we assuming that \(\large \binom{19}{k}\) is divisible by \(\large 19\) ?

Answer 5

Well, we're not assuming it if we can show it :P

The formula for the choose function is n!/( k! (n-k)!). Can you see why 19 divides 19!/(k! (19-k)!) for all values of k?

Answer 6

\[\large \binom{19}{k} = \dfrac{19.18.\cdots(19-k+1)}{k!}\]

since this evaluates to an integer and \(\large k\lt 19\), so 19 won't cancel out.

\(\large \binom{19}{k} = 19M\)

Answer 7

Nice! yes

Answer 8

thats true when 1<=k<=18

got it thank you so much :D

Answer 9

No problem! :)