Beginning Modern Algebra ProofsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/