The work here is actual assigned homework from Dr. Mary Flagg’s Number Theory, Math 4383 – Section 19842, going on now at the University of Houston this Spring 2012 semester. This is from homework assignment 2. The problems are taken from **Elementary Number Theory**, Seventh Edition, by David. M. Burton.

However, I will be going beyond much of this homework by adding additional material as it strikes me as being relevant to the topic at hand.

**Basic Divisibility Theory of the Integers**

2.2 – 5. For,prove thatis an integer.

**Proof.** By the division algorithm, if , we may write

where . Therefore, since r may only assume integer values, we have that may only assume any one of the following six forms, corresponding to each value of the remainder so that n must be in one of the following forms:

, , , , ,

Therefore, we need only substitute each of these in our expression and simplify to see what results. So, proceeding on a case by case basis, we have, for the first case:

for we get

which is an integer, as there are no fractions left on the RHS. Now, in the second case:

for we get

which is also clearly an integer. And, in the third case:

for we get

which is also clearly an integer. And, in the fourth case:

for we get

which is also clearly an integer. And, in the fifth case:

for we get

which is also clearly an integer. And, in the sixth case:

for we get

and this too is an integer. Therefore, for all values of , we have established that

is an integer for all . **QED**

Note. Of course, this expression is also the sum of the squares of the first n integers, or

for all and so, because the square of an integer is an integer, so would be a sum of squares of integers, and so this may be developed out into another proof, as a corollary, by obtaining and proving the summation formula itself it would follow that it is an integer.

2.2 – 11. If n is an odd integer, show thatis of the form 16k.

**Proof**. Assume that n has the form so that n is odd. Then, by direct substitution and upon simplification, we have

where

.

Therefore, is of the form 16K for all odd positive integers. **QED**

2.3 – 3. Prove or disprove: if, then eitheror.

**Proof**. By counterexample, we have

but false and is false.

So, without loss of generality, we may say that,

if and but , then it is true that:

or more fully, that and we see that and are both false. **QED**.

2.3 – 4. For, use mathematical induction to establish the following divisibility statement that.

**Proof**. Using the PMI, we have for ,

or

and therefore it is true that

when n=1. Assume that for some positive integer k that

is true and note that this also means that:

or that

or

for some multiple q of 15. But the LHS factors into:

which implies that:

or

and now this implies that, either:

or else

or else

and likewise for 5, that either:

or else

or else

one of which must be true and for each of the integers 3 and 5. Now, for (k+1) we have that:

or

or

where q is the quotient and r must equal 0 if 15 is to divide exactly into . Now, by factoring, we have that:

so that we have also:

or

but each of these factors is simply the same as the assumed case n=k when n=k+1. And it is already true, by assumption, that

or

Therefore, by the PMI, we have that,

for all

, . QED

2.3 – 13 Given two integers a and b, prove the following: there exists integers x and y for whichif and only if

**Proof**. This is almost the converse of theorem 2.4 on page 23, namely that, if a and b are both integers not equal to zero, then a and b are relatively prime if and only if there exist integers x and y such that . From this we have that, if , then:

but from corollary 1 to the theorem 2.4, both on page 23, we have that if then and this implies that:

but multiplying both sides of this by d and setting d=c yields:

but this means that but c|a and c|b and therefore because . **QED**

2.3 – 13(b) If there exist integers x and y for which,then.

**Proof**. This is theorem 2.4 where the terms are inverted. We have, by theorem 2.4, that a and b are relatively prime if and only if there exists integers x and you such that . Now, suppose that for some choice of x and y, such that . Because and , by theorm 2.2 we get that or but this last condition forces d to be 1. Therefore, must be true. **QED**

2.3 – 20(e). Confirm the following properties of the greatest common divisor. Ifandand,then.

**Proof**. We are given that a and b are relatively prime, which means that:

for some linear combination of a and b their exist such integers x and y that this is true. Now, if and means that and for some q, q’, r, r’. Therefore, we must have that d divides either a or c, given that , and likewise, d must divide either b or c, given that .

Assume, in the first case, that d divides a but not c. And assume that, in the second case, that d divides b but not c also. Then we would have and or subtracting these from the other set, that:

or

and

or

but a and b are relatively prime implies, if d dives both a and b, then:

or

but since it is also true that and that each implies that and that the respectably, which is a contradiction. Therefore, d must divide c if and . **QED**

2.3 – 21.

(a) Prove that if, then.

Proof. First off, if , then there exists a q and r such that:

where and so, we are being asked to prove that:

where

Now, from first principles, because , we must have that:

or else there could be no division by d into n in integer terms, and so therefore, we also have:

for some positive integer because . Note that this implies that . Now, subtracting one from both sides yields:

And, because implies that , and this implies that , upon division of the RHS by the LHS, yields:

, then , and so, if the , then

for some . Now, without loss of generally, taking and

substituting, we have:

but this implies that

or

or dividing both sides by b

which implies that

and likewise argument if we go substituting but this is just and therefore, if , then . **QED**

2.4 – 9. Prove that the greatest common divisor of two positive numbers a and b divides their least common multiple, especially that.

**Proof.** By merging the definitions of the gcd and lcm of two integers, a and b, we have that the gcd of a and b is the positive integer d satisfying the following:

(a) and

(b) if and , then

and the lcm of two positive integers a and b is the positive integer m satisfying:

(a) and

(b) If and , with , then

but and , therefore and because and . Again, we have that and , therefore and because and . Therefore, we see that the gcd does indeed divide the lcm, and we have established that

.

**QED**

Saturday 28 January 2012

© Kurt Lovelace all right reserved