February 2012 – Inbetween Math and Poetry

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 $\displaystyle n\ge 1$ , prove that $\displaystyle n(n+1)(2n+1)/6$ is an integer.

Proof. By the division algorithm, if $\displaystyle 6|n(n+1)(2n+1)$ , we may write

$\displaystyle n(n+1)(2n+1)=6q+r$ where $\displaystyle 0\le r\le 6$ . Therefore, since r may only assume integer values, we have that $\displaystyle n(n+1)(2n+1)$ may only assume any one of the following six forms, corresponding to each value of the remainder $\displaystyle r=0,1,2,3,4,5$ so that n must be in one of the following forms:

$\displaystyle n=6q$ , $\displaystyle n=6q+1$ , $\displaystyle n=6q+2$ , $\displaystyle n=6q+3$ , $\displaystyle n=6q+4$ , $\displaystyle n=6q+5$

Therefore, we need only substitute each of these in our expression $\displaystyle n(n+1)(2n+1)/6$ and simplify to see what results. So, proceeding on a case by case basis, we have, for the first case:

$\displaystyle n(n+1)(2n+1)/6$ for $\displaystyle n=6q$ we get

$\displaystyle \frac{6q(6q+1)(2(6q)+1)}{6}=\frac{432{{q}^{3}}+108{{q}^{2}}+6q}{6}$

$\displaystyle =72{{q}^{3}}+18{{q}^{2}}+q$

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

$\displaystyle n(n+1)(2n+1)/6$ for $\displaystyle n=6q+1$ we get

$\displaystyle \frac{(6q+1)((6q+1)+1)(2(6q+1)+1)}{6}=\frac{432{{q}^{3}}+324{{q}^{2}}+78q+6}{6}$

$\displaystyle =72{{q}^{3}}+54{{q}^{2}}+13q+1$

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

$\displaystyle n(n+1)(2n+1)/6$ for $\displaystyle n=6q+2$ we get

$\displaystyle \frac{(6q+2)((6q+2)+1)(2(6q+2)+1)}{6}=\frac{432{{q}^{3}}+540{{q}^{2}}+222q+30}{6}$

$\displaystyle =72{{q}^{3}}+90{{q}^{2}}+37q+5$

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

$\displaystyle n(n+1)(2n+1)/6$ for $\displaystyle n=6q+3$ we get

$\displaystyle \frac{(6q+3)((6q+3)+1)(2(6q+3)+1)}{6}=\frac{432{{q}^{3}}+756{{q}^{2}}+438q+84}{6}$

$\displaystyle =72{{q}^{3}}+126{{q}^{2}}+73q+14$

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

$\displaystyle n(n+1)(2n+1)/6$ for $\displaystyle n=6q+4$ we get

$\displaystyle \frac{(6q+4)((6q+4)+1)(2(6q+4)+1)}{6}=\frac{432{{q}^{3}}+972{{q}^{2}}+726q+180}{6}$

$\displaystyle =72{{q}^{3}}+162{{q}^{2}}+121q+30$

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

$\displaystyle n(n+1)(2n+1)/6$ for $\displaystyle n=6q+5$ we get

$\displaystyle \frac{(6q+5)((6q+5)+1)(2(6q+5)+1)}{6}=\frac{432{{q}^{3}}+1188{{q}^{2}}+1086q+330}{6}$

$\displaystyle =72{{q}^{3}}+198{{q}^{2}}+181q+55$

and this too is an integer. Therefore, for all values of $\displaystyle n\ge 1$ , we have established that

$\displaystyle \frac{n(n+1)(2n+1)}{6}$

is an integer for all $\displaystyle n\ge 1$ . QED

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

$\displaystyle {{1}^{2}}+{{2}^{2}}+{{3}^{2}}+...+{{n}^{2}}=\frac{n(n+1)(2n+1)}{6}$

for all $\displaystyle n\ge 1$ 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 that $\displaystyle {{n}^{4}}+4{{n}^{2}}+11$ is of the form 16k.

Proof. Assume that n has the form $\displaystyle n=2k+1$ so that n is odd. Then, by direct substitution and upon simplification, we have

