Comments on Test 4

below the fold... this is to help with the Final Exam preparation.

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

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.)

Tuesday 6 December class

Topics:

• 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

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...

How Tests 2 and 3 are being graded

below the fold...

Extra Credit you may want to work on (Updated)

below the fold are some possibilities, most of which I have mentioned in class already.

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.

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)

.

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 2ⁿ. 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 2ⁿ means even if n is an infinite numbers, and the point is, we have proved that 2ⁿ (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 א‎₀ (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^א‎₀.

The Continuum Hypothesis is the statement that there is no cardinality that is between א‎₀ and 2^א‎₀, so 2^א‎₀ 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)| = 2³ = 8
Form the power set of the power set: its size is |P(P(S))| = 2⁸ = 256
Form the power set of the power set of the power set: its size is |P(P(P(S)))| = 2²⁵⁶ = 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.

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  ℵ₀ - 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 2ⁿ 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 2ⁿ 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!

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.

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!)

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  a² 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 a² 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 a² 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.)

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.

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

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.)

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 71⁷ (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
(71⁷)¹⁰³  ≡ 71 (mod 143)

Here are the essential steps of the proof:

• Prove that 71⁷  ≡ 124 (mod 143) means that  71⁷  ≡ 124 (mod 11) and 71⁷  ≡ 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 (71⁷)¹⁰³  ≡ 71 (mod 11) using Fermat's Little Theorem
• This means that  (71⁷)¹⁰³  - 71 is divisible by 11 (division algorithm)

• Prove that (71⁷)¹⁰³ ≡ 71 (mod 13) using Fermat's Little Theorem
• This means that  (71⁷)¹⁰³  - 71 is divisible by 13 (division algorithm0

• Since (71⁷)¹⁰³  - 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 (71⁷)¹⁰³  ≡ 71 (mod 143)

A better source for proof by contradiction

Delphi for Fun

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 7¹⁴⁹² (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 3¹⁸ (mod 5).
This can be found with a calculator by computing 3¹⁸ = 387420489, and then reducing mod 5, so we get 3¹⁸ ≡ 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 3³ = 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 7¹⁴⁹²) 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) 1⁴ (mod 5), 2⁴ (mod 5), 3⁴ (mod 5), 4⁴ (mod 5)
     b) 1⁶ (mod 7), 2⁶ (mod 7), 3⁶ (mod 7), 4⁶ (mod 7), 5⁶ (mod 7), 6⁶ (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 8000³⁰ (mod 31). You must verify that the conditions are correct to use the theorem in this problem.
  b) Compute 8000⁴ (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.

Activity for Thursday 13 October

Fermat's Little Theorem: for any prime number p, and any natural number a which is not divisible by p,
$a^{p-1} \equiv 1$ (mod p)


For example, $4^{10} \equiv 1$ (mod 11)
because 11 is a prime number and 4 is not divisible by 11.


Based on your viewing of the video, assigned last time, from Maths by Jay, which discussed Fermat's Little Theorem and how it can be used to simplify some calculations:

Use the above-mentioned fact to find the value of
$4^{1357}$ (mod 11)
















Hint: You'll use the division algorithm on the exponent 1357







You want to rewrite $4^{1357}$ as a power of $4^{10}$, times another power of 4

Test 2 review problems

Test 2 is scheduled for Friday 14 October. The review problems are here. Answers and/or links will be posted soon, but I strongly encourage everyone to go back and review the proof that there is no largest prime number and make sure that you understand the reasoning that is being used in the proof. In particular, make sure that you understand how proof by contradiction works! The relevant links describing the proof are in this post (the readings at the end of the post), and a description of how the division algorithm fits in is in this post.

Thursday 29 September class

• Warmup activity: finding a pattern in the powers of 8 mod 5, and in the powers of 5 mod 3
We observed that in each case the powers cycled through all the possible nonzero residues, ending with 1:

81 ≡ 3 (mod 5)	51 ≡ 2 (mod 3)
82 ≡ 4 (mod 5)	52 ≡ 1 (mod 3)
83 ≡ 2 (mod 5)	53 ≡ 2 (mod 3)
84 ≡ 1 (mod 5)	54 ≡ 1 (mod 3)
85 ≡ 3 (mod 5)	55 ≡ 2 (mod 3)
... etc. ...	... etc. ...

Next time I will show you how you can exploit modular arithmetic to keep the numbers small when doing this type of computation - which will partially answer the question of what happens in RSA when the numbers get too big for even a computer to handle.

These are examples of Fermat's Little  Theorem:
If p is a prime number, and a is any integer which does not have p as a factor, then
a^p-1 ≡ 1 (mod p)

In the two examples we had
a=8, p=5: 8^5-1 = 8⁴ ≡ 1 (mod 5)
a=5, p=3: 5^3-1 = 5² ≡ 1 (mod 3)

This Theorem plays a role in proving that the RSA algorithm works. (see the notes)

• We showed how the two public keys and the private key are found, first by the example in my notes, and then by the example in this reading (Serge Matovic's homepage: see Section 1). We showed how his method for finding the private key is really the same as the method in my notes.:

In my notes, to find the private key d, we solve the Diophantine equation ed - my = 1 for integers d and y (actually, we want them to be natural numbers in fact)
So in Serge's example, we would be solving 7d - 20y =1 for natural numbers d and y
In Serge's webpage, he does this by solving the modular equation 7d ≡ 1 (mod 20)
By the division algorithm, this is the same as saying that 7d = 20q + 1 for some whole number q.
If you take our Diophantine equation and add 20y to both sides, you get exactly this - it doesn't matter whether you call the quotient q or y. 

So these are actually the same procedure written in different ways. It's an equally difficult or easy problem either way. It is just a matter of taste which way to go.

In a sense the RSA algorithm is a generalization of the Little Fermat Theorem, as discussed in the background article.

Homework:
• Journal assignment:

• Problems related to the RSA algorithm: (corrected problem number references)
1) Choosing the prime numbers p=3 and q=5, compute m [as in my notes on RSA] and then find possible values for e and d, using trial and error. Record your trial and error or other reasoning to explain how you got them! And try to keep them small.
2) Using the public and private keys you found in problem (1), encode the message 809.
3) Using the private key you found in problem (1), decode the encoded message from problem (4) and show that the decoded message is the original message 809.


