Math Help Forum - View Single Post

Grandad · #10 July 8th, 2009, 02:27 AM

Hello matsci0000

Quote:

Originally Posted by matsci0000

Thanks Grandad for the proof but I do not know anything about modulus and its operations.Is there any other alternate solution for this?

Yes. The modular arithmetic notation I used is a convenient way of discussing remainders when one integer is divided by another. But instead of using the mod notation, we can write the proof out as follows (it just looks a bit more complicated, that's all).

In the proof that follows, $A, B, ...$ are integers.

$P(k+1) = (p+1)P(k) - P(k-1)$

$= pP(k) + P(k) - P(k-1)$

$\Rightarrow P(k+1) =Ap+ P(k)-P(k-1)$ . Call this equation (1)

If we now replace $k$ by $(k-1)$ in this equation we get:

$P(k) = Bp+P(k-1) - P(k-2)$

$\Rightarrow P(k+1) =(A+B)p +P(k-1) - P(k-2) - P(k-1)$

$\Rightarrow P(k+1) =(A+B)p -P(k-2)$

Therefore if $P(k-2)$ is not a multiple of $p$ , then $P(k+1)$ isn't either.

So, provided $P(1), P(2)$ and $P(3)$ are not multiples of $p$ , we have sufficient to show that $P(k)$ is not a multiple of $p$ for all integers $k \ge 1$ .

$P(1) = \alpha + \beta = p+1 \Rightarrow P(1)$ leaves a remainder $1$ when divided by $p$ .

$P(2) = (\alpha+\beta)^2 - 2\alpha\beta = (p+1)^2 - 2 = p^2 +p+(p-1)$

$\Rightarrow P(2) =Cp+ (p-1)$

$\Rightarrow P(2)$ leaves a remainder $(p-1)> 0$ , for $p \ge 2$

$P(3) = Dp+ P(2) - P(1)$ (using equation (1) with $k = 2$ )

$\Rightarrow P(3) = (C+D)p + (p-1) - (p+1)$

$\Rightarrow P(3) = (C+D-1)p + (p - 2)$

$\Rightarrow P(3)$ leaves a remainder $(p-2) > 0$ , for $p \ge 3$ , when divided by $p$ .

That completes the proof.

Grandad

The following users thank Grandad for this useful post:
matsci0000
$Donate to MHF$