Mathematical Proofs

  1. Im doing a mathematical proof in my discrete class and i was wondering if you guys had any sort of interesting ideas for me to cover, the criteria is that it is beyond the grade 12 level. They must be either relevent or obscure. ANy ideas......?
  2. jcsd
  3. matt grime

    matt grime 9,396
    Science Advisor
    Homework Helper

    What do you mean you're 'doing a proof'? Surely all you do in discrete maths is prove things (or is that just my bias.... for instance: Grade 12 means what?)
  4. mathwonk

    mathwonk 9,666
    Science Advisor
    Homework Helper

    how about fermat's theorem that all primes of form 4k+1 are sums of 2 squares?

    Here is a sketch:

    Fermat’s Theorem on Sums of Two Squares
    The secret to understanding which integers are sums of two squares lies in introducing complex (“imaginary”) numbers. All numbers exist in our minds of course, hence are imaginary so we no longer use this old fashioned term for them, except informally or out of habit. Just as real numbers correspond to points on the line, complex numbers correspond to points on the plane, so just as it takes two real coordinates to describe a point in the plane, it takes two real numbers to describe a complex number. We define a complex number to be an ordered pair of real numbers (a,b). We add them by adding each coordinate separately, i.e. (a,b) + (c,d) = (a+c,b+d). The multiplication is more complicated, and we define (a,b)(c,d) = (ac-bd, ad+bc). In fact our new multiplication is commutative and has all the other properties you would expect of a multiplication (associative, and especially distributive).
    The definition can be made easier to remember as follows: notice that in our multiplication the complex number (1,0) is a multiplicative identity, since (1,0)(a,b) = (1a-0b, 1b+0a) = (a,b). Thus it is natural to call this number “1”, i.e. to set 1 = (1,0). On the other hand the complex number (0,1) has the interesting property that when you square it you get -1, i.e. (0,1)(0,1) = (0-1,0+0) = (-1,0) = -1. This is news, since we never had a number whose square was -1 before. If we denote this interesting complex number by “i”, i.e. if we set i = (0,1), then every complex number can be written in one and only one way as a linear combination of 1 and i as follows: (a,b) = (a,0) + (0,b) = a(1,0) + b(0,1) = a1 + bi = a+bi. From now on we drop the clunky notation of (a,b) for a complex number and use a+bi instead, where a and b are real numbers. Now the multiplication is easy to remember, because all you need to know is that i^2 = -1. I.e. now (a+bi)(c+di) = ac + adi + bic + bidi = ac +adi + bci + bdi^2 = ac +adi + bci -bd = (ac-bd) + i(ad+bc), and this is the same answer we got before for this multiplication, namely
    (ac-bd, ad+bc).
    We are interested only in complex numbers a+bi where a and b are both integers, and we call them “Gaussian integers”. They are the complex version of the integers. The useful property they have in relation to the problem of the sum of two squares is this: if n = a^2 + b^2, where n, a and b are natural numbers, then we can factor n as n = (a+bi)(a-bi) in the Gaussian integers. To see this, just use the old “difference of two squares” formula. I.e. now that -1 is a square, a sum of two squares behaves exactly like a difference of two squares, so we have = n = a^2 + b^2 = a^2 - b^2(-1) = a^2 - b^2i^2 = a^2 - (bi)^2 = (a+bi)(a-bi). Thus a number n like this which is a sum of two squares, even if it is prime in the usual integers, is no longer prime in the Gaussian integers.
    An example is 13, since 13 = 4+9 = 2^2 + 3^2 = (2+3i)(2-3i). Now notice that 13 is congruent to 1 mod 4. We have already proved that a number congruent to 3 mod 4 cannot be written as a sum of two squares. We claim that if n is a prime integer congruent to 1 mod 4, then n can be written as a sum of two squares.
    All we have to do is prove that n is not prime in the Gaussian integers, since then it can be factored as a product of two Gaussian integers, n = (a+bi)(c+di) and by taking absolute values, then n^2 = (a^2+b^2)(c^2+d^2). Since n is prime then n = a^2+b^2. Thus if n is a prime integer which can be factored in the Gaussian integers, we could write n as a sum of two squares. Thus writing a prime integer n as a sum of two squares is equivalent to factoring n in the Gaussian integers. So we want to show that a prime integer n of form 4m+1 is no longer prime (i.e. can be factored) in the Gaussian integers.
    Now look at the property of having a square root of -1. There is a square root of -1 in the Gaussian integers, namely i^2 = -1. But there is already a square root of -1 in some modular number systems Z/n too. For example, if n = 13, then 5^2 = 25 is congruent mod 13, to -1.
    In fact when n is an odd prime, then -1 has a square root mod n exactly when n is congruent to 1 mod 4. This is not hard to prove, since solving equations in a modular system like Z/n is relatively easy because there are only finitely many numbers to deal with. So if n is an odd prime of form 4K + 1, then -1 has a square root mod n, and we claim that then n is not prime in Z, which will prove it can be written as a sum of two squares.
    So let k be an integer such that k^2 is congruent to -1, mod n, and consider the Gaussian integers mod n, i.e. numbers of form a+bi where a and b are integers mod n. Then -1 has the two square roots k, i, so k^2 = -1 = i^2 , mod n, so 0 = k^2 - i^2 = (k-i)(k+i) = k^2+1, mod n. This means k^2+1 is divisible by n. But n does not divide either factor (k-i) or (k+i), since by definition of division in the Gaussian integers, n would have to divide both parts, k and i, and n does not divide i.
    Thus in the Gaussian integers we have found a product that n divides, while n does not divide either factor. Since prime numbers have the same “prime divisibility” property in the Gaussian integers as in the usual integers, this means that although n is a prime number in Z, n is not a prime in the Gaussian integers Z, i.e. although n does not factor non trivially using only ordinary integers, it does factor using complex or “Gaussian” integers, which is what we wanted to show.
    Summary: If a prime integer n has form n = 4m+1, then there is an integer k such that k^2 = -1, mod n, i.e. such that n divides k^2 - (-1) = k^2+1, in the usual integers, hence n divides k^2 + 1 also in the Gaussian integers. But in the Gaussian integers, k^2+1 = (k-i)(k+i), and n does not divide either factor, so n is not prime in the Gaussian integers, hence n = (a+bi)(c+di), so by taking absolute values of both sides and squaring, n^2 = (a^2 + b^2)(c^2+d^2), and since n is a prime integer, n = a^2+b^2. QED.
    Last edited: Mar 28, 2006
  5. yeah that might be a great topic to do but im having a lot of difficulty understanding it, im going to try and read it a few more times but i dont think i will get much more out of it, so any other ideas are welcome
  6. hey. im in the same class as tido611, and i am sort of stuck on ideas for this project too. i need a topic that is complex, but basic enough to understand and grasp, and still be able to convey and express in an academic manner. any ideas would be great for both of us i am sure.:smile:
  7. matt grime

    matt grime 9,396
    Science Advisor
    Homework Helper

    So it would be more accurate to say that you have an essay assigment in a discrete maths class that asks you to find a statement of some theorem, find its proof and explain its proof? That would make more sense than the first post. Pick a book, any book (n the subject), but I would recommend Proofs from The Book by Aigner and Ziegler.
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook
Similar discussions for: Mathematical Proofs