Advanced High-School Mathematics

SECTION 2.1 Elementary Number Theory 85

Clearly P(1) is true. Assuming that P(n) is true, assume that

uandv are positive integers such that the maximum ofuandv

is n+ 1. Then the maximum of u−1 and v−1 is n, forcing

u−1 =v−1 by the validity ofP(n). Therefore,u=v. What’s

wrong with this argument?

12. If A is a finite subset of real numbers, let π(A) be the prod-
    uct of the elements of A. If A = ∅, set π(A) = 1. Let Sn =
    { 1 , 2 , 3 ,...,n}, n≥1 and show that

(a)

∑

A⊆Sn

1

π(A)

=n+ 1,and that

(b)

∑

A⊆Sn

(−1)|A|

π(A)

= 0

13. IfAis a finite subset of real numbers, letσ(A) be the sum of the
    elements ofA. Let n≥1, and setSn={ 1 , 2 , 3 ,...,n},as above.
    Show that

(a)^16

∑

A⊆Sn

σ(A)

π(A)

= (n^2 + 2n)−(n+ 1)

(

1 +

1

2

+

1

3

+···+

1

n

)

,and

that

(b)

∑

A⊆Sn

(−1)|A|σ(A)

π(A)

=−

1

n

2.1.6 Fermat’s and Euler’s theorems

We start with a potentially surprising observation. Namely we consider
integersa not divisible by 7 and consider powersa^6 , reduced modulo

7. Note that we may, by the division algorithm, writea = 7q+r,
   where sincea is not divisible by 7, then 1 ≤r ≤ 6. Therefore, using
   the binomial theorem, we get

(^16) This is Problem #2 on the 20th USA Mathematical Olympiad, April 23, 1991. It’s really not
that hard!