Math 58 - Number Theory

September 12, 2006

SOLUTIONS TO

Homework 2 (due September 12):

(Most of these exercises are from the text, App. A, 1.3, or 1.5.)

 

Prove rigorously using only the axioms in Appendix A:

 

1.  If  a  and  b  are integers, then   (–a)(–b) = ab.

 

First: If a and b are any integers, then a(-b) = -(ab).

Proof:  “-(ab)” is, by definition, the unique number x that solves

                   ab + x = 0.

          Well, a(-b) does solve that equation, because

                   ab + a(-b) = ba + (-b)a      (two applications of commutativity,

                                                          needed because we only have the

                                                               left-hand form of distributivity)

                             = (b + (-b)) a                   (distributivity)

                             = 0 a                      (def. of –b, and axiom on negatives)

                             = 0.                       (by text example,

 or imbed that proof here)

          That shows that a(-b) = -(ab). //

 

Now, the problem as given.

Proof:  From the above (with –a in place of a):

                   (-a)(-b) = -((-a)b)

                             = -(b(-a))               (commutativity)

                             = -(-(ba))               (from the above, with b,a in place of a,b)

                             = ba                       (since –(–x) = x…did we prove that?)

                             = ab.   //

 

2.  If  a then  a2 ≥ 0.

 

Proof:  By the ordering axiom, either a is positive, or a=0, or –a is positive.

          If a is positive, then a2 = aa is the product of two positive numbers, so        

                   it is positive, so a2 > 0.

          If a = 0, well, then a2 ≥ 0  by definition of ≥.

          If –a is positive, then a2 = aa = (-a)(-a)  (by problem 1)

              which is the product of two positive numbers.  So again, a2 > 0.  //

3.  If  a < b  and  c < 0  then  ac > bc.

 

Proof:  a<b means that b-a is positive, and c<0 means 0-c = -c is positive.  So,

                   (b-a)(-c) must be positive.

          By distributivity (I’ll apply it on the right this time),

          b(-c) – a(-c) is positive

          so -(bc) +(ac) is positive

          so (ac) + (-(bc)) is positive

          so (ac) – (bc) is positive

          So ac > bc.

 

 

Prove by induction (or any variant on induction):

 

4.  If  n ≥ 4  then  2n < n!.

 

Proof:  BWOC, let n be the smallest integer such that n≥4 but 2n is not < n!.

          If n can’t be 4, because 24 = 16 < 24 = 4!.

          So the statement must be true for n-1 in place of n:

                   2n-1 < (n-1)!

          So

                   2n = 2 (2n-1) < 2 (n-1)! < n (n-1)! = n!.  //

 

Prove by any method:

(Extreme rigor not required.)

 

5.  If  x  and  y  are integers (different from each other) then  x – y | x2 – y2.

            (You can skip this one if you are satisfied with your proof of #7.)

 

Proof:  All we need to do is show that

                             (x-y) c = (x2 – y2)

          for some c.  But this is true when c = x + y, because of the

factorisation

                             x2-y2 = (x-y)(x+y).  //

 

6.  If  x  and  y  are integers (different from each other) and  n  is any positive

            integer,  then  x – y | xn – yn.

 

Proof:  Now all we need is the factorization

                   xn – yn = (x – y ) ( xn-1 + xn-2y + xn-3y2 + … + yn-1).      //

 

7.  If  a, b, c, d , a and c are nonzero, and  a | b  and  c | d,   then  ac | bd.

Proof:  If a | b then there is some x such that ax = b; and similarly,

there is some y

such that cy = d.  So

(ac) (xy) = bd,

which is enough to force  ac | bd.  //

 

Prove OR disprove:

(If the statement is false, a single example is enough to disprove it.  If any of these

is true, induction might be helpful in proving it.)

 

8.    If  a  is any integer, then  a2 – a  is  even.


It’s true.  Proof by factoring: 

a2 – a = a ( a-1 )

and either a or a-1 must be even, so their product is even.//

                       

9.    If  a  is any integer, then  a3 – a  is a multiple of 3.

 

True again:  Now  a3 – a = a ( a-1) (a+1),  and the factors are three

consecutive integers, so one of them must be a multiple of 3, so

a3-a is also a multiple of 3.

 

10.  If  a  is any integer, then  a4 – a  is a multiple of 4.

 

This isn’t always true.  It’s false when a=2 or when a=6, for example.

 

11.  If  a  is any integer, then  a5 – a  is a multiple of 5.

 

Two ways.  Both use the expansion

                    (x+y)5 = x5 + 5x4y + 10x3y2 + 10x2y3 + 5xy4 + y5.

          Note that all terms of the expansion are multiples of 5 except for

possibly the first and last.  If x is itself a multiple of 5, then

          all but the last term are guaranteed to be multiples of 5.

 

First:  Write  a = 5q + r,  where r must be 0, 1, 2, 3, or 4.  Now:

          a5 – a = (5q+r)5 – (5q+r)

                   = (  ± lots of multiples of 5 ) + ( r5 – r )

          Now, r must be 0, 1, 2, 3, or 4, so (r5 – r) must be

0, 0, 30, 240, or 1020 --- in every case, another multiple of 5. 

So, a5 – a  is a sum and difference of multiples of 5, so is itself

a multiple of 5.

 

Second:  At least for positive a, try inducting on a.  The statement is clearly

true when a is 0 or 1.  Assume that it’s true for (a-1).

          Now,  a5-a = ( (a-1) + 1 )5 – a

                             =  (a-1)5 + (multiples of 5) + 1 – a

                             =  (multiples of 5) + ( (a-1)5 – (a-1) ).

          By induction, the last expression is a multiple of 5, so a5-a is also

          a multiple of 5.

          (For negative a, note that  a5-a = - [ (-a)5-(-a) ], and the expression in

          square brackets is a multiple of 5, so its negative is, also.)

 

 

 

(end)