Associated Topics || Dr. Math Home || Search Dr. Math

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
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/
```
Associated Topics:
College Modern Algebra

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search