below the fold... this is to help with the Final Exam preparation.
15 December 2016
13 December 2016
Instructions for Project 2 (Frieze patterns and other)
Due: Tuesday 20 December at start of exam
-
Find real-life examples of frieze patterns. Photograph or sketch them and write down where you found
them. Find at least one example of each of at least 4 of the 7 different types of frieze patterns.
-
For each frieze pattern you found, give its type according to the classification scheme we used in class.
(F1, F2, F3, F4, F5, F6, F7)
-
Also look for tessellations by regular polygons other than squares. Photograph or sketch them and give
the locations where they were found. You should be able to find at least one of these. Extra credit if
you find more than one.
-
Also look for semiregular tessellations for extra credit. Photograph or sketch and give the locations
where they were found. Then give the name of each of the semiregular tessellations according to the
naming convention used in class.
You may use pictures found in books or on the web for examples of frieze patterns (not for the others), but you must provide the URL (web address) where the image was found. You may not use any image from a website or other source which already tells you what type of frieze pattern it is. Use of images from the web or from another source without giving information about the source is plagiarism.
How to submit:
Email would be the best, as I am unable to carry a lot of papers (and I'll have to carry the exam papers). You can make a document in any word processing program and insert the pictures, write whatever you have to write, and save it as a rtf or pdf (PLEASE only those formats!)
Name your document in the form
LastnameFirstnameMath1311FriezePatterns.pdf or .rtf if it's in that format.
Submit by posting a private note on Piazza or (preferably) attaching to an email to profshaver at gmail.com
07 December 2016
Scheduling and Final Exam information (with Exam room information!)
Test 4 is shorter than the previous three tests. I would like to take about 20 minutes at the start of class on Thursday to tie up any loose ends from tilings and frieze patterns. (It may not take this long.) So please make sure to at least take a look at them as well as studying for Test 4!
Remember that Monday 12 December is the last day of classes for the Fall 2016 semester. Tuesday 13 December is scheduled as a reading day: however, as mentioned earlier in the semester, we will meet (at our usual time and place) to review for the Final Exam on that day.
The Final Exam for all day sections of Math 1311 is scheduled for Tuesday 20 December at 10:30 AM - 12:30 PM.
The room will NOT be our usual classroom. Our exam meets in 1127 Ingersoll. There will be another section of Math 1311 having its exam in the same room, so don't be surprised to see people you don't recognize there.
Final Exam Review: you should go back to the review materials for the four tests, and your test papers. There are additional problems, on material that is not on the 4 tests, here. [Note: this is an edited version with the numbering corrected.]
Please bring your specific questions that you want to discuss on Tuesday the 13th! That way we can make sure to focus on what you need, rather than just meandering. (Not that there's anything wrong with meandering.)
Remember that Monday 12 December is the last day of classes for the Fall 2016 semester. Tuesday 13 December is scheduled as a reading day: however, as mentioned earlier in the semester, we will meet (at our usual time and place) to review for the Final Exam on that day.
The Final Exam for all day sections of Math 1311 is scheduled for Tuesday 20 December at 10:30 AM - 12:30 PM.
The room will NOT be our usual classroom. Our exam meets in 1127 Ingersoll. There will be another section of Math 1311 having its exam in the same room, so don't be surprised to see people you don't recognize there.
Final Exam Review: you should go back to the review materials for the four tests, and your test papers. There are additional problems, on material that is not on the 4 tests, here. [Note: this is an edited version with the numbering corrected.]
Please bring your specific questions that you want to discuss on Tuesday the 13th! That way we can make sure to focus on what you need, rather than just meandering. (Not that there's anything wrong with meandering.)
06 December 2016
Tuesday 6 December class
Topics:
• Return to regular tilings of the plane:
From last time Regular polygons and their exterior and interior angles.
and Tiling the plane with regular polygons: we show that there are only three regular tilings of the plane: by equilateral triangles, by squares, and by regular hexagons.
But we can exploit these to make beautiful patterns. (Something you may want to investigate for yourself.)
Here's another way these regular tilings are used. Surprising!
• Semiregular tilings (tessellations) of the plane;
here is another source (from Math Forum)
A semiregular tiling is a tiling by some combination of different regular polygons (not just one type). It must fulfill two rules:
1) The arrangement of the types of polygons must be the same at every vertex - we say that each vertex is of the same type
- and -
2) The sum of the angles of the polygons that meet at that vertex must be 360 degrees (obviously).
It turns out that there are only 8 semiregular tilings. They are named by listing the numbers of sides of the polygons going around each vertex, starting with a polygon with the least number of sides: I usually (in this class) use letter names instead of numbers, but it's not terribly important which way you do it. So instead of writing 3,3,3,4,4 I would write TTTSS (for triangle, triangle, triangle, square, square) for example. Choose whichever makes sense to you.
• Frieze patterns: (that link gives the webpage I handed out in class) - these are related to tilings, but they are tiling in only one direction, so to speak. A basic pattern, or "block" as I call it, is repeated by translation to the left and right. (In principle, the block is repeated infinitely many times: in reality, it is repeated until the end of the wall or whatever.)
We will use the naming convention in the above-linked MAA article: be aware that other sources will use different names for these patterns. It turns out that there are only 7 different frieze patterns based on the symmetries of the individual blocks. (Remember that all frieze patterns have translational symmetry.)
Assuming that the translational symmetry is in the horizontal direction (as it usually is), the symmetries that the block may have are:
vertical reflection (reflection over a vertical line through the middle of the block)
horizontal reflection (reflection over a horizontal line through the middle of the block)
rotation by 180° around a point at the center of the block
glide reflection ("gliding" in the horizontal direction by half a "block" and then horizontal reflection - this requires looking at the whole frieze pattern, not just the individual block, and it is probably the hardest to see at times.)
The block may, of course, have none of these. Please also note that if the frieze pattern has both horizontal and vertical reflection, then it will automatically have rotation, but the converse is not true. (For example, the Greek Key pattern has rotation but has neither horizontal nor vertical reflection.)
We looked at some of the examples here (EscherMath) to classify them according to our naming convention. Please note that this second site is using a different naming convention: please stay with the names and the F-numbers given in the handout. If you read that whole page, you will see another good explanation of the symmetries in the 7 frieze patterns: can you identify which of our names should be given to each pattern?
Homework:
• As I mentioned, your Project 2 will be to collect real-life (NOT Googled) examples of regular and semiregular tilings, and frieze patterns. Try to find an example of each of the 3 regular tilings, at least 2 of the semiregular tilings, and at least 4 of the frieze patterns. (Some semiregular tilings and frieze patterns are rather rare!) You can and should start doing this now.
Document them by taking nice (i.e. focused and framed) photos or else making a nice sketch, and make a note of the place where you found each one. In addition, identify which tiling or frieze pattern it represents.
Extra credit will be given if you find more than the above specified minimum number of different patterns.
Sources may be patterns you find in the world (on walls or walkways or fences, fabrics, etc.) or in craft patterns (knitting, crochet, embroidery, etc.) - the point is NOT to use a web search to search for "frieze patterns" for example. We want to see how these appear in our everyday (offline) lives.
This Project will be due on the day of the Final Exam. I will provide more detailed instructions on how to submit it in a separate post.
• Look at these three patterns from the MathForum article on tilings (tessellations): they look as if they should be able to be continued into semiregular tessellations. What goes wrong if you try to do that? Describe in your own words (but be specific!) It may help if you make 2 copies of each image into a program that can manipulate images (I did this in TextEdit on a Mac) and then try to move one of the images around to fit it together with the other one. Big hint: remember that each vertex in the tiling must have the same type! Is it possible to make this happen?
• Return to regular tilings of the plane:
"regular" in this case meant "with caffeine"
From last time Regular polygons and their exterior and interior angles.
and Tiling the plane with regular polygons: we show that there are only three regular tilings of the plane: by equilateral triangles, by squares, and by regular hexagons.
But we can exploit these to make beautiful patterns. (Something you may want to investigate for yourself.)
Here's another way these regular tilings are used. Surprising!
• Semiregular tilings (tessellations) of the plane;
here is another source (from Math Forum)
A semiregular tiling is a tiling by some combination of different regular polygons (not just one type). It must fulfill two rules:
1) The arrangement of the types of polygons must be the same at every vertex - we say that each vertex is of the same type
- and -
2) The sum of the angles of the polygons that meet at that vertex must be 360 degrees (obviously).
It turns out that there are only 8 semiregular tilings. They are named by listing the numbers of sides of the polygons going around each vertex, starting with a polygon with the least number of sides: I usually (in this class) use letter names instead of numbers, but it's not terribly important which way you do it. So instead of writing 3,3,3,4,4 I would write TTTSS (for triangle, triangle, triangle, square, square) for example. Choose whichever makes sense to you.
• Frieze patterns: (that link gives the webpage I handed out in class) - these are related to tilings, but they are tiling in only one direction, so to speak. A basic pattern, or "block" as I call it, is repeated by translation to the left and right. (In principle, the block is repeated infinitely many times: in reality, it is repeated until the end of the wall or whatever.)
We will use the naming convention in the above-linked MAA article: be aware that other sources will use different names for these patterns. It turns out that there are only 7 different frieze patterns based on the symmetries of the individual blocks. (Remember that all frieze patterns have translational symmetry.)
Assuming that the translational symmetry is in the horizontal direction (as it usually is), the symmetries that the block may have are:
vertical reflection (reflection over a vertical line through the middle of the block)
horizontal reflection (reflection over a horizontal line through the middle of the block)
rotation by 180° around a point at the center of the block
glide reflection ("gliding" in the horizontal direction by half a "block" and then horizontal reflection - this requires looking at the whole frieze pattern, not just the individual block, and it is probably the hardest to see at times.)
The block may, of course, have none of these. Please also note that if the frieze pattern has both horizontal and vertical reflection, then it will automatically have rotation, but the converse is not true. (For example, the Greek Key pattern has rotation but has neither horizontal nor vertical reflection.)
We looked at some of the examples here (EscherMath) to classify them according to our naming convention. Please note that this second site is using a different naming convention: please stay with the names and the F-numbers given in the handout. If you read that whole page, you will see another good explanation of the symmetries in the 7 frieze patterns: can you identify which of our names should be given to each pattern?
Homework:
• As I mentioned, your Project 2 will be to collect real-life (NOT Googled) examples of regular and semiregular tilings, and frieze patterns. Try to find an example of each of the 3 regular tilings, at least 2 of the semiregular tilings, and at least 4 of the frieze patterns. (Some semiregular tilings and frieze patterns are rather rare!) You can and should start doing this now.
Document them by taking nice (i.e. focused and framed) photos or else making a nice sketch, and make a note of the place where you found each one. In addition, identify which tiling or frieze pattern it represents.
Extra credit will be given if you find more than the above specified minimum number of different patterns.
Sources may be patterns you find in the world (on walls or walkways or fences, fabrics, etc.) or in craft patterns (knitting, crochet, embroidery, etc.) - the point is NOT to use a web search to search for "frieze patterns" for example. We want to see how these appear in our everyday (offline) lives.
This Project will be due on the day of the Final Exam. I will provide more detailed instructions on how to submit it in a separate post.
• Look at these three patterns from the MathForum article on tilings (tessellations): they look as if they should be able to be continued into semiregular tessellations. What goes wrong if you try to do that? Describe in your own words (but be specific!) It may help if you make 2 copies of each image into a program that can manipulate images (I did this in TextEdit on a Mac) and then try to move one of the images around to fit it together with the other one. Big hint: remember that each vertex in the tiling must have the same type! Is it possible to make this happen?
• In the EscherMath discussion of the frieze patterns, go to the heading "The Seven Frieze Patterns" (or here is a pdf of them) and identify each of those frieze patterns according to our naming convention (given here).
• In the Frieze Exercises from EscherMath, do problems #1, 2, 3, 4, and 9a: use our naming convention, again. I'll be posting answers to these later, or you could do them on Piazza for extra credit!
tiling and frieze links
Tiling the plane with regular polygons (Regular tilings)
There are only three regular tilings of the plane: by equilateral triangles, by squares, and by regular hexagons. But we can exploit these to make beautiful patterns.
Here's another way these regular tilings are used. Surprising!
Semiregular tilings (tessellations) of the plane; here is another source (from Math Forum)
Frieze patterns: Conway's naming convention
translation symmetry
More here (EscherMath)
Exercises attached to EscherMath
There are only three regular tilings of the plane: by equilateral triangles, by squares, and by regular hexagons. But we can exploit these to make beautiful patterns.
Here's another way these regular tilings are used. Surprising!
Semiregular tilings (tessellations) of the plane; here is another source (from Math Forum)
Frieze patterns: Conway's naming convention
translation symmetry
More here (EscherMath)
Exercises attached to EscherMath
04 December 2016
Test 4 review (updated now with answers/links)
Test 4 is scheduled for Thursday 8 December.
The review problems are here.
Answers /links are below the fold...
The review problems are here.
Answers /links are below the fold...
02 December 2016
Extra Credit you may want to work on (Updated)
below the fold are some possibilities, most of which I have mentioned in class already.
01 December 2016
Thursday 1 December class (updated)
Topics:
• Checking that the angles add up correctly in the "algebraic" proof of the Pythagorean Theorem from Math is Fun.
Clearly the sides of the interior square match up with the hypotenuse of the right triangle - that is how we constructed the square. The only question is whether the angles add up correctly where the corners of that square touch the sides of the big square - we are asking if the sides of the big square are really straight lines, as they appear to be.
Regular polygons and their exterior and interior angles.
Tiling the plane with regular polygons (Regular tilings; we will discuss semi-regular tilings next time)
Homework:
Find the measures of the exterior and interior angles for the following regular polygons:
1) the regular nonagon (9 sides)
2) the regular dodecagon (12 sides)
.
• Checking that the angles add up correctly in the "algebraic" proof of the Pythagorean Theorem from Math is Fun.
Clearly the sides of the interior square match up with the hypotenuse of the right triangle - that is how we constructed the square. The only question is whether the angles add up correctly where the corners of that square touch the sides of the big square - we are asking if the sides of the big square are really straight lines, as they appear to be.
We can check this by using two facts:
1) In any right triangle, the other two angles add up to 90 degrees (they are complimentary).
2) The three angles that meet at the corner of the interior square consist of a right angle (from the square), and the two other non-right angles from the right triangle. They are labeled A and B in the picture below (look at the top edge of the big square).
So the total of those three angles is 90 degrees plus angle A plus angle B, which is 9- degrees plus 90 degrees = 180 degrees, a straight line, as it appears to be. So all is well, the big square really is a square and we can compute its area by squaring the length of its side.
• Polygons, regular polygons, and introduction to regular tilings (tessellations) of the plane.
Polygons (that link also gives the names of many of the polygons)Regular polygons and their exterior and interior angles.
Tiling the plane with regular polygons (Regular tilings; we will discuss semi-regular tilings next time)
Homework:
Find the measures of the exterior and interior angles for the following regular polygons:
1) the regular nonagon (9 sides)
2) the regular dodecagon (12 sides)
.
29 November 2016
Tuesday 22 November and Tuesday 29 November classes
Activities: Area paradoxes
Area paradox Math Less Traveled
Area paradox triangle problem: here is another link with hints and discussion
Both of these have connections to Fibonacci numbers: that is not an accident.
Topics:
• Proving that the power set of a set S is always strictly larger in size (cardinality) than the original set S, even when S is an infinite set. This is usually called Cantor's Theorem.
We do not exactly do the proof, but rather we indicate how the proof is done. The problem is that the set we start with may be uncountable, so we cannot assume that we can list its elements. If you are interested to see how an actual proof appears, here is a fairly accessible one (The proof is at the end of the article: but be warned that they use some notation and terms that may be new to you!)
The Wikipedia article on Cantor's Theorem contains a description of how the proof would work if the original set is countable (listable), specifically if the original set is the set of natural numbers. In order to make the proof more general, you should notice that it does not depend on being able to list all of the elements of the one-to-one correspondence: that is only done for convenience (in order to be very concrete). The center of the proof is the rule we use for deciding whether or not each element of the original set should be included in the new set we construct, and that rule can be used whether or not we can list all of the elements of the original set. We just have to give up the idea that we can think of using the rule one-by-one on the elements, and think of using it on all of them "at the same time" so to speak.
I have written up rough notes on the proof as I described it in class which are available here. They are unedited, so please let me know if you find anything that looks wrong or any typographical or other errors!
Next we returned to looking at the sizes of power sets. We already found the following result: For a finite set S, if |S| = n, then the size of the power set of S will be 2n. This is why it is called the power set!
The same thing holds if S is an infinite set, except that then the numbers we get are not real numbers. But there is a way to interpret what 2n means even if n is an infinite numbers, and the point is, we have proved that 2n (the cardinality of the power set) is larger than n (the cardinality of the original set) even when n is an infinite number.
Recall that the cardinality of the set of natural numbers (or of any countable set) is denoted by א0 (aleph-naught or aleph-null) : The power set of the set of natural numbers is the set of real numbers (actually, we should say that the power set of the natural numbers can be put in one-to-one correspondence with the real numbers), so the cardinality of the set of real numbers is 2א0.
The Continuum Hypothesis is the statement that there is no cardinality that is between א0 and 2א0, so 2א0 would be the "next in line" in the infinite cardinalities. It is now known that this statement cannot be proved either true or false in the mathematical system we use. (A somewhat accessible article explaining this, by Juliette Kennedy, is available from the Institute for Advanced Study.Warning: it's long, because it gives some history of the problem and also explains some of the concepts and ideas involved.)
However, with or without the Continuum Hypothesis, we can show that there are in fact an infinite number of "sizes of infinity"! How to do this: we can take the power set of a set S, and form the power set of the power set:
So if |S|=3, we know that |P(S)| = 23 = 8
Form the power set of the power set: its size is |P(P(S))| = 28 = 256
Form the power set of the power set of the power set: its size is |P(P(P(S)))| = 2256 = a really big number! (It has 78 digits)
And we can continue this process indefinitely. This gives us a "tower of powers" where each successive number is 2 to the power of the last one.
The same thing can be done starting with an infinite set, the set of natural numbers. Then we get an infinite "tower of powers" with each one being an infinite cardinality which is strictly larger than the one that came before it. So there are (at least!) countably many sizes of infinity.
Next topic: Stating and proving the Pythagorean Theorem
Note: what we will do through the remainder of the course will be more geometrical, to take a break from the analytical stuff we have done so far. It will still be "Thinking Mathematically", but in a little different way.
For the statement of the Pythagorean Theorem, see the post from Math is Fun, and also the Regent's Prep post
Cut-the-Knot has a list of 118 different proofs of this theorem. Why prove a theorem more than one way? Because every proof sheds a little different light on the theorem. This theorem is so important (maybe the most important theorem in mathematics!) that we keep coming back and looking at it again from different points of view.
The proof we will examine is this one, called "algebraic" by Math is Fun, although it is also geometric.
Next time: We will look more carefully at the picture in that proof, and make sure that all the angles add up as they should! (Being careful after being warned by those area paradoxes.) We will also look at the two proofs given in the original Math is Fun article about the Pythagorean Theorem.(They are near the bottom of the page.)
Homework:
• Go to this Math is Fun article about power sets, and find the Questions at the bottom of the page. Do Questions 1-8 (you can skip #9 and #10). While you do them, record in your journal what work you did to answer the question, what answer you got, was it right or wrong, and what you learned.
• Make sure that you understand how the proof of Cantor's Theorem works, and also how we know that there are an infinite number of sizes of infinity - in other words, an infinite number of infinite cardinalities.
• Read the two links above to Math is Fun on the Pythagorean Theorem and on the proof of the Pythagorean Theorem, looking specifically at the proofs so you are prepared to examine them closely next time.
Area paradox Math Less Traveled
Area paradox triangle problem: here is another link with hints and discussion
Both of these have connections to Fibonacci numbers: that is not an accident.
Topics:
• Proving that the power set of a set S is always strictly larger in size (cardinality) than the original set S, even when S is an infinite set. This is usually called Cantor's Theorem.
We do not exactly do the proof, but rather we indicate how the proof is done. The problem is that the set we start with may be uncountable, so we cannot assume that we can list its elements. If you are interested to see how an actual proof appears, here is a fairly accessible one (The proof is at the end of the article: but be warned that they use some notation and terms that may be new to you!)
The Wikipedia article on Cantor's Theorem contains a description of how the proof would work if the original set is countable (listable), specifically if the original set is the set of natural numbers. In order to make the proof more general, you should notice that it does not depend on being able to list all of the elements of the one-to-one correspondence: that is only done for convenience (in order to be very concrete). The center of the proof is the rule we use for deciding whether or not each element of the original set should be included in the new set we construct, and that rule can be used whether or not we can list all of the elements of the original set. We just have to give up the idea that we can think of using the rule one-by-one on the elements, and think of using it on all of them "at the same time" so to speak.
I have written up rough notes on the proof as I described it in class which are available here. They are unedited, so please let me know if you find anything that looks wrong or any typographical or other errors!
Next we returned to looking at the sizes of power sets. We already found the following result: For a finite set S, if |S| = n, then the size of the power set of S will be 2n. This is why it is called the power set!
The same thing holds if S is an infinite set, except that then the numbers we get are not real numbers. But there is a way to interpret what 2n means even if n is an infinite numbers, and the point is, we have proved that 2n (the cardinality of the power set) is larger than n (the cardinality of the original set) even when n is an infinite number.
Recall that the cardinality of the set of natural numbers (or of any countable set) is denoted by א0 (aleph-naught or aleph-null) : The power set of the set of natural numbers is the set of real numbers (actually, we should say that the power set of the natural numbers can be put in one-to-one correspondence with the real numbers), so the cardinality of the set of real numbers is 2א0.
The Continuum Hypothesis is the statement that there is no cardinality that is between א0 and 2א0, so 2א0 would be the "next in line" in the infinite cardinalities. It is now known that this statement cannot be proved either true or false in the mathematical system we use. (A somewhat accessible article explaining this, by Juliette Kennedy, is available from the Institute for Advanced Study.Warning: it's long, because it gives some history of the problem and also explains some of the concepts and ideas involved.)
However, with or without the Continuum Hypothesis, we can show that there are in fact an infinite number of "sizes of infinity"! How to do this: we can take the power set of a set S, and form the power set of the power set:
So if |S|=3, we know that |P(S)| = 23 = 8
Form the power set of the power set: its size is |P(P(S))| = 28 = 256
Form the power set of the power set of the power set: its size is |P(P(P(S)))| = 2256 = a really big number! (It has 78 digits)
And we can continue this process indefinitely. This gives us a "tower of powers" where each successive number is 2 to the power of the last one.
The same thing can be done starting with an infinite set, the set of natural numbers. Then we get an infinite "tower of powers" with each one being an infinite cardinality which is strictly larger than the one that came before it. So there are (at least!) countably many sizes of infinity.
Next topic: Stating and proving the Pythagorean Theorem
Note: what we will do through the remainder of the course will be more geometrical, to take a break from the analytical stuff we have done so far. It will still be "Thinking Mathematically", but in a little different way.
For the statement of the Pythagorean Theorem, see the post from Math is Fun, and also the Regent's Prep post
Cut-the-Knot has a list of 118 different proofs of this theorem. Why prove a theorem more than one way? Because every proof sheds a little different light on the theorem. This theorem is so important (maybe the most important theorem in mathematics!) that we keep coming back and looking at it again from different points of view.
The proof we will examine is this one, called "algebraic" by Math is Fun, although it is also geometric.
Next time: We will look more carefully at the picture in that proof, and make sure that all the angles add up as they should! (Being careful after being warned by those area paradoxes.) We will also look at the two proofs given in the original Math is Fun article about the Pythagorean Theorem.(They are near the bottom of the page.)
Homework:
• Go to this Math is Fun article about power sets, and find the Questions at the bottom of the page. Do Questions 1-8 (you can skip #9 and #10). While you do them, record in your journal what work you did to answer the question, what answer you got, was it right or wrong, and what you learned.
• Make sure that you understand how the proof of Cantor's Theorem works, and also how we know that there are an infinite number of sizes of infinity - in other words, an infinite number of infinite cardinalities.
• Read the two links above to Math is Fun on the Pythagorean Theorem and on the proof of the Pythagorean Theorem, looking specifically at the proofs so you are prepared to examine them closely next time.
17 November 2016
Thursday 17 November class
Topics:
• Some set notation that we need
See the Set post from Math is Fun
Also: cardinality of a set
The cardinality of a set A is the size of that set: we use the notation |A| for the cardinality of the set A.
For a finite set A, the cardinality is just the number of elements in A:
if A has n elements, then |A|=n.
For an infinite set, we have to define different cardinalities, according to which sets are in one-to-one correspondence with each other.
We define the cardinality of the set of natural numbers (or any countable set) to be aleph-null (or aleph-nought), designated by the symbol ℵ0 - this kind of infinite size number is called a transfinite number).
• Power sets
See the Power Set post from Math is Fun, and also in Wikipedia: the power set of A is the set whose elements are all the subsets of A.
The important thing we need from Power Sets is that the power set of a set A has size greater than the size of A: If |A|=n, then the power set of A has 2n elements. We prove that by making a one-to-one correspondence between the elements of the power set and the binary numbers with n digits: we then need to know that there are exactly 2n binary numbers with n digits.
So in fact, the size of the power set is exponentially greater than the size of A.
This will continue to be true even for infinite sets, as we will discuss more next time.
Homework:
• Make sure that you review the notation for sets and cardinalities of sets given and linked above.
• Problems:
1) Write down all of the 4-digit binary numbers in a list (as is done in the Power Set post from Math is Fun, under "It's Binary!", for 3-digit numbers)
2) For the set {red, yellow, green, blue}, give the power set by listing the subset that corresponds to each binary number in the list from problem #1. How many elements does the power set have?
For next time: We'll look at power sets of infinite sets, how we can prove that the power set of an infinite set has larger cardinality than the original set, and how to show that there is an infinite number of sizes of infinity!
Preliminary Reading: Ask Dr. Math on finding the power set of a power set
P.S. no journals due yet: you'll submit them Tuesday, since there is no class on Thursday next week!
• Some set notation that we need
See the Set post from Math is Fun
Also: cardinality of a set
The cardinality of a set A is the size of that set: we use the notation |A| for the cardinality of the set A.
For a finite set A, the cardinality is just the number of elements in A:
if A has n elements, then |A|=n.
For an infinite set, we have to define different cardinalities, according to which sets are in one-to-one correspondence with each other.
We define the cardinality of the set of natural numbers (or any countable set) to be aleph-null (or aleph-nought), designated by the symbol ℵ0 - this kind of infinite size number is called a transfinite number).
• Power sets
See the Power Set post from Math is Fun, and also in Wikipedia: the power set of A is the set whose elements are all the subsets of A.
The important thing we need from Power Sets is that the power set of a set A has size greater than the size of A: If |A|=n, then the power set of A has 2n elements. We prove that by making a one-to-one correspondence between the elements of the power set and the binary numbers with n digits: we then need to know that there are exactly 2n binary numbers with n digits.
So in fact, the size of the power set is exponentially greater than the size of A.
This will continue to be true even for infinite sets, as we will discuss more next time.
Homework:
• Make sure that you review the notation for sets and cardinalities of sets given and linked above.
• Problems:
1) Write down all of the 4-digit binary numbers in a list (as is done in the Power Set post from Math is Fun, under "It's Binary!", for 3-digit numbers)
2) For the set {red, yellow, green, blue}, give the power set by listing the subset that corresponds to each binary number in the list from problem #1. How many elements does the power set have?
For next time: We'll look at power sets of infinite sets, how we can prove that the power set of an infinite set has larger cardinality than the original set, and how to show that there is an infinite number of sizes of infinity!
Preliminary Reading: Ask Dr. Math on finding the power set of a power set
P.S. no journals due yet: you'll submit them Tuesday, since there is no class on Thursday next week!
10 November 2016
Thursday 10 November class
• Activity: "Dodge Ball" from The Heart of Mathematics
Topics: How to count/measure infinite sets!
First we have to examine closely what we do when we count a finite set. Essentially we are making what is called a one-to-one correspondence between the first however-many counting numbers (the natural numbers) and the items that we are counting.
The idea of one-to-one correspondence is what will carry over into infinite sets.
• David Hilbert's Hotel, and some theorems about the sizes of some infinite sets: See the Science4All article. (Warning: it contains math notation that may not display correctly on a phone. Here is another article which uses less math notation but has fewer details)
If an infinite set of numbers (or anything else) can be put into a one-to-one correspondence with the st of natural numbers (that is, it can be put into the form of an infinite list), we say it is a countable set. In the Science4All article, countable sets are called listable, which is a good name for them but is not standard.
First we discussed Hilbert's infinite hotel. Even if every room is occupied, we can accommodate an additional guest, or even a countably infinite number of guests! So you can say "infinity plus 1 is infinity" or "infinity plus infinity is infinity" - but wait! That second statement needs some care, because it turns out there are different sizes of infinity.
We showed the following in class:
• The whole numbers are countable (listable)
• The even numbers are countable (listable)
• The integers are countable (listable) - this is also proved in some of the videos linked below
• The rational numbers are countable (listable) - this is also proved in some of the videos linked below
• The real numbers are not countable. In other words, the set of real numbers is larger than the set of natural numbers (or even the set of rational numbers)!
The implication of this is that the set of irrational numbers is uncountable, which means that it is reasonable to say that there are more irrational numbers than rational numbers. (More on this next time.)
Look for the proofs of the following theorems in the article or in this video and this video (for the Cantor proof) , and here is another video as well. (all three of them are worth watching.)
• Theorem: The integers are countable (listable)
• Theorem: all countable (listable) sets have the same size (same number of elements)
• Theorem: The rational numbers are countable (listable)
And then the big one:
• Theorem: The real numbers are uncountable (they are not listable).
The last one is Cantor's diagonal proof, and it relies on the strategy that Player 2 can use for "Dodge Ball" to make sure they always win.
Homework:
• Journal assignment: write the proofs of the Theorems listed above in your own words.
• Prove that the odd numbers are countable (listable) by pairing them up with the natural numbers. (Make a one-to-one correspondence with the natural numbers. Watch the videos linked above if you have doubt about what this means.)
• Next time: Power sets and the Continuum Hypothesis. (The continuum is another name for the real number line.)
See Math is Fun on sets for some set notation that we will be using.
Topics: How to count/measure infinite sets!
First we have to examine closely what we do when we count a finite set. Essentially we are making what is called a one-to-one correspondence between the first however-many counting numbers (the natural numbers) and the items that we are counting.
The idea of one-to-one correspondence is what will carry over into infinite sets.
• David Hilbert's Hotel, and some theorems about the sizes of some infinite sets: See the Science4All article. (Warning: it contains math notation that may not display correctly on a phone. Here is another article which uses less math notation but has fewer details)
If an infinite set of numbers (or anything else) can be put into a one-to-one correspondence with the st of natural numbers (that is, it can be put into the form of an infinite list), we say it is a countable set. In the Science4All article, countable sets are called listable, which is a good name for them but is not standard.
First we discussed Hilbert's infinite hotel. Even if every room is occupied, we can accommodate an additional guest, or even a countably infinite number of guests! So you can say "infinity plus 1 is infinity" or "infinity plus infinity is infinity" - but wait! That second statement needs some care, because it turns out there are different sizes of infinity.
We showed the following in class:
• The whole numbers are countable (listable)
• The even numbers are countable (listable)
• The integers are countable (listable) - this is also proved in some of the videos linked below
• The rational numbers are countable (listable) - this is also proved in some of the videos linked below
• The real numbers are not countable. In other words, the set of real numbers is larger than the set of natural numbers (or even the set of rational numbers)!
The implication of this is that the set of irrational numbers is uncountable, which means that it is reasonable to say that there are more irrational numbers than rational numbers. (More on this next time.)
Look for the proofs of the following theorems in the article or in this video and this video (for the Cantor proof) , and here is another video as well. (all three of them are worth watching.)
• Theorem: The integers are countable (listable)
• Theorem: all countable (listable) sets have the same size (same number of elements)
• Theorem: The rational numbers are countable (listable)
And then the big one:
• Theorem: The real numbers are uncountable (they are not listable).
The last one is Cantor's diagonal proof, and it relies on the strategy that Player 2 can use for "Dodge Ball" to make sure they always win.
Homework:
• Journal assignment: write the proofs of the Theorems listed above in your own words.
• Prove that the odd numbers are countable (listable) by pairing them up with the natural numbers. (Make a one-to-one correspondence with the natural numbers. Watch the videos linked above if you have doubt about what this means.)
• Next time: Power sets and the Continuum Hypothesis. (The continuum is another name for the real number line.)
See Math is Fun on sets for some set notation that we will be using.
Test 3 Review, with answers/links
Test 3 is (re)scheduled for Tuesday 15 November.
The Test 3 Review problems are here. (link fixed)
Answers, and/or links to the relevant posts, are below the fold... I am temporarily working with an old computer which is very slow and has slow internet connection and has a difficult ketboard, so pardon any uncorrected typos (let me know about them!)
The Test 3 Review problems are here. (link fixed)
Answers, and/or links to the relevant posts, are below the fold... I am temporarily working with an old computer which is very slow and has slow internet connection and has a difficult ketboard, so pardon any uncorrected typos (let me know about them!)
03 November 2016
Thursday 3 November class
Topics:
• Proving that the square root of 2 is irrational: here are my notes, which I handed out in class. We also imitated that proof in the case of the square root of 3.
A similar proof will work in any case of a square root of a prime number. All square roots of prime numbers are irrational. But even more is true: If n is any positive integer (natural number) which is not a perfect square, then the square root of n is irrational. It is just a little more work to prove this if n is not a prime number, as you will see in the exercises.
• Density of rational numbers:
Theorem: between any two rational numbers, there is another rational number.
Proof: Take the average of the two rational numbers. The result is another rational number which is halfway between them.
Example: between $\frac{1}{2}$ and $\frac{3}{4}$ we can find the number $\left(\frac{1}{2} + \frac{3}{4}\right)\frac{1}{2}$ (their average, where instead of dividing by 2 we have multiplied by 2, which is the same thing. This comes out to be $\frac{5}{8}$, which is in between $\frac{1}{2}$ and $\frac{3}{4}$ and is a rational number.
Note: this is not the only rational number in between $\frac{1}{2}$ and $\frac{3}{4}$: but we only needed to show that there was at least one. So this one is convenient to find.
• A consequence of this theorem is that between any two rational numbers there is an infinite number of rational numbers. You can find rational numbers as close together as you like on the real number line. We say that the rational numbers are dense in the real numbers.
But even though the rational numbers are so close together and "thick" on the real line, there is still room enough for an infinite number of irrational numbers! In fact, as we will see next time, there are (in a very concrete sense) more irrational numbers than rational numbers.
• It follows from this that in between every two rational numbers there are infinitely many rational numbers. (Just keep taking averages of averages...)
• Comment: in fact, between every two real numbers (whether or not they are rational) there is a rational number, and also between every two real numbers there is an irrational number. The proofs of those facts are harder so we do not discuss them in this course. Ask Dr. Math gives a proof of the first statement here.
Homework:
• Journal assignment:
- The proof that the square root of 2 is irrational uses at one point the fact that if a2 is divisible by 2, then a must itself be divisible by 2. This happens because of the Fundamental Theorem of Arithmetic (Unique Prime Factorization). Explain why this is so. (Give an example, it may help. Factor both a and a2 into primes and see how their prime factorizations are related to each other.)
- What goes wrong if you try to imitate this proof to prove that the square root of 4 is irrational?
• Problems to do:
Related to 0.999999,,, = 1:
1) Write 0.09999999... as a fraction in lowest terms.
2) Write 0.29999999... as a fraction in lowest terms
3) Write 0.45999999... as a fraction in lowest terms
4) Prove that the square root of 5 is irrational
5) Prove that the square root of 6 is irrational. Since 6 is not a prime number, you will have to think about how to handle the step where we say "since a2 is divisible by 6, then a must itself be divisible by 6."
6) Challenge! This is extra credit. Prove that the square root of 12 is irrational. You must be extra-careful at the above-mentioned step here!
Next up: Hilbert's Hotel, which always has room for more: up to a point, that is. Measuring the size of infinity. Yes, it makes sense.
Please watch this video and this video (for the Cantor proof) , and here is another video as well. (all three of them are worth watching.)
• Proving that the square root of 2 is irrational: here are my notes, which I handed out in class. We also imitated that proof in the case of the square root of 3.
A similar proof will work in any case of a square root of a prime number. All square roots of prime numbers are irrational. But even more is true: If n is any positive integer (natural number) which is not a perfect square, then the square root of n is irrational. It is just a little more work to prove this if n is not a prime number, as you will see in the exercises.
• Density of rational numbers:
Theorem: between any two rational numbers, there is another rational number.
Proof: Take the average of the two rational numbers. The result is another rational number which is halfway between them.
Example: between $\frac{1}{2}$ and $\frac{3}{4}$ we can find the number $\left(\frac{1}{2} + \frac{3}{4}\right)\frac{1}{2}$ (their average, where instead of dividing by 2 we have multiplied by 2, which is the same thing. This comes out to be $\frac{5}{8}$, which is in between $\frac{1}{2}$ and $\frac{3}{4}$ and is a rational number.
Note: this is not the only rational number in between $\frac{1}{2}$ and $\frac{3}{4}$: but we only needed to show that there was at least one. So this one is convenient to find.
• A consequence of this theorem is that between any two rational numbers there is an infinite number of rational numbers. You can find rational numbers as close together as you like on the real number line. We say that the rational numbers are dense in the real numbers.
But even though the rational numbers are so close together and "thick" on the real line, there is still room enough for an infinite number of irrational numbers! In fact, as we will see next time, there are (in a very concrete sense) more irrational numbers than rational numbers.
• It follows from this that in between every two rational numbers there are infinitely many rational numbers. (Just keep taking averages of averages...)
• Comment: in fact, between every two real numbers (whether or not they are rational) there is a rational number, and also between every two real numbers there is an irrational number. The proofs of those facts are harder so we do not discuss them in this course. Ask Dr. Math gives a proof of the first statement here.
Homework:
• Journal assignment:
- The proof that the square root of 2 is irrational uses at one point the fact that if a2 is divisible by 2, then a must itself be divisible by 2. This happens because of the Fundamental Theorem of Arithmetic (Unique Prime Factorization). Explain why this is so. (Give an example, it may help. Factor both a and a2 into primes and see how their prime factorizations are related to each other.)
- What goes wrong if you try to imitate this proof to prove that the square root of 4 is irrational?
• Problems to do:
Related to 0.999999,,, = 1:
1) Write 0.09999999... as a fraction in lowest terms.
2) Write 0.29999999... as a fraction in lowest terms
3) Write 0.45999999... as a fraction in lowest terms
4) Prove that the square root of 5 is irrational
5) Prove that the square root of 6 is irrational. Since 6 is not a prime number, you will have to think about how to handle the step where we say "since a2 is divisible by 6, then a must itself be divisible by 6."
6) Challenge! This is extra credit. Prove that the square root of 12 is irrational. You must be extra-careful at the above-mentioned step here!
Next up: Hilbert's Hotel, which always has room for more: up to a point, that is. Measuring the size of infinity. Yes, it makes sense.
Please watch this video and this video (for the Cantor proof) , and here is another video as well. (all three of them are worth watching.)
01 November 2016
Report on RSA or other topic (Project 1) - UPDATED
- Report on RSA topic: due Thursday 10 November
Write an essay on one of the following topics, or if you have another idea check with me by email not later than Sunday:
* The history of the RSA algorithm and the people who developed it
* Current uses of the RSA algorithm and other public-key security
* The problem of computer factoring of large numbers: How long would it currently take to factor a number with 100 or more digits? What progress has been made recently? How would this affect the security of the RSA algorithm?
You should use at least two different sources for your essay. List your sources in correct format and make sure to cite them (cite sources for quotes and make bibliography) correctly. Your essay should be approximately 2 pages long (typed in no bigger than 12 point font.)
Citation styles source here. You may use APA style (this is the one most commonly used in the sciences) or MLA if you are more familiar with it.
Note: You may work together with another student, if you like: both together should produce one paper. If you want to do this, please let me know by email BEFORE the due date.
Write an essay on one of the following topics, or if you have another idea check with me by email not later than Sunday:
* The history of the RSA algorithm and the people who developed it
* Current uses of the RSA algorithm and other public-key security
* The problem of computer factoring of large numbers: How long would it currently take to factor a number with 100 or more digits? What progress has been made recently? How would this affect the security of the RSA algorithm?
You should use at least two different sources for your essay. List your sources in correct format and make sure to cite them (cite sources for quotes and make bibliography) correctly. Your essay should be approximately 2 pages long (typed in no bigger than 12 point font.)
Citation styles source here. You may use APA style (this is the one most commonly used in the sciences) or MLA if you are more familiar with it.
Note: You may work together with another student, if you like: both together should produce one paper. If you want to do this, please let me know by email BEFORE the due date.
Rational and Irrational numbers UPDATED - Tuesday 1 November class
Update: here are some links to good sources about how people in Euclid's time and place thought about numbers, and about the Pythagoreans in particular:
Euclid's Proof of the Infinitude of Primes (from the Prime Pages, a great source for all things related to prime numbers. This discussed how the numbers were viewed at Euclid's time and place.)
Pythagorus - Greek Mathematics (from The Story of Mathematics website)
Pythagoras - The Music and Math Connection (video, from the Science Channel: Warning: video may autoplay)
• Rational and Irrational numbers:
We begin by defining some important sets of numbers (some we have seen before):
the Natural numbers - which are also called the positive integers
the Whole numbers (which include the Natural numbers) - also called the non-negative integers
the Integers (which include the Whole numbers)
the Rational numbers (which include the Integers)
If we think of "number" as a directed distance ( a vector) starting from 0 on the number line, then there are points on the number line that correspond to these numbers we have defined so far. But it turns out that there are ponts (distances) which cannot be represented as a ratio of integers. We call these numbers Irrational numbers.
Examples of numbers which are irrational include π and the square root of 2. We will prove later that the square root of 2 is irrational.
We showed how the square root of 2 appears as a length (distance), namely, the hypotenuse of a right triangle whose sides both have length 1. Using the Pythagorean Theorem, the hypotenuse has length the square root of 2.
For any rational number, we can prove (using the Pigeonhole Principle) that its decimal expansion will either terminate or (eventually) repeat (here's another description of the proof from A Math Less Travelled): also, conversely, a terminating or repeating decimal will always represent a rational number. So from this we know that an irrational number must be represented by a nonterminating, nonrepeating decimal. That decimal is called the decimal expansion of the number.
More on the decimal expansions of rational numbers: how long can they go on before they repeat? (Here is a discussion similar to what I said in class which also uses the Pigeonhole principle: scroll down at that link until the header "Decimal representations of rational". )
How to write a repeating decimal as a ratio of integers: videos from Khan Academy part 1, part 2
So 0.9999999... = 1
[A better way to prove that 0.9999999... = 1 uses the idea of limit and the sum of an infinite geometric series - this is usually done in pre-calculus classes. The fact is that an infinite decimal expansion is really an infinite sum: 0.9999999... means 9/10 + 9/100 + 9/1000 + 9/10000 + ... (the sum has infinitely many terms).]
Homework:
(Journal assignment pending)
Problems to do:
1) By using long division by hand, find the decimal expansions of these rational numbers:
$\frac{1}{250}$
$\frac{3}{11}$
$\frac{7}{12}$
2) Rewrite the following decimals as ratios of integers: reduce to lowest terms
2.3
0.056
0.1717171717...
0.2555555...
Next up: proving that the square root of 2 is irrational; other irrational numbers; more on decimal expansions; the Real Numbers
Euclid's Proof of the Infinitude of Primes (from the Prime Pages, a great source for all things related to prime numbers. This discussed how the numbers were viewed at Euclid's time and place.)
Pythagorus - Greek Mathematics (from The Story of Mathematics website)
Pythagoras - The Music and Math Connection (video, from the Science Channel: Warning: video may autoplay)
• Rational and Irrational numbers:
We begin by defining some important sets of numbers (some we have seen before):
the Natural numbers - which are also called the positive integers
the Whole numbers (which include the Natural numbers) - also called the non-negative integers
the Integers (which include the Whole numbers)
the Rational numbers (which include the Integers)
If we think of "number" as a directed distance ( a vector) starting from 0 on the number line, then there are points on the number line that correspond to these numbers we have defined so far. But it turns out that there are ponts (distances) which cannot be represented as a ratio of integers. We call these numbers Irrational numbers.
Examples of numbers which are irrational include π and the square root of 2. We will prove later that the square root of 2 is irrational.
We showed how the square root of 2 appears as a length (distance), namely, the hypotenuse of a right triangle whose sides both have length 1. Using the Pythagorean Theorem, the hypotenuse has length the square root of 2.
For any rational number, we can prove (using the Pigeonhole Principle) that its decimal expansion will either terminate or (eventually) repeat (here's another description of the proof from A Math Less Travelled): also, conversely, a terminating or repeating decimal will always represent a rational number. So from this we know that an irrational number must be represented by a nonterminating, nonrepeating decimal. That decimal is called the decimal expansion of the number.
More on the decimal expansions of rational numbers: how long can they go on before they repeat? (Here is a discussion similar to what I said in class which also uses the Pigeonhole principle: scroll down at that link until the header "Decimal representations of rational". )
How to write a repeating decimal as a ratio of integers: videos from Khan Academy part 1, part 2
So 0.9999999... = 1
[A better way to prove that 0.9999999... = 1 uses the idea of limit and the sum of an infinite geometric series - this is usually done in pre-calculus classes. The fact is that an infinite decimal expansion is really an infinite sum: 0.9999999... means 9/10 + 9/100 + 9/1000 + 9/10000 + ... (the sum has infinitely many terms).]
Homework:
(Journal assignment pending)
Problems to do:
1) By using long division by hand, find the decimal expansions of these rational numbers:
$\frac{1}{250}$
$\frac{3}{11}$
$\frac{7}{12}$
2) Rewrite the following decimals as ratios of integers: reduce to lowest terms
2.3
0.056
0.1717171717...
0.2555555...
Next up: proving that the square root of 2 is irrational; other irrational numbers; more on decimal expansions; the Real Numbers
27 October 2016
Thursday 27 October class
Topics:
• Outlining the proof that there is no largest prime number
For this purpose the best source to use is Delphi For Fun on Proof by Contradiction, which explains a bit of the logic behind proofs by contradiction. You may then also want to look at these sources:
Why are there infinitely many prime numbers? (from Peter Alfeld, University of Utah)
Euclid's proof that there are an infinite number of primes (from Susan Stepney, University of York, UK) - this one, beware: the part below the line, where it says "for example", is not part of the proof!
And also the sources linked below...
• How Euclid (and those of his time and place) conceived of the proof and their concept of "number":
See Cut-The-Knot, which gives alternate versions of the proof as well,but is rather technical: and also the proof as described in the Prime Number Pages, which describes how Euclid would have thought of numbers.
Here is the outline of the proof we developed in class. I've put an asterisk * next to parts that need proving but are not proved in any of the sources linked above, for some reason. We did the proofs of those parts in previous classes.
To prove: there is no largest prime number
Proving by contradiction (reductio ad absurdum): we will assume the opposite, and show that assumption leads to a contradiction.
Outline of Proof:
• Assume that there is a largest prime number. Call it p.
[Note: either there is a largest prime number, or there is not a largest prime number. There is no other possibility. This is important for the logic of the proof.]
Commentary: This assumption puts us into an alternate universe, not the one we actually live in. The rest of this proof will be showing that that alternate universe cannot exist. In that alternate universe, we know everything else we know about prime numbers from our universe, including the Fundamental Theorem of Arithmetic (Unique Prime Factorization), but we are assuming that in that universe there is a largest prime number.
OK, now in the alternate universe:
• Construct the number N = (the product of all the prime numbers 2 through p) +1.
Then N has these properties:
* • N > p
[so N cannot be prime, as p is the largest prime number in the alternate universe]
* • N is not divisible by any of the prime numbers 2 through p
[so N must be prime, as these are all the possible prime factors of N in the alternate universe]
• But N cannot be both non-prime and prime at the same time:
CONTRADICTION!
A final note about this proof: where do we use the Fundamental Theorem of Arithmetic? It is in the step where we prove that N is not divisible by any of the prime numbers 2 through p, and conclude from this that N must be prime. (Some people say that we conclude that either N is prime or N has a prime factor greater than p. The second part is not necessary, but if it makes you feel better, go ahead and put it in. You'll have to patch up the contradiction in the last line of the proof, in that case.)
• Outlining the proof that there is no largest prime number
For this purpose the best source to use is Delphi For Fun on Proof by Contradiction, which explains a bit of the logic behind proofs by contradiction. You may then also want to look at these sources:
Why are there infinitely many prime numbers? (from Peter Alfeld, University of Utah)
Euclid's proof that there are an infinite number of primes (from Susan Stepney, University of York, UK) - this one, beware: the part below the line, where it says "for example", is not part of the proof!
And also the sources linked below...
• How Euclid (and those of his time and place) conceived of the proof and their concept of "number":
See Cut-The-Knot, which gives alternate versions of the proof as well,but is rather technical: and also the proof as described in the Prime Number Pages, which describes how Euclid would have thought of numbers.
Here is the outline of the proof we developed in class. I've put an asterisk * next to parts that need proving but are not proved in any of the sources linked above, for some reason. We did the proofs of those parts in previous classes.
To prove: there is no largest prime number
Proving by contradiction (reductio ad absurdum): we will assume the opposite, and show that assumption leads to a contradiction.
Outline of Proof:
• Assume that there is a largest prime number. Call it p.
[Note: either there is a largest prime number, or there is not a largest prime number. There is no other possibility. This is important for the logic of the proof.]
Commentary: This assumption puts us into an alternate universe, not the one we actually live in. The rest of this proof will be showing that that alternate universe cannot exist. In that alternate universe, we know everything else we know about prime numbers from our universe, including the Fundamental Theorem of Arithmetic (Unique Prime Factorization), but we are assuming that in that universe there is a largest prime number.
OK, now in the alternate universe:
• Construct the number N = (the product of all the prime numbers 2 through p) +1.
Then N has these properties:
* • N > p
[so N cannot be prime, as p is the largest prime number in the alternate universe]
* • N is not divisible by any of the prime numbers 2 through p
[so N must be prime, as these are all the possible prime factors of N in the alternate universe]
• But N cannot be both non-prime and prime at the same time:
CONTRADICTION!
A final note about this proof: where do we use the Fundamental Theorem of Arithmetic? It is in the step where we prove that N is not divisible by any of the prime numbers 2 through p, and conclude from this that N must be prime. (Some people say that we conclude that either N is prime or N has a prime factor greater than p. The second part is not necessary, but if it makes you feel better, go ahead and put it in. You'll have to patch up the contradiction in the last line of the proof, in that case.)
20 October 2016
Thursday 20 October class
Topic:
Outlining the "proof" that the RSA works, for the example given in my notes.
This is not a real proof (hence the scare quotes above), because it only proves that RSA works for this particular example. However, if you read carefully, you can see that nothing in the proof depends on the specific numbers we use, but only on their relationship to each other. (UPDATE: here are the revised notes. I hope they are a bit clearer: certainly they are longer!)
The essential thing we are trying to prove is this:
If we encode a message, and then decode it, we come back to the original message.
In the example, the message was the number 71.
The public keys were the numbers 143 = 11*13 (the modulus) and 7 (the exponent).
To find 143, we chose two prime numbers and multiplied them together.
Then we had to compute the number (11-1)*(13-1) = 120 and choose the exponent so that it had no factors in common with that number 120.
The private key was the number 103. This number came from solving the Diophantine equation ed-my=1, or equivalently, from solving the modular congruence ed ≡ 1 (mod m), where e=7 (our public key exponent) and m = 120 (the number that e was chosen to have no factors in common with).
What we want to prove in the example is that if we encode the message 71 by taking 717 (mod 143), and then decode that encoded message by taking it to the 103rd power (mod 143), we get back the original message 71.
In other words, we want to prove (without actually computing it) that
(717)103 ≡ 71 (mod 143)
Here are the essential steps of the proof:
• Prove that 717 ≡ 124 (mod 143) means that 717 ≡ 124 (mod 11) and 717 ≡ 124 (mod 13)
[This is a special case of a general theorem: if two numbers are equivalent mod n, then they are also equivalent modulo any prime factor of n.]
• Prove that (717)103 ≡ 71 (mod 11) using Fermat's Little Theorem
• This means that (717)103 - 71 is divisible by 11 (division algorithm)
• Prove that (717)103 ≡ 71 (mod 13) using Fermat's Little Theorem
• This means that (717)103 - 71 is divisible by 13 (division algorithm0
• Since (717)103 - 71 is divisible by both 11 and 13, it must be divisible by their product 143 (Here we use Unique Prime Factorization, a/k/a the Fundamental Theorem of Arithmetic.)
• So (717)103 ≡ 71 (mod 143)
Outlining the "proof" that the RSA works, for the example given in my notes.
This is not a real proof (hence the scare quotes above), because it only proves that RSA works for this particular example. However, if you read carefully, you can see that nothing in the proof depends on the specific numbers we use, but only on their relationship to each other. (UPDATE: here are the revised notes. I hope they are a bit clearer: certainly they are longer!)
The essential thing we are trying to prove is this:
If we encode a message, and then decode it, we come back to the original message.
In the example, the message was the number 71.
The public keys were the numbers 143 = 11*13 (the modulus) and 7 (the exponent).
To find 143, we chose two prime numbers and multiplied them together.
Then we had to compute the number (11-1)*(13-1) = 120 and choose the exponent so that it had no factors in common with that number 120.
The private key was the number 103. This number came from solving the Diophantine equation ed-my=1, or equivalently, from solving the modular congruence ed ≡ 1 (mod m), where e=7 (our public key exponent) and m = 120 (the number that e was chosen to have no factors in common with).
What we want to prove in the example is that if we encode the message 71 by taking 717 (mod 143), and then decode that encoded message by taking it to the 103rd power (mod 143), we get back the original message 71.
In other words, we want to prove (without actually computing it) that
(717)103 ≡ 71 (mod 143)
Here are the essential steps of the proof:
• Prove that 717 ≡ 124 (mod 143) means that 717 ≡ 124 (mod 11) and 717 ≡ 124 (mod 13)
[This is a special case of a general theorem: if two numbers are equivalent mod n, then they are also equivalent modulo any prime factor of n.]
• Prove that (717)103 ≡ 71 (mod 11) using Fermat's Little Theorem
• This means that (717)103 - 71 is divisible by 11 (division algorithm)
• Prove that (717)103 ≡ 71 (mod 13) using Fermat's Little Theorem
• This means that (717)103 - 71 is divisible by 13 (division algorithm0
• Since (717)103 - 71 is divisible by both 11 and 13, it must be divisible by their product 143 (Here we use Unique Prime Factorization, a/k/a the Fundamental Theorem of Arithmetic.)
• So (717)103 ≡ 71 (mod 143)
13 October 2016
Thursday 13 October class
Note: No journals are due this week. Hold on till next week.
Also don't forget that this class will not meet on Tuesday the 18th of October!
After Test 2 our next meeting will be Thursday the 20th.
Topics:
• Activity related to the video on Fermat's Little Theorem linked in last time's post.
• Review of reasoning I used in computing 71492 (mod 100) (to remind that we could not just reduce the exponent mod 100) - see more on this below
• Showing why the RSA algorithm works (from my notes) - we only got through the first part of the proof on p. 3 of these notes, so it will continue next time.
More comments on the problem of computing exponential expressions in modular arithmetic:
I asserted and also gave an example in class to show that you cannot reduce the exponent (at least, not to the modulus you are starting with). I do not know if I wrote up my example in the blog, so here is an example (which may or may not be the one I did in class):
Suppose we want to compute 318 (mod 5).
This can be found with a calculator by computing 318 = 387420489, and then reducing mod 5, so we get 318 ≡ 4 (mod 5).
But if we try to shortcut by reducing the exponent mod 5, we get 18 ≡ 3 (mod 5), so we would think that our answer could be computed by taking 33 = 27 ≡ 2 (mod 5), which is not the correct answer.
Referring back to this post (or to the reading from Art of Problem Solving), the cases where we can reduce before performing the computations (and then reduce again, if necessary) are these:
• In addition or subtraction, we can reduce the numbers before adding or subtracting
• In multiplication, we can reduce the numbers before multiplying - (please note that there is no division in modular arithmetic)
• Because we can reduce factors before we multiply them together, we can reduce the base of a natural number exponent (since the base represents the factor which is being repeatedly multiplied together) before taking the power.
When it is the exponent which is "too big", other tricks must be used, such as looking for patterns in the powers of the base (as in the example of 71492) or using Fermat's Little Theorem (which is a special case of looking for patterns in the powers.)
Homework:
• Journal assignment: watch the video on Fermat's Little Theorem (which was assigned previously!), write on what you learn from it, and then use that to try the Activity again.
• Problems related to Fermat's Little Theorem:
1) Compute each of the following:
a) 14 (mod 5), 24 (mod 5), 34 (mod 5), 44 (mod 5)
b) 16 (mod 7), 26 (mod 7), 36 (mod 7), 46 (mod 7), 56 (mod 7), 66 (mod 7)
c) How does Fermat's Little Theorem relate to the answers in (a) and (b)?
2a) Using Fermat's Little Theorem (not by direct computation), find 800030 (mod 31). You must verify that the conditions are correct to use the theorem in this problem.
b) Compute 80004 (mod 5). The answer is not 1. Why doesn't this contradict Fermat's LittleTheorem?
Up next: Completing the verification of the RSA algorithm (showing why it works). Reread the part of the proof on p. 3 of the notes and make sure that you are following the reasoning being used at each step (even if you don't see where it is going yet). Next time we will outline or "flowchart" the proof to get a better idea of how it fits together.
Also don't forget that this class will not meet on Tuesday the 18th of October!
After Test 2 our next meeting will be Thursday the 20th.
Topics:
• Activity related to the video on Fermat's Little Theorem linked in last time's post.
• Review of reasoning I used in computing 71492 (mod 100) (to remind that we could not just reduce the exponent mod 100) - see more on this below
• Showing why the RSA algorithm works (from my notes) - we only got through the first part of the proof on p. 3 of these notes, so it will continue next time.
More comments on the problem of computing exponential expressions in modular arithmetic:
I asserted and also gave an example in class to show that you cannot reduce the exponent (at least, not to the modulus you are starting with). I do not know if I wrote up my example in the blog, so here is an example (which may or may not be the one I did in class):
Suppose we want to compute 318 (mod 5).
This can be found with a calculator by computing 318 = 387420489, and then reducing mod 5, so we get 318 ≡ 4 (mod 5).
But if we try to shortcut by reducing the exponent mod 5, we get 18 ≡ 3 (mod 5), so we would think that our answer could be computed by taking 33 = 27 ≡ 2 (mod 5), which is not the correct answer.
Referring back to this post (or to the reading from Art of Problem Solving), the cases where we can reduce before performing the computations (and then reduce again, if necessary) are these:
• In addition or subtraction, we can reduce the numbers before adding or subtracting
• In multiplication, we can reduce the numbers before multiplying - (please note that there is no division in modular arithmetic)
• Because we can reduce factors before we multiply them together, we can reduce the base of a natural number exponent (since the base represents the factor which is being repeatedly multiplied together) before taking the power.
When it is the exponent which is "too big", other tricks must be used, such as looking for patterns in the powers of the base (as in the example of 71492) or using Fermat's Little Theorem (which is a special case of looking for patterns in the powers.)
Homework:
• Journal assignment: watch the video on Fermat's Little Theorem (which was assigned previously!), write on what you learn from it, and then use that to try the Activity again.
• Problems related to Fermat's Little Theorem:
1) Compute each of the following:
a) 14 (mod 5), 24 (mod 5), 34 (mod 5), 44 (mod 5)
b) 16 (mod 7), 26 (mod 7), 36 (mod 7), 46 (mod 7), 56 (mod 7), 66 (mod 7)
c) How does Fermat's Little Theorem relate to the answers in (a) and (b)?
2a) Using Fermat's Little Theorem (not by direct computation), find 800030 (mod 31). You must verify that the conditions are correct to use the theorem in this problem.
b) Compute 80004 (mod 5). The answer is not 1. Why doesn't this contradict Fermat's LittleTheorem?
Up next: Completing the verification of the RSA algorithm (showing why it works). Reread the part of the proof on p. 3 of the notes and make sure that you are following the reasoning being used at each step (even if you don't see where it is going yet). Next time we will outline or "flowchart" the proof to get a better idea of how it fits together.