• For future use: you will be asked to write a short essay on some aspect of the RSA algorithm. Start thinking about this and doing research on the area you would like to write about. Here are some suggestions (pick ONE, or make up one of your own):
    • The history of the RSA algorithm: how and why it came to be developed by Rivest, Shamir, and Adleman
    • How RSA is used today
    • How long would it take the fastest computer to factor large numbers? What progress has been made on this problem in recent years?

Next up: Explaining why the RSA algorithm works, and how to exploit modular arithmetic to keep the numbers for getting too large when we take those powers. This will involve using Fermat's Little Theorem: please view this video which gives an example  and then shows you how it can be used!

Journal 4 to be submitted by 5:30 PM today

This post is to clarify what goes into this journal submission and what its number is.

This is journal 4, so when you name your file that is the journal number you should use.

(If you have already submitted it, please make sure that you used the number 4, and if you did not, please go back and change the filename. You do not need to make a new post: you can just edit the post you already made, remove the uploaded file link, rename the file, and edit the post again to put in the file with the correct name. PLEASE DO NOT LEAVE THE FILE WITH THE WRONG NAME POSTED!)

Journal 4 submission should contain everything in your journal since Test 1: in other words, starting with Tuesday the 19th, up until what you have as of the start of class today (not including today's class, obviously!)

Please make sure that you follow the instructions in this post (as always) for naming your file and for posting it to Piazza, and what your summary line of your Piazza post should be.

If you fail to follow the instructions I will simply respond to your post telling you that you did not follow instructions, and I will not evaluate your journal until you've corrected the situation. 

National Voter Registration Day - register to vote

Today is National Voter Registration Day.

If you are eligible to vote and have not already done so, please register and vote in the upcoming  November elections. (There are many positions on the ballot, not just the Presidential election!)

In New York state, the deadline to register for this election is the 14th of October. You can find information  for NY State about how to check eligibility and how to register either online, by mail, or in person, at this link. (Thanks, Google!) You can also check the status of your registration if you previously registered to vote, to make sure everything is OK.

Here is the link with information for registering in New Jersey. NJ does not have online registration: you must register by mail or in person. The deadline for NJ is the 18th of October.

Note: in NY State, Students may establish voting residency in the place they consider their principal home, whether that be their current school address or at another address (such as a parent’s address) they still consider to be “home.”  

So if you are an out-of-state student living in a Brooklyn College dorm you may register to vote in  NY State or in your home state, it is up to you. Source: the Brennan Center.

Tuesday 27 September class

Topics:
• Warmup for RSA (although the connection will not be made until next time):
   Find two integers d and y such that 11d - 8y = 1. (There are infinitely many solutions, in fact.) It turns out that the solution with the smallest integers (in absolute value)  is d=3, y=4. There is also an easy way to generate other solutions once you have one: add a multiple of 8 to d and add the same multiple of 11 to y. (It can be proved that this always works.)

• We discussed some of the homework problems, specifically, what in the multiplication table mod 4 is problematic.

The problem with using a modulus that is not prime is that there will be products which are 0 but where the factors are both non-zero.  (These are called zero divisors.) In mod 4, we have 2•2 ≡ 0. This means that there is no "zero product principle" in that number system: if a•b = 0, it is not necessarily true that a=0 or b=0.

• Warmup for RSA (although the connection will not be made until next time):
   Find two integers d and y such that 11d - 8y = 1. (There are infinitely many solutions, in fact.) It turns out that the solution with the smallest integers (in absolute value)  is d=3, y=4. There is also an easy way to generate other solutions once you have one: add a multiple of 8 to d and add the same multiple of 11 to y. (It can be proved that this always works.)
Note: In general, an equation which is to be solved for solutions in the integers is called a Diophantine equation. We will see another example (coming from the Pythagorean Theorem) later in the course.

• Note that when we use the word "code" or "coding" in what follows, it does not always mean that we are trying to keep something a secret! See these Wikipedia articles about code and coding theory.

• UPCs (Universal Product Codes) as an application of modular arithmetic: modular arithmetic is employed to check that the code has been entered correctly. In a 12-digit UPC, the first 6 digits represent the company that makes the product, and the next 5 digits represent the product itself. The last digit is a check digit, chosen so that a certain sum will be congruent to 0 mod 10.

If we call the digits d₁, d₂,d₃,..., d₁₂, then the checksum is
 3d₁ + d₂ + 3d₃ + d₄ + 3d₅ + d₆ + ... + 3d₁₁ + d₁₂
and we require that this checksum be ≡ 0 (mod 10)

We checked some examples in class and also checked to see what happened when we reversed two of the digits in a UPC (an easy mistake to make). When two adjacent nonzero digits were reversed, the checksum was no longer ≡ 0 (mod 10).

This sort of checksum catches many (most?) errors but there are some errors that it will not catch. This is a tradeoff: we want the checking process to be simple and quick (not to waste time) but we also want to catch as many errors as possible. A more elaborate checking process might catch more errors but also would take more time to carry out. In each case of a coding like this (ISBNs, credit card numbers, account numbers, etc.) a decision has to be made how to balance out these two concerns.


Homework:
• Journal assignment: Write up what you learned about the purpose of the checksum for a UPC. How does it check for errors? Why is it important to check for errors? You may want to see if you can find out what kind of checksums are used for other important numbers, such as ISBNs.

Also use your journal (as always) to work out concepts in the lesson that may not be clear to you.

• Problems on UPCs: these are all based on real UPCs, and all the real UPCs I have found so far begin with 0. I don't know why that is.
1) Is each of the following a valid UPC or not?  (I've put spaces in them to represent how they are usually shown on the products these days.)
    a) 0 28367 82855 9
    b) 0 75063 01114 0
2) Find the check digit for the UPC:  (if you have any doubt about how to do this, consult the Wikipedia article - remember that you want the checksum to be congruent to 0 mod 10)
    a) 0 28367 82903 _
    b) 0 50428 10148 _
3) The UPC for a product is  0 50428 32193 5
   Explain why the checksum will not catch the following errors:
    a) 0 50428 39123 5
    b) 0 50428 19323 5
4)(Based on a problem from The Heart of Mathematics)
A friend with bad handwriting writes down a UPC. Unfortunately, you can't tell his 4's from his 9's (they look alike), or his 1's from his 7's (they also look alike). If the code looks like 903068823517, is there any way you can figure out what the real UPC is? If so, what do you do and what is the real UPC? If it is not possible to determine the correct UPC, explain why.

• Next topic is the RSA algorithm for encoding a message to be sent, for security purposes. Make sure that you read this RSA algorithm background article (from Slate).

There will be three phases of discussion of the RSA algorithm:
    First, how it is carried out. We will do this next time with two examples.
    Second, how we find the two public keys and the private key. That's coming up later. And then finally:
    Third, how to prove that the algorithm works.

My notes were handed out in class and are also available here.  You could take look through the first page, after reading the background article linked above.  We will also use this reading from Serge Matovic's homepage. (Section 2 and Section 3 where he encodes and decodes the message. He shows how to use a calculator and some tricks to find the remainder we need.)

Math Club talk about proving the infinitude of primes

This may be of interest since we have already discussed one of the proofs. And there's pizza!

----------------------------------------

Mathematical Sciences Colloquium

Alexander Gindes

Brooklyn College Mathematics

Title: Four Proofs of the Infinitude of Primes

Abstract: We will discuss one of the most beautiful theorems in all of mathematics – the infinitude of primes. We will give four proofs with variations: Euclid's indirect proof, Euler's analytic proof, Furstenberg's topological proof, and Chaitin's complexity proof. These proofs reflect the evolution of techniques in number theory and in mathematical proofs in general.

Date: Tuesday September 27, 2016 
Time: 12:30 pm - 1:30 pm 
Location: 1146 Ingersoll Hall 

Pizza will be served.

This colloquium is sponsored by the Math Club www.facebook.com/bcmathclub 

Thursday 22 September class

Topics:
• Activity: computing 96³ mod 7  two ways:
  By first computing 96³ and then reducing mod 7
  By first reducing 96 mod 7, then raising that number to the 3rd power (and then reducing again)
This showed by example that we can reduce the base of a whole number exponent before exponentiation in modular arithmetic. (This is not a proof, but an example.)

While showing the solution on the board, I showed how you can use a calculator to find a remainder/residue. The details are in this post.

We contrast this with the computation of 7¹⁹⁴² mod 100 that we did last time. The difference was that there we would want to reduce the exponent, but reducing mod 100 does not work. (I could not show this directly because the numbers involved are too big, but I made an example of 3¹⁵ mod 5 later.)

This led to a discussion of a heuristic that connects to the thinking involved in the way we found the value of 7¹⁹⁴² mod 100. I have posted those notes separately.

Next  was to construct some addition and multiplication tables for modular arithmetic. Since the modular number systems are finite, we can construct complete tables for them. Fixing the modulus m,  we show all the residues for that modulus along the top and side of the table: then the entry at each intersection of a row and column is the sum or product of those two residues, reduced mod m. We made the following addition and multiplication tables:

Mod 2: Addition

+	0	1
0	0	1
1	1	0

Mod 2: Multiplication

•	0	1
0	0	0
1	0	1

Mod 3: Addition

+	0	1	2
0	0	1	2
1	1	2	0
2	2	0	1

The tables for mod 2 allow us to prove the results for the questions in last time's warmup, and others, since an integer is even if (and only if) it is congruent to 0 mod 2, and it is odd if (and only if) it is congruent to 1 mod 2. Therefore, for example, we can translate:

0+0 ≡ 0 (mod 2) means that "even plus even = even"

1+1 ≡ 0 (mod 2) means that "odd plus odd = even"

But we get even more: 0+1 ≡ 1 (mod 2) means that "even plus odd = odd"

Go through the tables and see what else they prove!


Homework:
• Journal assignment: Write about the group activity (computing 96³ (mod 7) two ways): what your group did, and what you learned about modular arithmetic from this.
• Problems to work:
1)  Construct a multiplication table for multiplication mod 3

2) Construct an addition table and a multiplication table for addition and multiplication mod 5

3) The moduli we are most interested in are prime numbers. To see one reason for this, construct the multiplication table for multiplication mod 4. (It may not be obvious from the table that there is a problem: you might want to think about the zero product property from algebra. More next time.)

4) Translate the 8 entries in the addition and multiplication tables mod 2 into statements about the sums and products of even and odd numbers: three of them are translated in the notes above.

Thinking about the problem 7^(1942) mod 100

below the fold... This is a journal-like post, where I describe my thinking as I think through the problem

Finding remainders with the help of a calculator

Most calculators will not give you remainders directly. But we can use a form of the division algorithm together with the calculator to find a remainder when the long division would be too lengthy or tedious.

To recall, the division algorithms says that for any natural numbers m and n, there are whole numbers q and r (with r<n) such that
     m = n*q + r
Solving this for r, we can rewrite it as
    r = m - n*q
In this, m is the dividend, n is the divisor (or modulus), and q is the whole-number quotient when the dividend is divided by the modulus. We will use the calculator to find q and then to find r by the formula above.

The example I worked in class was finding 884736 mod 7.
Divide 884736 by 7 on the calculator. Here the dividend m is 884736 and the divisor n is 7. The calculated quotient will contain a decimal part: 126390.857142857...
So we just ignore everything after the decimal point to get q = 126390
Note: do not round: just ignore everything after the decimal point. (This is called "truncating".)

Now we can find the remainder r:
r = 884736 - 7*126390 = 884736 - 884730 = 6

No journal submissions tomorrow

As I said in class Tuesday, there will be no journal submission tomorrow (Thursday the 22nd). It would only include one day anyway, namely Tuesday. Just include that with next week's submission.

Make sure the previous 3 weeks are posted and, if necessary, that you have gone back and corrected the file names and the summary line of your post. Double-check these things even if I have not left an answer to your post yet.

And please make sure that the posts are private!

You do not need to make new posts, you can edit the posts that you already put up (even to change them to private questions).

[Cross-posted to Piazza]

Tuesday 20 September class

Topics:
More modular arithmetic...

Activity: a more detailed version of the "odd/even/sometimes" activity from last week. We will be able to answer these questions completely using modular arithmetic (showing one application of it).

Continuing the discussion of modular arithmetic from last time:

Replacing (or better, representing) a number by its congruent residue is referred to as reducing that number. I will use that language when describing the operations below.

The modular residues for a particular modulus form a number system (technically, it's called  a ring) and since there is only a finite number of residues, we can write down complete addition and multiplication tables for all the numbers in that system. (This will be done next time.)

To add (or subtract) or multiply in these number systems, we can either reduce the numbers before we perform the operations, or perform the operations and then reduce. We saw and worked on examples which show this is true:
   In the reading, the problem of finding the units digit of a sum of four integers
    (and you can also look at the example following that one, which is of subtraction)
   We also found the product 57•93 (mod 5) in two ways: first, by multiplying and then reducing mod 5; second, by reducing mod 5 and then multiplying the residues (and then we had to reduce again). The two answers were the same (both were 1).

Another example from the reading: to find the last two digits of 7¹⁹⁴²
We computed some powers of 7 mod 100 (so the residues will be the tens and units digits) and saw that there was a pattern, that the residues mod 100 repeat the values 7, 49, 43, 1: and every time the exponent is a multiple of 4, the residue mod 100 is 1. It would be nice if our exponent 1942 were a multiple of 4, but it is not: it leaves a remainder of 2 when we divide 1942 by 4. (This means that 1942 can be expressed as 1940+2 where 1940 is a multiple of 4.) We then used that pattern to reduce 7¹⁹⁴⁰and 7² separately
We then observed that 7¹⁹⁴⁰•7² = 7¹⁹⁴² by a property of exponents. We then used that pattern we had found to reduce 7¹⁹⁴⁰and 7² separately, and so we could combine the two previous results to solve the problem. (See the reading for the details.)

Notice that in this exponentiation problem, we cannot just reduce the exponent mod 100 and then compute: it will not give the correct answer. But there is a pattern we can exploit (which actually involves mod 4 arithmetic!) and that will always be the case in this type of problem.

More on exponential expressions in modular arithmetic next time, with examples to show what does and does not work.


The operations that work well with modular arithmetic are: addition, subtraction (which is really just a version of addition, not a separate operation), multiplication, and whole number exponents (which is just repeated multiplication). Division is a problem because the result of dividing an integer by an integer may not be an integer, and we are only "allowed" to use integers in the modular arithmetic.

Homework:
The first thing to do is to go back over these examples (this time and last time) and the vocabulary/notation and make sure that you understand what we did in class. Use your Journal to write things out as necessary.

Problems to work:
1) Reduce (find the residues):
     57 ≡ ____ (mod 8)
     24 ≡ ____ (mod 6)
     3 ≡ ____ (mod 5)
     985,321 ≡ ____ (mod 1000)
2) Compute each of the following:
     56 + 113 (mod 5)
     918•46 (mod 11)
     5²⁴⁸⁷⁵⁶(mod 6)

Hint: that last one is surprisingly easy once you've found the pattern in the powers of 5 mod 6. Think about the problem in front of you, don't try to model it on anything else!

Next up: More examples, addition and multiplication tables for modular arithmetic, and later some applications of modular arithmetic: check digits for UPC, ISBN, and so forth, leading eventually to the RSA algorithm.

Test 1 logistics

Test 1 will take place in our usual classroom. However, the desks will have to be rearranged and there will be assigned seating. Therefore the test will take the whole period. 

