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.)
27 October 2016
20 October 2016
Thursday 20 October class
Topic:
Outlining the "proof" that the RSA works, for the example given in my notes.
This is not a real proof (hence the scare quotes above), because it only proves that RSA works for this particular example. However, if you read carefully, you can see that nothing in the proof depends on the specific numbers we use, but only on their relationship to each other. (UPDATE: here are the revised notes. I hope they are a bit clearer: certainly they are longer!)
The essential thing we are trying to prove is this:
If we encode a message, and then decode it, we come back to the original message.
In the example, the message was the number 71.
The public keys were the numbers 143 = 11*13 (the modulus) and 7 (the exponent).
To find 143, we chose two prime numbers and multiplied them together.
Then we had to compute the number (11-1)*(13-1) = 120 and choose the exponent so that it had no factors in common with that number 120.
The private key was the number 103. This number came from solving the Diophantine equation ed-my=1, or equivalently, from solving the modular congruence ed ≡ 1 (mod m), where e=7 (our public key exponent) and m = 120 (the number that e was chosen to have no factors in common with).
What we want to prove in the example is that if we encode the message 71 by taking 717 (mod 143), and then decode that encoded message by taking it to the 103rd power (mod 143), we get back the original message 71.
In other words, we want to prove (without actually computing it) that
(717)103 ≡ 71 (mod 143)
Here are the essential steps of the proof:
• Prove that 717 ≡ 124 (mod 143) means that 717 ≡ 124 (mod 11) and 717 ≡ 124 (mod 13)
[This is a special case of a general theorem: if two numbers are equivalent mod n, then they are also equivalent modulo any prime factor of n.]
• Prove that (717)103 ≡ 71 (mod 11) using Fermat's Little Theorem
• This means that (717)103 - 71 is divisible by 11 (division algorithm)
• Prove that (717)103 ≡ 71 (mod 13) using Fermat's Little Theorem
• This means that (717)103 - 71 is divisible by 13 (division algorithm0
• Since (717)103 - 71 is divisible by both 11 and 13, it must be divisible by their product 143 (Here we use Unique Prime Factorization, a/k/a the Fundamental Theorem of Arithmetic.)
• So (717)103 ≡ 71 (mod 143)
Outlining the "proof" that the RSA works, for the example given in my notes.
This is not a real proof (hence the scare quotes above), because it only proves that RSA works for this particular example. However, if you read carefully, you can see that nothing in the proof depends on the specific numbers we use, but only on their relationship to each other. (UPDATE: here are the revised notes. I hope they are a bit clearer: certainly they are longer!)
The essential thing we are trying to prove is this:
If we encode a message, and then decode it, we come back to the original message.
In the example, the message was the number 71.
The public keys were the numbers 143 = 11*13 (the modulus) and 7 (the exponent).
To find 143, we chose two prime numbers and multiplied them together.
Then we had to compute the number (11-1)*(13-1) = 120 and choose the exponent so that it had no factors in common with that number 120.
The private key was the number 103. This number came from solving the Diophantine equation ed-my=1, or equivalently, from solving the modular congruence ed ≡ 1 (mod m), where e=7 (our public key exponent) and m = 120 (the number that e was chosen to have no factors in common with).
What we want to prove in the example is that if we encode the message 71 by taking 717 (mod 143), and then decode that encoded message by taking it to the 103rd power (mod 143), we get back the original message 71.
In other words, we want to prove (without actually computing it) that
(717)103 ≡ 71 (mod 143)
Here are the essential steps of the proof:
• Prove that 717 ≡ 124 (mod 143) means that 717 ≡ 124 (mod 11) and 717 ≡ 124 (mod 13)
[This is a special case of a general theorem: if two numbers are equivalent mod n, then they are also equivalent modulo any prime factor of n.]
• Prove that (717)103 ≡ 71 (mod 11) using Fermat's Little Theorem
• This means that (717)103 - 71 is divisible by 11 (division algorithm)
• Prove that (717)103 ≡ 71 (mod 13) using Fermat's Little Theorem
• This means that (717)103 - 71 is divisible by 13 (division algorithm0
• Since (717)103 - 71 is divisible by both 11 and 13, it must be divisible by their product 143 (Here we use Unique Prime Factorization, a/k/a the Fundamental Theorem of Arithmetic.)
• So (717)103 ≡ 71 (mod 143)
13 October 2016
Thursday 13 October class
Note: No journals are due this week. Hold on till next week.
Also don't forget that this class will not meet on Tuesday the 18th of October!
After Test 2 our next meeting will be Thursday the 20th.
Topics:
• Activity related to the video on Fermat's Little Theorem linked in last time's post.
• Review of reasoning I used in computing 71492 (mod 100) (to remind that we could not just reduce the exponent mod 100) - see more on this below
• Showing why the RSA algorithm works (from my notes) - we only got through the first part of the proof on p. 3 of these notes, so it will continue next time.
More comments on the problem of computing exponential expressions in modular arithmetic:
I asserted and also gave an example in class to show that you cannot reduce the exponent (at least, not to the modulus you are starting with). I do not know if I wrote up my example in the blog, so here is an example (which may or may not be the one I did in class):
Suppose we want to compute 318 (mod 5).
This can be found with a calculator by computing 318 = 387420489, and then reducing mod 5, so we get 318 ≡ 4 (mod 5).
But if we try to shortcut by reducing the exponent mod 5, we get 18 ≡ 3 (mod 5), so we would think that our answer could be computed by taking 33 = 27 ≡ 2 (mod 5), which is not the correct answer.
Referring back to this post (or to the reading from Art of Problem Solving), the cases where we can reduce before performing the computations (and then reduce again, if necessary) are these:
• In addition or subtraction, we can reduce the numbers before adding or subtracting
• In multiplication, we can reduce the numbers before multiplying - (please note that there is no division in modular arithmetic)
• Because we can reduce factors before we multiply them together, we can reduce the base of a natural number exponent (since the base represents the factor which is being repeatedly multiplied together) before taking the power.
When it is the exponent which is "too big", other tricks must be used, such as looking for patterns in the powers of the base (as in the example of 71492) or using Fermat's Little Theorem (which is a special case of looking for patterns in the powers.)
Homework:
• Journal assignment: watch the video on Fermat's Little Theorem (which was assigned previously!), write on what you learn from it, and then use that to try the Activity again.
• Problems related to Fermat's Little Theorem:
1) Compute each of the following:
a) 14 (mod 5), 24 (mod 5), 34 (mod 5), 44 (mod 5)
b) 16 (mod 7), 26 (mod 7), 36 (mod 7), 46 (mod 7), 56 (mod 7), 66 (mod 7)
c) How does Fermat's Little Theorem relate to the answers in (a) and (b)?
2a) Using Fermat's Little Theorem (not by direct computation), find 800030 (mod 31). You must verify that the conditions are correct to use the theorem in this problem.
b) Compute 80004 (mod 5). The answer is not 1. Why doesn't this contradict Fermat's LittleTheorem?
Up next: Completing the verification of the RSA algorithm (showing why it works). Reread the part of the proof on p. 3 of the notes and make sure that you are following the reasoning being used at each step (even if you don't see where it is going yet). Next time we will outline or "flowchart" the proof to get a better idea of how it fits together.
Also don't forget that this class will not meet on Tuesday the 18th of October!
After Test 2 our next meeting will be Thursday the 20th.
Topics:
• Activity related to the video on Fermat's Little Theorem linked in last time's post.
• Review of reasoning I used in computing 71492 (mod 100) (to remind that we could not just reduce the exponent mod 100) - see more on this below
• Showing why the RSA algorithm works (from my notes) - we only got through the first part of the proof on p. 3 of these notes, so it will continue next time.
More comments on the problem of computing exponential expressions in modular arithmetic:
I asserted and also gave an example in class to show that you cannot reduce the exponent (at least, not to the modulus you are starting with). I do not know if I wrote up my example in the blog, so here is an example (which may or may not be the one I did in class):
Suppose we want to compute 318 (mod 5).
This can be found with a calculator by computing 318 = 387420489, and then reducing mod 5, so we get 318 ≡ 4 (mod 5).
But if we try to shortcut by reducing the exponent mod 5, we get 18 ≡ 3 (mod 5), so we would think that our answer could be computed by taking 33 = 27 ≡ 2 (mod 5), which is not the correct answer.
Referring back to this post (or to the reading from Art of Problem Solving), the cases where we can reduce before performing the computations (and then reduce again, if necessary) are these:
• In addition or subtraction, we can reduce the numbers before adding or subtracting
• In multiplication, we can reduce the numbers before multiplying - (please note that there is no division in modular arithmetic)
• Because we can reduce factors before we multiply them together, we can reduce the base of a natural number exponent (since the base represents the factor which is being repeatedly multiplied together) before taking the power.
When it is the exponent which is "too big", other tricks must be used, such as looking for patterns in the powers of the base (as in the example of 71492) or using Fermat's Little Theorem (which is a special case of looking for patterns in the powers.)
Homework:
• Journal assignment: watch the video on Fermat's Little Theorem (which was assigned previously!), write on what you learn from it, and then use that to try the Activity again.
• Problems related to Fermat's Little Theorem:
1) Compute each of the following:
a) 14 (mod 5), 24 (mod 5), 34 (mod 5), 44 (mod 5)
b) 16 (mod 7), 26 (mod 7), 36 (mod 7), 46 (mod 7), 56 (mod 7), 66 (mod 7)
c) How does Fermat's Little Theorem relate to the answers in (a) and (b)?
2a) Using Fermat's Little Theorem (not by direct computation), find 800030 (mod 31). You must verify that the conditions are correct to use the theorem in this problem.
b) Compute 80004 (mod 5). The answer is not 1. Why doesn't this contradict Fermat's LittleTheorem?
Up next: Completing the verification of the RSA algorithm (showing why it works). Reread the part of the proof on p. 3 of the notes and make sure that you are following the reasoning being used at each step (even if you don't see where it is going yet). Next time we will outline or "flowchart" the proof to get a better idea of how it fits together.
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
$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