We spent the last couple times discussing linear and quadratic Diophantine equations. As you can see, even relatively simple questions become much harder once you have to restrict yourself to integer solutions. And doing it without any more tools becomes increasingly unwieldy.
But there is one final example of a question we can at least touch on. Just like Pythagorean triples come, at their heart, from the observation that $3^2+4^2=5^2$  an interesting coincidence with close numbers  so too, we can notice that $3^2$ and $2^3$ are only one apart, and $5^2$ and $3^3$ are only two units apart.
Click to the left again to hide and once more to show the dynamic interactive window 
This is known as Bachet's equation or the Mordell equation. Mordell, an early 20thcentury mathematician, proved that there are only finitely many integer solutions for a given $k$; however, finding them all  or even some!  turns out to be quite tricky, especially since many have no solution (see this page for some tables of what is known).
It turns out that this, too, has incredibly deep connections to "elliptic curves", and that is enough reason to study them. However, it is interesting that there are some which are provable by more elementary means, and later this semester I hope to have us do a few. Fermat claimed the $25+2=27$ was the only solution for $k=2$, but even Euler's proof of this was faulty. Euler's proof in 1738 that $91=8$ was the only nontrivial solution to $k=1$, however, is correct  and uses the same method of 'infinite descent' to even show that there aren't even any other rational number solutions to $y^21=x^3$.
This is also related to a very old question which was called Catalan's conjecture  namely, are there any other consecutive perfect powers other than 8 and 9?
[(2, 3, 3, 2)] [(2, 3, 3, 2)] 
I saw this was called Catalan's conjecture because, as of 2002, it is Mihailescu's Theorem! See this link for a nice overview of the history (going back as far as the 1200s).
Now it's time to introduce maybe the most important concept in the whole course  one you are already pretty familiar with. That is the concept of prime numbers.
As you know, the first few primes are $2,3,5,7,11,\ldots$ That means $4,6,8,9,10,12\ldots$ are composite.
Below, we introduce a few Sage functions for this. Comments on them are given after '#' signs.
True False True False 
True False True False 
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] 
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541] [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541] 
2 * 3 * 7 * 13 * 43 * 139 2 * 3 * 7 * 13 * 43 * 139 
I should point out here that of course the search for 100, or 1000, or how every many prime numbers is not hopeless; that is the content of Euclid's famous theorem on the infinitude of the primes. Strictly speaking, he proves that no matter what $n$ is, there is always a bigger prime $p>n$, which isn't exactly the same thing as a Cantoresque "infinite set of primes"! But we still say there are infinitely many prime numbers.
The handout is a particularly cute proof which appeared in the MAA Monthly a few years back. For Euclid's original, Joyce's web version is still a great resource. There are many proofs of this.
Much later in the course we will talk some about efficient ways to tell if a number is prime, or to get prime numbers. For now, all we will use is something usually known as the Sieve of Eratosthenes.
This is nice, because to get all numbers up through 100 it suffices to remove any numbers divisible by $2,3,5$, or $7$. By the way, Eratosthenes was a contemporary of Archimedes, and no slouch  he is best known for estimating the size of the Earth fairly accurately, amazingly so for the time.
Our biggest goal for today is the Fundamental Theorem of Arithmetic. It says two things:
It is quite old, and of course Euclid has a nice proof of it, along with various lemmas he needs to get there. The book has it as Theorem 2.3. The key ingredients are:
I'll fill in any remaining details in class. Since you've had Algebraic Structures, I should note  this theorem is not true for every algebraic system! Not even for every such system that is like the integers in other ways. Most interesting examples of this will end up being just beyond the level/time available for this course, though.
The FTA is so great, I cannot overstate its significance. For instance:
As an example, let's prove with it (on the board) two things I used for the proofs about Pythagorean triples last time:
There are oodles of things this helps with. Exercise 2.3 is interesting here, for example.
Here are some ways to calculate these things in Sage.
[3, 7, 11] [3, 7, 11] 
3^2 * 7 * 11 3^2 * 7 * 11 
Note that one of these functions gives just a list of the prime divisors, while the other gives the full factorization.
One last thing that is useful is some additional notation (page 23 in the book, if you like).
As an example, $5^2\parallel 75$. The prime factorization of a number clearly gives you information about this.
2^18 * 3^8 * 5^4 * 7^2 * 11 * 13 * 17 * 19 2^18 * 3^8 * 5^4 * 7^2 * 11 * 13 * 17 * 19 
Since $2^{18} \parallel 20!$ and $5^4\parallel 20!$, we can conclude that $20!$ ends with exactly 4 zeros merely from the prime factorization, which we could certainly get without multiplying it out (though in this case Sage probably does that first). We can check this:
2432902008176640000 2432902008176640000 
Well, now it's time for some homework!
