Beginning Modern Algebra Proofs

Date: 02/02/99 at 10:27:29
From: Micah McDaniel
Subject: Equality of sets, n^2 mod m

I'm trying to work my way through Seth Warner's Modern Algebra book, 
and I'm stuck on a few of the early problems. I've had differentiable 
calculus, vector spaces, most other things that a physics or 
engineering student would have to take.

Here are the problems:

1. Let (a,b) = { {a}, {a,b} }.
   Prove that if (a,b) = (c,d), then a = b and c = d.

   This is obvious to me, but how do I formally prove it?

2. Let Nm be the set of natural numbers < m. Prove that for any m>2,
   there exists k in Nm that is not a perfect square mod m. (i.e.
   k != j*j mod m for any j).

   I think I know why this is true. Since there are only m different
   j's to choose, if j*j mod m = i*i mod m for any i,j, then this is
   true. How can I make a formal proof of that, though?

Also, I found in your archives a proof that Sqrt(2) is irrational. That 
proof only works, though, for Sqrt(prime number). How can I prove that 
Sqrt(15) is irrational? that Sqrt(4) is not?

Obviously, proofs are a weak point for me, since I've never had to do 
them. If you have any suggestions for improving my proving skills, I'd 
love to hear it.

Thanks,

Micah

Date: 02/02/99 at 16:11:13
From: Doctor Rob
Subject: Re: Equality of sets, n^2 mod m

Thanks for writing to Ask Dr. Math!

We have a FAQ about proofs which might (or might not) help:

   http://mathforum.org/dr.math/faq/faq.proof.html   

In your problems, here are some ideas:

1. What is the union U of all the elements in (a,b)?  What is the
intersection I of all the elements in (a,b)?  What is U~I?

2. Notice that if m-1 >= i > m/2, then 1 <= m-i < m/2. Notice, too,
that (m-i)^2 = i^2 (mod m) for any i with 1 <= i <= m/2. Throw in zero, 
and that means that the squares fall into at most 1 + [m/2] congruence 
classes. Now there are m congruence classes altogether, so there are at 
least m - (1+[m/2]) = [m+1]/2 - 1 classes containing no squares, and 
this is positive as long as m >= 3.

3. Here is an alternate proof.

Suppose N > 1 is not a perfect square, and suppose that sqrt(N) = a/b 
for some positive integers a and b, and that b is the smallest positive 
integer denominator for which this is true. Then b^2 < N*b^2 = a^2, 
because N > 1, so 0 < b < a. Now divide a by b, obtaining quotient q 
and remainder r, so a = q*b + r, with 0 <= r < b. Now if r = 0, we have 
a = q*b, and a/b = q, so N = q^2, and N is a perfect square, a 
contradiction. This means that r
cannot be zero, and so 0 < r = a - q*b < b. Now

             N*b^2 = a^2
     N*b^2 - q*a*b = a^2 - q*a*b
       b*(N*b-q*a) = a*(a-q*b)
 (N*b-q*a)/(a-q*b) = a/b = sqrt(N)

This contradicts the minimality of b, since 0 < a - q*b < b. This
contradiction means that no such integers a and b can exist, and 
sqrt(N) is irrational.

Now all you have to do is show that your number, N = 15 or whatever, is 
not a perfect square, and you will know that sqrt(N) is irrational. If 
it is a perfect square N = q^2, then sqrt(N) = q is rational.

Here are two versions of the proof in the archives:

   Irrationality of Root 2
   http://mathforum.org/dr.math/problems/lord3.26.98.html   

   Proof that Sqrt(3) is Irrational
   http://mathforum.org/dr.math/problems/gardner8.14.97.html   

The proof in the archives is easily modified, by the way, to handle
composite N's. Just pick a prime number p that divides N to an odd 
power. If there is none, N is a perfect square, and you can write down 
its integer (and so rational) square root. If there is one, proceed as 
before to obtain a contradiction, that the power of p appearing on the 
left side of the equation N*b^2 = a^2 is odd and the power of p on the 
right side is even, contradicting unique factorization.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/