Mathematical Proofs: Ideas Beyond Grade 12

In summary, the mathematician is doing a proof in his discrete class and was wondering if anyone had any ideas for him to cover. Some ideas he mentioned were Fermat's Theorem on sums of two squares, that all primes of form 4k+1 are sums of 2 squares, and the complex number i which is a multiplicative identity and has the interesting property that when you square it you get -1.
  • #1
Tido611
79
0
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 relevant or obscure. ANy ideas...?
 
Physics news on Phys.org
  • #2
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?)
 
  • #3
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:
  • #4
yeah that might be a great topic to do but I am having a lot of difficulty understanding it, I am going to try and read it a few more times but i don't think i will get much more out of it, so any other ideas are welcome
 
  • #5
hey. I am 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:
 
  • #6
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.
 

1. What is a mathematical proof?

A mathematical proof is a logical argument that shows that a statement or theorem is true based on previously accepted facts and rules. It is a way to demonstrate the validity of a mathematical statement.

2. Why are mathematical proofs important?

Mathematical proofs are important because they provide a rigorous and systematic way to verify the truth of mathematical statements. They help to establish the validity of mathematical theories and allow for the development of new ideas and concepts.

3. What are some common techniques used in mathematical proofs?

Some common techniques used in mathematical proofs include mathematical induction, proof by contradiction, direct proof, and proof by contrapositive. Other techniques include using counterexamples, proofs by exhaustion, and proof by construction.

4. How do you approach a proof?

When approaching a proof, it is important to carefully read and understand the statement or theorem to be proven. Then, you can break down the statement into smaller parts and look for connections to previously proven theorems. You can also consider different approaches and techniques to see which one is most suitable for the given problem.

5. Are there any tips for writing a clear and concise proof?

Yes, some tips for writing a clear and concise proof include being organized and logical in your approach, using precise and concise language, providing clear and detailed explanations for each step, and using diagrams or illustrations if necessary. It is also important to check your work for any errors or gaps in logic before presenting your proof.

Similar threads

  • Science and Math Textbooks
Replies
6
Views
922
  • Science and Math Textbooks
Replies
4
Views
3K
Replies
2
Views
587
Replies
8
Views
303
  • Beyond the Standard Models
Replies
12
Views
845
Replies
4
Views
789
Replies
2
Views
870
  • STEM Educators and Teaching
4
Replies
107
Views
4K
  • STEM Academic Advising
Replies
6
Views
2K
  • Science and Math Textbooks
Replies
4
Views
989
Back
Top