$\displaystyle {{(2n+1)}^{4}}+4{{(2k+1)}^{2}}+11$

$\displaystyle =(16{{k}^{4}}+16{{k}^{3}}+16{{k}^{2}}+8k+1)+(8k+4)+11$

$\displaystyle =16{{k}^{4}}+16{{k}^{3}}+16{{k}^{2}}+(8+8)k+(1+4+11)$

$\displaystyle =16{{k}^{4}}+16{{k}^{3}}+16{{k}^{2}}+16k+16$

$\displaystyle =16({{k}^{4}}+{{k}^{3}}+{{k}^{2}}+k+1)=16K$

where

$\displaystyle K={{k}^{4}}+{{k}^{3}}+{{k}^{2}}+k+1$ .

Therefore, $\displaystyle {{n}^{4}}+4{{n}^{2}}+11$ is of the form 16K for all odd positive integers. QED

2.3 – 3. Prove or disprove: if $\displaystyle a|(b+c)$ , then either $\displaystyle a|b$ or $\displaystyle a|c$ .

Proof. By counterexample, we have

$\displaystyle 18|7+11$ but $\displaystyle 18|7$ false and $\displaystyle 18|11$ is false.

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

if $\displaystyle b<a$ and $\displaystyle c<a$ but $\displaystyle b+c=a$ , then it is true that:

$\displaystyle a|(b+c)$ or more fully, that $\displaystyle \frac{b+c}{a}=\frac{a}{a}=1$ and we see that $\displaystyle a|b$ and $\displaystyle a|c$ are both false. QED.

2.3 – 4. For $\displaystyle n\ge 1$ , use mathematical induction to establish the following divisibility statement that

$\displaystyle 15|{{2}^{4n}}-1$ .

Proof. Using the PMI, we have for $\displaystyle n=1$ ,

$\displaystyle \frac{{{2}^{4(1)}}-1}{15}=\frac{{{2}^{4}}-1}{15}=\frac{16-1}{15}=\frac{15}{15}=1$

$\displaystyle ({{2}^{4}}-1)=1\cdot 15+0$

and therefore it is true that

$\displaystyle 15|{{2}^{4n}}-1$

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

$\displaystyle 15|{{2}^{4k}}-1$

is true and note that this also means that:

$\displaystyle 3\cdot 5|{{2}^{4k}}-1$

or that

$\displaystyle {{2}^{4k}}-1=15q$

$\displaystyle {{2}^{4k}}-1=3\cdot 5\cdot q$

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

$\displaystyle {{2}^{4k}}-1=({{2}^{k}}+1)({{2}^{2k}}+1)({{2}^{k}}-1)$

which implies that:

$\displaystyle 3\cdot 5|({{2}^{k}}+1)({{2}^{2k}}+1)({{2}^{k}}-1)$

$\displaystyle ({{2}^{k}}+1)({{2}^{2k}}+1)({{2}^{k}}-1)=3\cdot 5\cdot q$

and now this implies that, either:

$\displaystyle 3|{{2}^{k}}+1$

or else

$\displaystyle 3|{{2}^{2k}}+1$

or else

$\displaystyle 3|{{2}^{k}}-1$

and likewise for 5, that either:

$\displaystyle 5|{{2}^{k}}+1$

or else

$\displaystyle 5|{{2}^{2k}}+1$

or else

$\displaystyle 5|{{2}^{k}}-1$

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

$\displaystyle \frac{{{2}^{4(k+1)}}-1}{15}=\frac{{{2}^{4k+4}}-1}{15}=q+r$

$\displaystyle {{2}^{4k+4}}-1=15q$

$\displaystyle {{2}^{4k+4}}-1=3\cdot 5\cdot q$

where q is the quotient and r must equal 0 if 15 is to divide exactly into $\displaystyle {{2}^{4k+4}}-1$ . Now, by factoring, we have that:

$\displaystyle {{2}^{4k+4}}-1=({{2}^{k+1}}+1)({{2}^{2k+2}}+1)({{2}^{k+1}}-1)$

