Math Help Forum - View Single Post

Prove It · #6 July 5th, 2009, 03:22 AM

Part 2:

We know the following:

$\alpha + \beta = p + 1$

$\alpha\beta = 1$

$P(k + 1) = \alpha^{k + 1} + b^{k + 1} = (\alpha^k + \beta^k)(\alpha + \beta) - \alpha\beta(\alpha^{k - 1} + \beta^{k - 1})$ .

So $P(k + 1) = (\alpha^k + \beta^k)(p + 1) - 1(\alpha^{k - 1} + \beta^{k - 1})$

$= (p + 1)(\alpha^k + \beta^k) - (\alpha^{k - 1} + \beta^{k - 1})$

Try dividing $P(k + 1)$ by $p$ .

$\frac{P(k + 1)}{p} = \frac{(p + 1)(\alpha^k + \beta^k) - (\alpha^{k - 1} + \beta^{k - 1})}{p}$

$= \frac{(p + 1)(\alpha^k + \beta^k)}{p} - \frac{\alpha^{k - 1} + \beta^{k - 1}}{p}$ .

Clearly $p + 1$ can not be divided by $p$ exactly, and you have already established that $\alpha^k + \beta^k$ and $\alpha^{k - 1} + \beta^{k - 1}$ are not divisible by $p$ , so $P(k + 1)$ can not be divided by $p$ .

Q.E.D.