Math Help Forum - View Single Post

matsci0000 · #9 July 7th, 2009, 07:59 PM

Quote:

Originally Posted by Grandad

Hello everyone -

I don't think any of the proofs so far are really complete, although simplependulum has all but done it - without adequately testing the initial hypotheses. (Where, for instance, is the requirement that $p \ge 3$ ?)

I'm afraid ProveIt's last line doesn't work. Just because $\frac{A}{p}$ is not an integer and $\frac{B}{p}$ is not an integer doesn't necessarily mean that $\frac{A-B}{p}$ is not an integer.

May I suggest the following.

Using the notation $P(k) = \alpha^k +\beta^k$ , and the proofs so far offered, we know that

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

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

$\Rightarrow P(k+1) \equiv P(k)-P(k-1) \mod p$ . Call this equation (1)

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

$P(k) \equiv P(k-1) - P(k-2) \mod p$

$\Rightarrow P(k+1) \equiv P(k-1) - P(k-2) - P(k-1) \mod p$

$\Rightarrow P(k+1) \equiv -P(k-2) \mod p$

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)$ is not a multiple of $p$

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

$\Rightarrow P(2) \equiv (p-1) \mod p$

$\Rightarrow P(2) \ne 0 \mod p$ , for $p \ge 2$

$P(3) \equiv P(2) - P(1) \mod p$ (using equation (1) with $k = 2$ )

$\Rightarrow P(3) \equiv (p-1) - 1 \mod p$

$\Rightarrow P(3) \equiv (p-2) \mod p$

$\Rightarrow P(3) \ne 0 \mod p$ , for $p\ge 3$

And that completes the proof, I think.

Grandad

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