so that we have also:

$\displaystyle ({{2}^{k+1}}+1)({{2}^{2k+2}}+1)({{2}^{k+1}}-1)=15q$

$\displaystyle ({{2}^{k+1}}+1)({{2}^{2k+2}}+1)({{2}^{k+1}}-1)=3\cdot 5\cdot q$

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

$\displaystyle 3\cdot 5|({{2}^{k}}+1)({{2}^{2k}}+1)({{2}^{k}}-1)$

$\displaystyle 3\cdot 5|{{2}^{4k}}-1$

Therefore, by the PMI, we have that,

$\displaystyle 15|{{2}^{4n}}-1$

for all

$\displaystyle n\ge 1$ , $\displaystyle n\in {{\mathbb{Z}}^{+}}$ . QED

2.3 – 13 Given two integers a and b, prove the following: there exists integers x and y for which $\displaystyle c=ax+by$ if and only if $\displaystyle \gcd (a,b)|c.$

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 $\displaystyle 1=ax+by$ . From this we have that, if $\displaystyle \gcd (a,b)=1$ , then:

$\displaystyle 1=ax+by$ but from corollary 1 to the theorem 2.4, both on page 23, we have that if $\displaystyle \gcd (a,b)=d$ then $\displaystyle gdc(a/d,b/d)=1$ and this implies that:

$\displaystyle 1=\left( \frac{a}{d} \right)x+\left( \frac{b}{d} \right)y$

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

$\displaystyle c=ax+by$

but this means that $\displaystyle \gcd (a,b)=c$ but c|a and c|b and therefore $\displaystyle \gcd (a,b)|c$ because $\displaystyle \frac{\gcd (a,b)}{c}=\frac{c}{c}=1$ . QED

2.3 – 13(b) If there exist integers x and y for which $\displaystyle ax+by=\gcd (a,b)$ , then $\displaystyle \gcd (x,y)=1$ .

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 $\displaystyle 1=ax+by$ . Now, suppose that $\displaystyle 1=ax+by$ for some choice of x and y, such that $\displaystyle =\gcd (a,b)$ . Because $\displaystyle |a$ and $\displaystyle |b$ , by theorm 2.2 we get that $\displaystyle |(ax+by)$ or $\displaystyle =0$ but this last condition forces d to be 1. Therefore, $\displaystyle \gcd (x,y)=1$ must be true. QED

2.3 – 20(e). Confirm the following properties of the greatest common divisor. If $\displaystyle \gcd (a,b)=1$ and $\displaystyle |ac$ and $\displaystyle |bc$ , then $\displaystyle |c$ .

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

$\displaystyle 1=ax+by$ for some linear combination of a and b their exist such integers x and y that this is true. Now, if $\displaystyle |ac$ and $\displaystyle |bc$ means that $\displaystyle ac=qd+r$ and $\displaystyle bc={{q}^{'}}d+{{r}^{'}}$ for some q, q’, r, r’. Therefore, we must have that d divides either a or c, given that $\displaystyle d|ac$ , and likewise, d must divide either b or c, given that $\displaystyle d|bc$ .

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 $\displaystyle a={{q}_{1}}d+{{r}_{1}}$ and $\displaystyle b={{q}_{1}}^{'}d+{{r}^{'}}_{1}$ or subtracting these from the other set, that:

$\displaystyle ac-a=q-{{q}_{1}}d+(r-{{r}_{1}})$

$\displaystyle a(c-1)=(q-{{q}_{1}})d+(r-{{r}_{1}})$

and

