Discrete Mathematics

_____________________________

COUNTING

247

Then,

aP

-a=

(b+

W

-(b+

1) =

bP

+(~

}P-

1

+

....

+(p~

1

)b+

1-b-1

=

(bp

-b)+(~

}p-I+

..

..

+c~

1

}

Here the expression

bP

- b in parenthesis is divisible by p

by

the induction hypothesis, while the other terms

are divisible by p by lemma. It follows that

aP

- a is also divisible by p, which completes the induction.

Let us take a look at the history

of

mathematics here. Fermat is most famous for his "Last" theorem,

which is the following assertion:

if

n > 2, then the sum

of

the n-th powers

of

two positive integers is never an n-th power

of

a positive

integer.

(The assumption that n > 2 is essential: there ...