30 September 2016
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.
29 September 2016
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:
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
ap-1 ≡ 1 (mod p)
In the two examples we had
a=8, p=5: 85-1 = 84 ≡ 1 (mod 5)
a=5, p=3: 53-1 = 52 ≡ 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 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!
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
ap-1 ≡ 1 (mod p)
In the two examples we had
a=8, p=5: 85-1 = 84 ≡ 1 (mod 5)
a=5, p=3: 53-1 = 52 ≡ 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.
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.
27 September 2016
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.
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 d1, d2,d3,..., d12, then the checksum is
3d1 + d2 + 3d3 + d4 + 3d5 + d6 + ... + 3d11 + d12
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.)
• 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 d1, d2,d3,..., d12, then the checksum is
3d1 + d2 + 3d3 + d4 + 3d5 + d6 + ... + 3d11 + d12
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.)
23 September 2016
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!
----------------------------------------
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
----------------------------------------
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
22 September 2016
Thursday 22 September class
Topics:
• Activity: computing 963 mod 7 two ways:
By first computing 963 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 71942 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 315 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 71942 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
Mod 2: Multiplication
Mod 3: Addition
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:
• Activity: computing 963 mod 7 two ways:
By first computing 963 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 71942 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 315 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 71942 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 |
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 963 (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.
Homework:
• Journal assignment: Write about the group activity (computing 963 (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
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
21 September 2016
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]
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]
20 September 2016
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 71942
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 71940and 72 separately
We then observed that 71940•72 = 71942 by a property of exponents. We then used that pattern we had found to reduce 71940and 72 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)
5248756(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.
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 71942
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 71940and 72 separately
We then observed that 71940•72 = 71942 by a property of exponents. We then used that pattern we had found to reduce 71940and 72 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)
5248756(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.
15 September 2016
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)
13 September 2016
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.
(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.
• 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.
Special case: (remainder 0) n is divisible by m if and only if n = mq for some natural number q.
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.
(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.
12 September 2016
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.
the answers or links to answers are posted on Piazza, so I could use math notation.
08 September 2016
How to scan and submit your Journal pages (with important note!) - UPDATED and bumped to the top
**There are two changes to the instructions below, starting with Journal2. They are marked with double stars!**
Important note: all of the journal pages you submit each week should be contained in one single file, numbered according to the week! And make sure that you are submitting EVERYTHING that is supposed to be in the journal!
Submitting your journal pages:
First of all, make sure that you know what your journal is supposed to contain: read the syllabus!
Each time I ask you to submit, you will submit the pages of the journal which are new since the last time you submitted.
The pages must be scanned, not merely photographed, and saved as one single pdf file. jpg files or any other file type are not acceptable.
However you scan your journal pages, you are responsible for making sure that the result is clearly legible and is saved with the appropriate file name in pdf form.
You must save the file containing the scanned pages using the following name format:
Lastname-firstname-Math1311-Journal-number.pdf
For example, Joe Seeley would save his first journal submission under the name
Seeley-Joe-Math1311-Journal-1.pdf
and his second journal submission would be
Seeley-Joe-Math1311-Journal-2.pdf
Important note: Your file MUST have its filename in that format. If you forgot to name it that way when you scanned it, make sure to change the name before you submit it.
Double-check that your file is easily legible and contains all the things you intend it to contain before you post it.
Post the file containing your Journal pages to Piazza as a **Private Question** (not a Note) to me.
**Make sure that the "Summary" line includes your name and the number of the journal submission; for example Joe Seeley could use the Summary line Joe Seeley Journal 2 for his second Journal submission.**
Put it in the Journals folder when you post it.
-------------------------------------------------------------------------------------------
There are several ways you can scan the pages:
• There are free scanner apps available for smart phones or iPads. Two which have received consistently good reviews and which I have tried out are: CamScanner, and Genius Scan. They are both available for iPhones and Android phones and, I believe, for Windows phones as well (and for iPad). Specific instructions for each of these will be posted as I get them written up, but they are both fairly easy to learn to use.
• There are scanners available for your use in several Brooklyn College Library locations:
The self-service scanners are located in the following areas of the Library and Library Café:
• Lower Level
• 1st Floor
• New Media Center (2nd Floor)
• Library Cafe
Please see the staff member at the appropriate service desk for assistance in obtaining and using a scanner.
Important note: all of the journal pages you submit each week should be contained in one single file, numbered according to the week! And make sure that you are submitting EVERYTHING that is supposed to be in the journal!
Submitting your journal pages:
First of all, make sure that you know what your journal is supposed to contain: read the syllabus!
Each time I ask you to submit, you will submit the pages of the journal which are new since the last time you submitted.
The pages must be scanned, not merely photographed, and saved as one single pdf file. jpg files or any other file type are not acceptable.
However you scan your journal pages, you are responsible for making sure that the result is clearly legible and is saved with the appropriate file name in pdf form.
You must save the file containing the scanned pages using the following name format:
Lastname-firstname-Math1311-Journal-number.pdf
For example, Joe Seeley would save his first journal submission under the name
Seeley-Joe-Math1311-Journal-1.pdf
and his second journal submission would be
Seeley-Joe-Math1311-Journal-2.pdf
Important note: Your file MUST have its filename in that format. If you forgot to name it that way when you scanned it, make sure to change the name before you submit it.
Double-check that your file is easily legible and contains all the things you intend it to contain before you post it.
Post the file containing your Journal pages to Piazza as a **Private Question** (not a Note) to me.
**Make sure that the "Summary" line includes your name and the number of the journal submission; for example Joe Seeley could use the Summary line Joe Seeley Journal 2 for his second Journal submission.**
Put it in the Journals folder when you post it.
-------------------------------------------------------------------------------------------
There are several ways you can scan the pages:
• There are free scanner apps available for smart phones or iPads. Two which have received consistently good reviews and which I have tried out are: CamScanner, and Genius Scan. They are both available for iPhones and Android phones and, I believe, for Windows phones as well (and for iPad). Specific instructions for each of these will be posted as I get them written up, but they are both fairly easy to learn to use.
• There are scanners available for your use in several Brooklyn College Library locations:
The self-service scanners are located in the following areas of the Library and Library Café:
• Lower Level
• 1st Floor
• New Media Center (2nd Floor)
• Library Cafe
Please see the staff member at the appropriate service desk for assistance in obtaining and using a scanner.
Thursday 8 September class
Topics:
• We discussed some of the homework problems: the socks problems from the second day (30 August) and the algebraic problems from last time.
Most of this is from the reading: prime numbers and prime factorization of natural numbers (from Math is Fun), except when other links are provided.
• What is a prime number?
Note: divisibility rules are linked at the end of the reading from Math is Fun
• Finding prime numbers using the sieve of Eratosthenes: here is the grid that I printed out
• Finding the prime factorization of a natural number (this is done in the reading)
Homework:
• Journal assignment: write a definition of prime number. Explain in your own words what the prime factorization of a natural number is: give at least 3 examples to illustrate it.
Problems:
Find (by hand, using any of the methods we discussed in class) the prime factorization of each of these numbers:
30, 48, 143, 41
Next topic: We will state the Fundamental Theorem of Arithmetic, and then prove that there are infinitely many prime numbers (here's another description of the proof). Along the way we encounter the Division Algorithm, which explains one of the steps in that proof.
• We discussed some of the homework problems: the socks problems from the second day (30 August) and the algebraic problems from last time.
If you need more review of using the quadratic formula, here are some good sources:New topic: Prime numbers and Prime Factorization
Webpages: Regents Prep (good explanation), Algebra Lab (this has practice problems where you can enter your answer and it checks it - excellent for practice!)
Videos: Khan Academy, Patrick's Just Math Tutorials (this link is to Example 1; there are links below the video to two more examples)
Most of this is from the reading: prime numbers and prime factorization of natural numbers (from Math is Fun), except when other links are provided.
• What is a prime number?
Note: divisibility rules are linked at the end of the reading from Math is Fun
• Finding prime numbers using the sieve of Eratosthenes: here is the grid that I printed out
• Finding the prime factorization of a natural number (this is done in the reading)
Homework:
• Journal assignment: write a definition of prime number. Explain in your own words what the prime factorization of a natural number is: give at least 3 examples to illustrate it.
Problems:
Find (by hand, using any of the methods we discussed in class) the prime factorization of each of these numbers:
30, 48, 143, 41
Next topic: We will state the Fundamental Theorem of Arithmetic, and then prove that there are infinitely many prime numbers (here's another description of the proof). Along the way we encounter the Division Algorithm, which explains one of the steps in that proof.
06 September 2016
Tuesday 6 September class
Topics: more properties of Fibonacci sequence and similar sequences
• Activity: can you write these numbers as sums of distinct Fibonacci numbers?
• Theorem: any natural number can be written as a sum of one or more non-consecutive Fibonacci numbers. Also, there is only one way to do this. (This is called Zeckendorf's Theorem)
• Looking at the ratios of consecutive Fibonacci numbers, we previously saw they approach a number we call "the Golden Ratio"
which will turn out to be irrational (more on this later).
• A "Fibonacci-like" sequence starting with any two randomly selected natural numbers (in place of 1 and 1) will have its ratios approach the same value
• A continued fraction representation of
: Here is a video which shows the continued fraction being developed, by Michael McCafferty. (You could stop watching at about 2:00 when he has finished the continued fraction, or go on as he explains more advanced properties.)
• From this we learn that satisfies the equation
which we can solve to find the exact value
What is important to get from each of these: (some of this I mentioned last time)
• You should know how to get the next number in the Fibonacci sequence (or any Fibonacci-like sequence) by adding together the two previous numbers
• You should make sure to understand how the algebraic formula an = an-1 + an-2 represents that rule
• You should understand how we computed the ratios of successive Fibonacci numbers and how we concluded that those ratios were approaching a single number as we went farther and farther out
• Same thing for the "Fibonacci-like" example in the reading which started with 192 and 16
• Make sure that you see how the Fibonacci numbers and the spiral are being shown in the examples from nature: the sunflower seed head and the chambered nautilus shell in particular
• Understand how we got the continued fraction representation of and that the fact that it contains only 1's means that is very special indeed
• Know how to solve the equation to find the exact value of (including why we choose the + sign in the quadratic formula).
We will be going into more detail about rational and irrational numbers later in the course, and will prove that the square root of 5 is irrational, so that will prove that is also irrational. For now it is enough to know that a rational number is a number that can be written in the form of a fraction, and that the decimal expansion of a rational number either terminates or eventually repeats.
Homework:
Journal assignment:
Use your journal to start work on understanding each of the points above on the topic of Fibonacci numbers. Describe any part that seems unclear to you and try to work it out, possibly by discussion on the Piazza discussion board. (Don't worry if you don't get this totally understood by next time; it's just important to identify what you need to work on and to get started on it. The homework problems below may help with some things.)
Homework problems: (the first one was assigned last time, I'm just repeating it herre)
1) Choose any two natural numbers (not 1 and 1, and not 192 and 16, but some other pair, preferably not too big) and make the "Fibonacci-like" sequence starting with them. Write down at least the first 10 numbers in the sequence. Then compute the ratios of successive numbers in your sequence, as we did for the Fibonacci numbers. Do your ratios appear to be approaching? Why or why not?
2) We can verify that
by simplifying "from the inside out":
Do the same to simplify
3) Now simplify
4) Solve for x:
5) Solve for x:
Reading for tomorrow: We will start a new topic, prime numbers and prime factorization of natural numbers (from Math is Fun). This will lead eventually to discussion of public-key cryptography, a very important (and lucrative!) application of number theory. Something to look forward to.
• Activity: can you write these numbers as sums of distinct Fibonacci numbers?
• Theorem: any natural number can be written as a sum of one or more non-consecutive Fibonacci numbers. Also, there is only one way to do this. (This is called Zeckendorf's Theorem)
• Looking at the ratios of consecutive Fibonacci numbers, we previously saw they approach a number we call "the Golden Ratio"
which will turn out to be irrational (more on this later).• A "Fibonacci-like" sequence starting with any two randomly selected natural numbers (in place of 1 and 1) will have its ratios approach the same value
• A continued fraction representation of
: Here is a video which shows the continued fraction being developed, by Michael McCafferty. (You could stop watching at about 2:00 when he has finished the continued fraction, or go on as he explains more advanced properties.)• From this we learn that
satisfies the equationwhich we can solve to find the exact value
What is important to get from each of these: (some of this I mentioned last time)
• You should know how to get the next number in the Fibonacci sequence (or any Fibonacci-like sequence) by adding together the two previous numbers
• You should make sure to understand how the algebraic formula an = an-1 + an-2 represents that rule
• You should understand how we computed the ratios of successive Fibonacci numbers and how we concluded that those ratios were approaching a single number as we went farther and farther out
• Same thing for the "Fibonacci-like" example in the reading which started with 192 and 16
• Make sure that you see how the Fibonacci numbers and the spiral are being shown in the examples from nature: the sunflower seed head and the chambered nautilus shell in particular
• Understand how we got the continued fraction representation of
and that the fact that it contains only 1's means that is very special indeed• Know how to solve the equation to find the exact value of
(including why we choose the + sign in the quadratic formula).We will be going into more detail about rational and irrational numbers later in the course, and will prove that the square root of 5 is irrational, so that will prove that
is also irrational. For now it is enough to know that a rational number is a number that can be written in the form of a fraction, and that the decimal expansion of a rational number either terminates or eventually repeats.Homework:
Journal assignment:
Use your journal to start work on understanding each of the points above on the topic of Fibonacci numbers. Describe any part that seems unclear to you and try to work it out, possibly by discussion on the Piazza discussion board. (Don't worry if you don't get this totally understood by next time; it's just important to identify what you need to work on and to get started on it. The homework problems below may help with some things.)
Homework problems: (the first one was assigned last time, I'm just repeating it herre)
1) Choose any two natural numbers (not 1 and 1, and not 192 and 16, but some other pair, preferably not too big) and make the "Fibonacci-like" sequence starting with them. Write down at least the first 10 numbers in the sequence. Then compute the ratios of successive numbers in your sequence, as we did for the Fibonacci numbers. Do your ratios appear to be approaching
? Why or why not?2) We can verify that
Do the same to simplify
3) Now simplify
4) Solve for x:
5) Solve for x:
Reading for tomorrow: We will start a new topic, prime numbers and prime factorization of natural numbers (from Math is Fun). This will lead eventually to discussion of public-key cryptography, a very important (and lucrative!) application of number theory. Something to look forward to.
02 September 2016
Thursday 1 September class
• Activity: Pigeonhole principle statements and mis-statements. Here is the handout. We did not finish all of these in class: you should look at the rest of them at home.
• Fibonacci numbers: beginning with the reading from Math is Fun.
- How to get the next number in the sequence by adding together the two previous numbers
- A spiral that is constructed on squares whose side lengths are the Fibonacci numbers
- Subscript notation so we can write the above rule in algebraic form: $a_n = a_{n-1} + a_{n-2}$
- Looking at the ratios of consecutive Fibonacci numbers, they approach a number we call "the Golden Ratio" $\varphi \approx 1.618$ which will turn out to be irrational (more on this later).
- Fibonacci numbers in nature [the link I used: Math is Fun, also look at Fibonacci Numbers and Nature]
- A beautiful video showing many real-world instances related to Fibonacci numbers, the Golden Ratio, and things that follow from them: Nature by Numbers, by Cristobal Vila
What is important to get from each of these:
• You should know how to get the next number in the Fibonacci sequence (or any Fibonacci-like sequence) by adding together the two previous numbers
• You should make sure to understand how the algebraic formula $a_n = a_{n-1} + a_{n-2}$ represents that rule
• You should understand how we computed the ratios of successive Fibonacci numbers and how we concluded that those ratios were approaching a single number as we went farther and farther out
• Make sure that you see how the Fibonacci numbers and the spiral are being shown in the examples from nature: the sunflower seed head and the chambered nautilus shell in particular
We will be going into more detail about rational and irrational numbers later in the course, and will prove that $\sqrt{5}$ is irrational, so that will prove that $\varphi$ is also irrational. For now it is enough to know that a rational number is a number that can be written in the form of a fraction, and that the decimal expansion of a rational number either terminates or eventually repeats.
Homework:
Journal assignment:
Record any new thing you learned from the homework discussion today.
Use your journal to start work on understanding each of the points above on the topic of Fibonacci numbers. Describe any part that seems unclear to you and try to work it out, possibly by discussion on the Piazza discussion board. (Don't worry if you don't get this totally understood by next time it's just important to identify what you need to work on and to get started on it. The homework problems below may help with some things.)
Homework problem:
Choose any two natural numbers (not 1 and 1, but some other pair) and make the "Fibonacci-like" sequence starting with them and using the Fibonacci rule to get the next number. Write down at least the first 10 numbers in the sequence. Then compute the ratios of successive numbers in your sequence, as we did for the Fibonacci numbers. Do your ratios appear to be approaching $\varphi$? Why or why not?
Reading for next time: We will find a continued fraction expansion for the Golden Ratio, which leads to an equation we can solve to find its exact value (which is, alas, irrational). I'm still looking for sources for this, so no links yet, sorry.
• Fibonacci numbers: beginning with the reading from Math is Fun.
- How to get the next number in the sequence by adding together the two previous numbers
- A spiral that is constructed on squares whose side lengths are the Fibonacci numbers
- Subscript notation so we can write the above rule in algebraic form: $a_n = a_{n-1} + a_{n-2}$
- Looking at the ratios of consecutive Fibonacci numbers, they approach a number we call "the Golden Ratio" $\varphi \approx 1.618$ which will turn out to be irrational (more on this later).
- Fibonacci numbers in nature [the link I used: Math is Fun, also look at Fibonacci Numbers and Nature]
- A beautiful video showing many real-world instances related to Fibonacci numbers, the Golden Ratio, and things that follow from them: Nature by Numbers, by Cristobal Vila
What is important to get from each of these:
• You should know how to get the next number in the Fibonacci sequence (or any Fibonacci-like sequence) by adding together the two previous numbers
• You should make sure to understand how the algebraic formula $a_n = a_{n-1} + a_{n-2}$ represents that rule
• You should understand how we computed the ratios of successive Fibonacci numbers and how we concluded that those ratios were approaching a single number as we went farther and farther out
• Make sure that you see how the Fibonacci numbers and the spiral are being shown in the examples from nature: the sunflower seed head and the chambered nautilus shell in particular
We will be going into more detail about rational and irrational numbers later in the course, and will prove that $\sqrt{5}$ is irrational, so that will prove that $\varphi$ is also irrational. For now it is enough to know that a rational number is a number that can be written in the form of a fraction, and that the decimal expansion of a rational number either terminates or eventually repeats.
Homework:
Journal assignment:
Record any new thing you learned from the homework discussion today.
Use your journal to start work on understanding each of the points above on the topic of Fibonacci numbers. Describe any part that seems unclear to you and try to work it out, possibly by discussion on the Piazza discussion board. (Don't worry if you don't get this totally understood by next time it's just important to identify what you need to work on and to get started on it. The homework problems below may help with some things.)
Homework problem:
Choose any two natural numbers (not 1 and 1, but some other pair) and make the "Fibonacci-like" sequence starting with them and using the Fibonacci rule to get the next number. Write down at least the first 10 numbers in the sequence. Then compute the ratios of successive numbers in your sequence, as we did for the Fibonacci numbers. Do your ratios appear to be approaching $\varphi$? Why or why not?
Reading for next time: We will find a continued fraction expansion for the Golden Ratio, which leads to an equation we can solve to find its exact value (which is, alas, irrational). I'm still looking for sources for this, so no links yet, sorry.
01 September 2016
Using Genius Scan to scan and post Journals to Piazza
In most ways I prefer Genius Scan to CamScanner (slightly prefer, let's say), but one thing I do not like is that there does not seem to be any way to delete a document in Genius Scan! All you can do is delete all the pages in the document, but the document remains cluttering up your Documents screen. Oh well.
Note: I'm posting this now without illustrations, just so I can get it up. I will put in the illustrations when I have time to get them from my phone.
(In the illustrations, I'm scanning the syllabus for this class page by page to show you how it's done.)
Always before scanning, try to have a nice flat surface, preferably of a color other than white, to place your pages on. This is not strictly necessary but it helps.
(Note: when you first open Genius Scan , you may see a screen that asks you to sign in or register. Just ignore those choices and move on, if that happens.)
Put your first page flat on your surface. Now you will touch the camera icon at the bottom of the screen:
Position the camera so that you can see the entire page. Notice that you don't necessarily have to hold the camera parallel to the document: the scanner will take care of that later.
Notice that Genius Scan has automatically outlined the document's edges in orange. When it is ready to scan the little rotating circle icon will be totally surrounded, and the scan will be done automatically: no need for you to press the button! Notice then that Genius Scan has corrected the perspective. (THIS is a big reason why you want a scan and not a photo! It is always best to take the scan as close to parallel as possible, but it is not necessary to be precise, as it would be if you were taking a photo.)
Now I can edit the scanned page to make it clearer, but I am happy with it like this.
When I am happy with the appearance of this page, I will touch Save, save to New Document, and then add the next page: notice that the document is automatically given a name which is the date and time it was created. Just leave this for now and go back to Documents.
Set up the next page, and then touch the camera icon at the lower left of the screen to add the next page. When its image is ready, I touch Save but I will add it to the Existing Document. I continue adding pages until they are all added and ready to go.
I want to name this document "Shaver-Sybil-Math1311-Journal -1" (that's not what it really is, but remember that is the way you should be naming your journal submission) so I touch the document in the Documents screen and then touch its name at the top of the screen. Delete the old name and type the new one in. (You don't have to capitalize, but please put in the dashes where I've indicated.) And touch "Done".
I'm now going to share it via Piazza. I touch the Upload icon (box with an arrow coming out of the top) at the bottom right of the screen. I see this:
I touch the "Other Apps" and then swipe left until I see the Piazza icon. And touch it. Log in to Piazza if necessary.
I touch the new post icon at the bottom right in Piazza, post as New Note
My Note Summary is "Journal 1". I type in something (it doesn't matter what) into the Note Details, because Piazza won't let you leave this blank even if you are posting a file. Then touch Next and add folder "journals", go back < and add file, choose the file that I just shared from Genius Scan.
Touch Done. Now I go to Post to... because I want this to be a private post. I change it to post to Individuals. I then add the individual (myself, in this case) that I want to post to: that means that I choose "All Instructors".
Then "Done" and "Post"
Don't omit any of these steps in Piazza, they are all necessary!
Note: I'm posting this now without illustrations, just so I can get it up. I will put in the illustrations when I have time to get them from my phone.
(In the illustrations, I'm scanning the syllabus for this class page by page to show you how it's done.)
Always before scanning, try to have a nice flat surface, preferably of a color other than white, to place your pages on. This is not strictly necessary but it helps.
(Note: when you first open Genius Scan , you may see a screen that asks you to sign in or register. Just ignore those choices and move on, if that happens.)
Put your first page flat on your surface. Now you will touch the camera icon at the bottom of the screen:
Position the camera so that you can see the entire page. Notice that you don't necessarily have to hold the camera parallel to the document: the scanner will take care of that later.
Notice that Genius Scan has automatically outlined the document's edges in orange. When it is ready to scan the little rotating circle icon will be totally surrounded, and the scan will be done automatically: no need for you to press the button! Notice then that Genius Scan has corrected the perspective. (THIS is a big reason why you want a scan and not a photo! It is always best to take the scan as close to parallel as possible, but it is not necessary to be precise, as it would be if you were taking a photo.)
Now I can edit the scanned page to make it clearer, but I am happy with it like this.
When I am happy with the appearance of this page, I will touch Save, save to New Document, and then add the next page: notice that the document is automatically given a name which is the date and time it was created. Just leave this for now and go back to Documents.
Set up the next page, and then touch the camera icon at the lower left of the screen to add the next page. When its image is ready, I touch Save but I will add it to the Existing Document. I continue adding pages until they are all added and ready to go.
I want to name this document "Shaver-Sybil-Math1311-Journal -1" (that's not what it really is, but remember that is the way you should be naming your journal submission) so I touch the document in the Documents screen and then touch its name at the top of the screen. Delete the old name and type the new one in. (You don't have to capitalize, but please put in the dashes where I've indicated.) And touch "Done".
I'm now going to share it via Piazza. I touch the Upload icon (box with an arrow coming out of the top) at the bottom right of the screen. I see this:
I touch the "Other Apps" and then swipe left until I see the Piazza icon. And touch it. Log in to Piazza if necessary.
I touch the new post icon at the bottom right in Piazza, post as New Note
My Note Summary is "Journal 1". I type in something (it doesn't matter what) into the Note Details, because Piazza won't let you leave this blank even if you are posting a file. Then touch Next and add folder "journals", go back < and add file, choose the file that I just shared from Genius Scan.
Touch Done. Now I go to Post to... because I want this to be a private post. I change it to post to Individuals. I then add the individual (myself, in this case) that I want to post to: that means that I choose "All Instructors".
Then "Done" and "Post"
Don't omit any of these steps in Piazza, they are all necessary!
Using CamScanner to scan Journal and post to Piazza
Note: I'm posting this now without illustrations, just so I can get it up. I will put in the illustrations when I have time to get them from my phone.
(In the illustrations, I'm scanning the syllabus for this class page by page to show you how it's done.)
Always before scanning, try to have a nice flat surface, preferably of a color other than white, to place your pages on. This is not strictly necessary but it helps.
(Note: when you first open CamScanner, you may see a screen that asks you to sign in or register. Just ignore those choices and move on, if that happens.)
Put your first page flat on your surface. Now you will touch the camera icon at the bottom of the screen:
Position the camera so that you can see the entire page. Notice that you don't necessarily have to hold the camera parallel to the document: the scanner will take care of that later. When you are ready, push the button to take the picture:
Notice that CamScanner has outlined the document's edges. If necessary, you can correct that outline by touching and dragging the dots you see around the edge. But this one looks OK, so I will proceed.
Touch the checkmark at the lower right when the outline is correct:
Notice that CamScanner has corrected the perspective. (THIS is a big reason why you want a scan and not a photo! It is always best to take the scan as close to parallel as possible, but it is not necessary to be precise, as it would be if you were taking a photo.)
Now I can edit the scanned page to make it clearer. I see that it looks a little pale in the B&W choice along the bottom. Going back to Original I see this:
When I am happy with the appearance of this page, I will touch the checkmark, and then add the next page:
Set up the next page, and then Touch the "Add" camera icon at the lower left of the screen to add the next page. I then proceed as before to edit that page and check it off, and add pages until I have added all the pages I want. Now I have this:
My document at this point has the name "new doc 1" and has 4 pages. To change the name, I touch the name "new doc 1" and it pulls up a Rename dialog:
I want to name this document "Shaver-Sybil-Math1311-Journal -1" (that's not what it really is, but remember that is the way you should be naming your journal submission) so I type that in. (You don't have to capitalize, but please put in the dashes where I've indicated.)
And touch "OK". Now I want to preview it, so I touch "More..." at the lower right of the screen and I see this:
Touching "PDF Preview" lets me see what it will look like. (This one actually looks pretty bad, because I had my flash turned off when I took the scans. Take my advice and use your flash! Bright lighting also helps.)
I'm now going to share it via Piazza. I touch the "<Back" at the top left of the screen and then Cancel the actions to get back to the sharing screen:
Touch "Share" at the bottom of the screen and I see this:
By swiping left I can move over until I see the Piazza icon. Touch it, then sign in to Piazza if necessary,
I touch the new post icon at the bottom right in Piazza, post as New Note
My Note Summary is "Journal 1". I type in something (it doesn't matter what) into the Note Details, because Piazza won't let you leave this blank even if you are posting a file. Then touch Next and add folder "journals", go back < and add file, choose the file that I just shared from CamScanner. (You will notice at this point that CamScanner has appended a lot of numbers at the end if the file name. They are the date and time that the file was created, and I know of no way to keep them from showing up, so don't worry about them for now. This is one thing I do not like about CamScanner.)
Touch Done. Now I go to Post to... because I want this to be a private post. I change it to post to Individuals. I then add the individual (myself, in this case) that I want to post to: that means that I choose "All Instructors".
Then "Done" and "Post"
Don't omit any of these steps in Piazza, they are all necessary!
(In the illustrations, I'm scanning the syllabus for this class page by page to show you how it's done.)
Always before scanning, try to have a nice flat surface, preferably of a color other than white, to place your pages on. This is not strictly necessary but it helps.
(Note: when you first open CamScanner, you may see a screen that asks you to sign in or register. Just ignore those choices and move on, if that happens.)
Put your first page flat on your surface. Now you will touch the camera icon at the bottom of the screen:
Position the camera so that you can see the entire page. Notice that you don't necessarily have to hold the camera parallel to the document: the scanner will take care of that later. When you are ready, push the button to take the picture:
Notice that CamScanner has outlined the document's edges. If necessary, you can correct that outline by touching and dragging the dots you see around the edge. But this one looks OK, so I will proceed.
Touch the checkmark at the lower right when the outline is correct:
Notice that CamScanner has corrected the perspective. (THIS is a big reason why you want a scan and not a photo! It is always best to take the scan as close to parallel as possible, but it is not necessary to be precise, as it would be if you were taking a photo.)
Now I can edit the scanned page to make it clearer. I see that it looks a little pale in the B&W choice along the bottom. Going back to Original I see this:
When I am happy with the appearance of this page, I will touch the checkmark, and then add the next page:
Set up the next page, and then Touch the "Add" camera icon at the lower left of the screen to add the next page. I then proceed as before to edit that page and check it off, and add pages until I have added all the pages I want. Now I have this:
My document at this point has the name "new doc 1" and has 4 pages. To change the name, I touch the name "new doc 1" and it pulls up a Rename dialog:
I want to name this document "Shaver-Sybil-Math1311-Journal -1" (that's not what it really is, but remember that is the way you should be naming your journal submission) so I type that in. (You don't have to capitalize, but please put in the dashes where I've indicated.)
And touch "OK". Now I want to preview it, so I touch "More..." at the lower right of the screen and I see this:
Touching "PDF Preview" lets me see what it will look like. (This one actually looks pretty bad, because I had my flash turned off when I took the scans. Take my advice and use your flash! Bright lighting also helps.)
I'm now going to share it via Piazza. I touch the "<Back" at the top left of the screen and then Cancel the actions to get back to the sharing screen:
Touch "Share" at the bottom of the screen and I see this:
By swiping left I can move over until I see the Piazza icon. Touch it, then sign in to Piazza if necessary,
I touch the new post icon at the bottom right in Piazza, post as New Note
My Note Summary is "Journal 1". I type in something (it doesn't matter what) into the Note Details, because Piazza won't let you leave this blank even if you are posting a file. Then touch Next and add folder "journals", go back < and add file, choose the file that I just shared from CamScanner. (You will notice at this point that CamScanner has appended a lot of numbers at the end if the file name. They are the date and time that the file was created, and I know of no way to keep them from showing up, so don't worry about them for now. This is one thing I do not like about CamScanner.)
Touch Done. Now I go to Post to... because I want this to be a private post. I change it to post to Individuals. I then add the individual (myself, in this case) that I want to post to: that means that I choose "All Instructors".
Then "Done" and "Post"
Don't omit any of these steps in Piazza, they are all necessary!