$\displaystyle c-b={{q}^{'}}-{{q}_{1}}^{'}d+({{r}^{'}}-{{r}_{1}}^{'})$

$\displaystyle (c-1)=({{q}^{'}}-{{q}_{1}}^{'})d+({{r}^{'}}-{{r}_{1}}^{'})$

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

$\displaystyle 1=\left( \frac{a}{d} \right)x+\left( \frac{b}{d} \right)y$

$\displaystyle d=ax+by$

but since it is also true that $\displaystyle d|ac$ and that $\displaystyle d|bc$ each implies that $\displaystyle \gcd (d,a)=1$ and that the $\displaystyle \gcd (d,b)=1$ respectably, which is a contradiction. Therefore, d must divide c if $\displaystyle d|ac$ and $\displaystyle d|bc$ . QED

2.3 – 21.
(a) Prove that if $\displaystyle d|n$ , then $\displaystyle {{2}^{d}}-1|{{2}^{n}}-1$ .

Proof. First off, if $\displaystyle d|n$ , then there exists a q and r such that:

$\displaystyle n=qd+r$ where $\displaystyle 0\le r\le d$ and so, we are being asked to prove that:

$\displaystyle ({{2}^{n}}-1)=q({{2}^{d}}-1)+r$ where $\displaystyle 0\le r\le ({{2}^{d}}-1)$

Now, from first principles, because $\displaystyle d|n$ , we must have that:

$\displaystyle d<n$

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

$\displaystyle {{a}^{d}}<{{a}^{n}}$ for some positive integer $\displaystyle a\ge 1$ because $\displaystyle d<n$ . Note that this implies that $\displaystyle 1<\frac{{{a}^{n}}}{{{a}^{d}}}={{a}^{n-d}}$ . Now, subtracting one from both sides yields:

$\displaystyle {{a}^{d}}-1<{{a}^{n}}-1$

And, because $\displaystyle d<n$ implies that $\displaystyle {{a}^{d}}<{{a}^{n}}$ , and this implies that $\displaystyle {{a}^{d}}-1<{{a}^{n}}-1$ , upon division of the RHS by the LHS, yields:

$\displaystyle 1b>0$ , then $\displaystyle a+b\le ab$ , and so, if the $\displaystyle \gcd (a,b)=1$ , then

$\displaystyle a=k\cdot b+0$ for some $\displaystyle k>0$ . Now, without loss of generally, taking $\displaystyle a=k\cdot b$ and

substituting, we have:

$\displaystyle \gcd (a+b,ab)=\gcd (kb,(kb)b)=\gcd (kb,k{{b}^{2}})$

but this implies that

$\displaystyle kb=kb\cdot b+0$

$\displaystyle kb=k{{b}^{2}}+0$

or dividing both sides by b

$\displaystyle k=kb+0$

which implies that

$\displaystyle \gcd (k,b)=1$ and likewise argument if we go substituting $\displaystyle a=k\cdot b$ but this is just $\displaystyle \gcd (k,b)=\gcd (kb,k{{b}^{2}})=\gcd (kb,(kb)b)=\gcd (a+b,ab)=1$ and therefore, if $\displaystyle \gcd (a,b)=1$ , then $\displaystyle \gcd (a+b,ab)=1$ . QED

2.4 – 9. Prove that the greatest common divisor of two positive numbers a and b divides their least common multiple, especially that $\displaystyle \frac{lcm(a,b)}{\gcd (a,b)}$ .

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) $\displaystyle d|a$ and $\displaystyle d|b$
(b) if $\displaystyle c|a$ and $\displaystyle c|a$ , then $\displaystyle c\le d$

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

(a) $\displaystyle a|m$ and $\displaystyle b|m$
(b) If $\displaystyle a|c$ and $\displaystyle b|c$ , with $\displaystyle c>0$ , then $\displaystyle m\le c$

but $\displaystyle d|a$ and $\displaystyle a|m$ , therefore $\displaystyle d|m$ and $\displaystyle m\le c\le d$ because $\displaystyle c\le d$ and $\displaystyle m\le c$ . Again, we have that $\displaystyle d|b$ and $\displaystyle b|m$ , therefore $\displaystyle d|m$ and $\displaystyle m\le c\le d$ because $\displaystyle c\le d$ and $\displaystyle m\le c$ . Therefore, we see that the gcd does indeed divide the lcm, and we have established that

$\displaystyle \gcd (a,b)|lcm(a,b)$ .

QED

Inbetween Math and Poetry

Month: February 2012

Divisiblity and the GCD

Share this: