187 – An exploration | A kind of library

187 – An exploration

Problem 6 in the midterm asked to prove that if $n$ is an integer and $n^2$ is a multiple of $3$ , then $n$ is already a multiple of $3$ .

As we now know from lecture, the key seems to be that $3$ is a prime number. For example, it is not necessarily the case that if $n^2$ is a multiple of $4$ , then $n$ is a multiple of $4$ . For a counterexample, we can take $n=2$ .

The proof I was expecting was by contrapositive: If $n$ is not a multiple of $3$ , then it has a non-zero remainder when divided by $3$ , so $n=3k+1$ or $n=3k+2$ for some integer $k$ . This means that $n^2=9k^2+6k+1$ or $n^2=9k^2+12k+4$ . After some rearranging, we see that in both cases we have $n^2=3t+1$ for some integer $t$ , but then $n^2$ is not a multiple of $3$ after all.

Using Euclid’s lemma, we can give another proof that is particularly short: Since $3$ is a prime, then whenever $3$ divides a product, it divides one of the factors. We are told that $3$ divides $n^2=n\cdot n$ , so it divides $n$ or it divides $n$ . On the other hand, this brevity is only apparent, as the proof uses Euclid’s lemma, which makes use of the Euclidean algorithm and the possibility of writing the GCD of two numbers as a linear combination of them. When written in full detail, this argument ends up being longer than the one we gave first.

A different approach was suggested during lecture, and I think it leads to a nice argument, so I am presenting it here.

The idea was simple: Suppose that $n^2$ is a multiple of $3$ . Then there is an integer $k$ such that $n^2=3k$ , so we can write

$\displaystyle n=3\left(\frac kn\right).$

If (and it is a big if) we manage to show that $n|k$ , then we see that $\displaystyle \frac kn$ is an integer, and the displayed equation above tells us that $n$ is $3$ times an integer, so it is a multiple of $3$ .

Let’s see if we can make this idea work. We simply divide $k$ by $n$ and see what we are left with:

$k= nq+r$

for some integer $q$ and some remainder $r$ with $0\le r<n$ . If $r=0$ , we are done: $k$ is indeed a multiple of $n$ . Let’s examine what happens otherwise.

We have then that $0<r<n$ and

$\displaystyle n=3\left(\frac kn\right)=3\left(\frac{nq+r}n\right)=3\left(q+\frac rn\right)=3q+3\frac rn.$

This means that $\displaystyle n-3q=\frac{3r}n$ is an integer, so $n|3r$ . But $0<r<n$ , so $0<3r<3n$ . Since ${}3r$ is a multiple of $n$ , the only possibilities are that $3r=n$ or $3r=2n$ .

In the first case, we have that $n=3r$ , so $n$ is a multiple of $3$ after all.

In the second case, we have $3r=2n$ . We can proceed in two ways now: A short argument goes by noticing that $3r=2n=3n-n$ , so

$n=3n-3r=3(n-r)$ ,

and $n$ is again a multiple of $3$ . We have now proved that, no matter what the remainder $r$ is when we divide $k$ by $n$ , in any case we have that $n$ is a multiple of $3$ , and this is what we needed.

A slightly longer argument but perhaps less of a trick goes by noticing that if $3r=2n$ , then ${}3r$ is even. One easily verifies that if $r$ is odd, then ${}3r$ is also odd, so it must be the case that $r$ itself is even. Say, $r=2s$ . Then $2n=3r=3(2s)=2(3s)$ , or

$n=3s,$

so $n$ is indeed a multiple of $3$ , and we are done as before.

Where do we go from here?

We are done with the argument, but it is worth continuing a bit further: We have that $n$ is a multiple of $3$ , say $n=3a$ . Then $n^2=9a^2=3(3a^2)$ , so the number we were calling $k$ before, is $k=3a^2=(3a)a=na$ , that is, $k$ is after all a multiple of $n$ , and $\displaystyle \frac kn$ is an integer. As it turned out, we ended up not needing this in our proof, but now we now it is true anyway.

Where does this argument fail when we use a number like $4$ instead of $3$ ? Exactly the same argument would give us: If $n^2=4k$ , then $n=4(k/n)$ . We can divide $k$ by $n$ , and we get $k=nq+r$ , so $k/n=q+(r/n)$ and $n=4q+4(r/n)$ . It follows that $n|4r$ . As before, $0\le r<n$ , so $0\le 4r<4n$ , so $4r=0,n,2n,$ or $3n$ . If $4r=0$ , then $n=4q$ is a multiple of $4$ . If $4r=n$ or $4r=3n=4n-n$ , then $n$ is again a multiple of $4$ . However, if $4r=2n$ , then $2r=n$ , and all we can conclude is that $n$ is even.

This suggests a natural question: Let $m$ be a positive integer. Consider the following statement, that we will call $R(m)$ :

Whenever $n^2$ is a multiple of $m$ , then in fact $n$ is a multiple of $m$ .

In the paragraph above, we saw that $R(4)$ is false, and before we saw that $R(3)$ is true.

Question. For which values of $m$ is $R(m)$ true?

It is true for $m$ prime (do you see why?), but this is not necessary; for example, it is true for $m=6$ . If you find the general solution, let me know and you can turn it in as extra credit.

This entry was posted on Monday, November 7th, 2011 at 5:27 pm and is filed under 187: Discrete mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

	ปั่นสล็อต on 414/514 The theorems of Rieman…
	Richard Kimberly Hec… on Woodin’s proof of the se…
	Is there a Borel-mea… on 414/514 Examples of Baire clas…
	Simple bijectiveness… on 580 -Some choiceless results…
	Schur’s theore… on 580 -III. Partition calcu…
	Uncountable linearly… on 403/503 – Homework …
	What is a non-constr… on On strong measure zero se…
	function from Nmathb… on Hindsight
	Cauchy Schwarz Inequ… on 275 -Positive polynomials
	What is a Cantor-sty… on 580 -Some choiceless results…
	Question about Gener… on 580 -Some choiceless results…
	Set has Measure Zero… on On strong measure zero se…
	Non-measurable subse… on 580 -Cardinal arithmetic …
	hmeng1 on 414/514 The theorems of Rieman…
	580 -Cardinal arithm… on 580 -Cardinal arithmetic …

M	T	W	T	F	S	S
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30

A kind of library