Please make an effort to arrive on time. If you arrive while I am distributing the test papers, you will find the door locked and a sign asking you to wait until the test papers have been distributed. If this happens, please do not knock on the door, but wait quietly and I will open the door when I am finished.

(cross-posted to Piazza)

Tuesday 13 September class

Topics:
 • Theorem: the prime factorization of a natural number is unique (just stated, not proved) - this is also called the Fundamental Theorem of Arithmetic
• The division algorithm (we used to prove the missing step of the proof that there is no largest prime number): see below
 • Proving that there is no largest prime number, that is, that the number of prime numbers is infinite.

The division algorithm: (which is not really an algorithm at all)
If n and m are any natural numbers, then
       n = m•q + r
where q (for quotient) and r (for remainder) are natural numbers or 0, and r is less than m.

Comment: you already know this fact, you just may not have seen it written in algebraic language before. It is how we check a division problem when dividing with remainder.

Examples showing what the division algorithms says:  in all of these divisions, we have to forget about decimals and even fractions, and just divide natural numbers with remainders left over.

Example 1: Let n=23 and m=5. If we divide 23 by 5, 5 goes into 23 4 times and there is a remainder of 3. So the quotient here is q=4 and the remainder is r=3, and the division algorithm says
           23 = 5•4 + 3
Which is true.

Example 2: Let n=35 and m=5. If we divide 35 by 5, 5 goes into 35 7 times with remainder 0. So the division algorithm here says that
          35 = 5•7 + 0
Which is also true.

Example 3: Let n=3 and m=5. If we try to divide 3 by 5 (remember, without using decimals or fractions) we see that 5 does not "go into" 3, that is, 5 goes into 3 0 times, and the remainder is 3. So the division algorithm here says that
          3 = 5•0 + 3
Which is also true.

The last two examples show why we need to allow q and r to be 0 if necessary. Also, the remainder r is not allowed to be greater than m-1, in other words if we are dividing by 5 (as in the examples above) then the remainder must be 4 or less.

Special case:  (remainder 0) n is divisible by m if and only if n = mq for some natural number q.
(We will use this later when proving that the square root of 2 is irrational, for example.)

How the division algorithm is used in the proof that there is no largest prime number: an example
We form the number N = 2•3•5•7•11•13•17•19 + 1
We can then observe that N has remainder 1 when divided by 2, by comparing to the division algorithm:
N = 2•(3•5•7•11•13•17•19) + 1, so in the division algorithm the quotient q is the quantity in parentheses, and the remainder r is 1.
Similarly N has remainder 1 when divided by 3, because we can rearrange the factors:
N = 3•(2•5•7•11•13•17•19) + 1
And similarly N has remainder 1 when divided by 5, because we can rearrange the factors:
N = 5•(2•3•7•11•13•17•19) + 1
And so on with the other prime numbers 7 through 19. Each one gives remainder 1 when we divide by it.

• Modular arithmetic (introduction and terminology/notation)
Activity to start with: operations on even/odd numbers
• Modular arithmetic: some vocabulary and notation (from the Art of Problem Solving  reading, as well):
  modulus: the number we are "dividing out"
  residue: the remainder when dividing by the modulus
  notation: a ≡ b (mod m)
                 read it as: "a is congruent to b mod m"
                 it means: a-b is divisible by m, or equivalently, that a and b have the same remainder when divided by m
   In case b is a residue mod m, a ≡ b (mod m) means that b is the remainder when a is divided by m.

Getting used to this language/notation:

So in the example of "clock arithmetic", the modulus is 12, the possible residues are the integers 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, and 11; and we can say for example that 98 ≡ 2 (mod 12) because 2 is the remainder we get when we divide 98 by 12.

Homework:
• Journal assignment: Write out the proof that there is no largest prime number, including an explanation for how you know that N is larger than p, and how you know that N is not divisible by any of the primes 2 through p.
Problems:
1) State the division algorithm for each of the following cases:
    a) n=31, m=4 (that is, dividing 31 by 4)
    b) n=60, m=3 (that is, dividing 60 by 3)
    c) n=7, m=11 (that is, dividing 7 by 11)

Next topic: more on Modular arithmetic (reading from The Art of Problem Solving) and connecting it to the odd/even activity.

Test 1 review problems (Answers are on Piazza)

Test 1 is scheduled for Thursday 15 September. Here are the review problems for you to use to prepare:

the answers or links to answers are posted on Piazza, so I could use math notation.