# MAT 338 Day 5 2011

## 2580 days ago by kcrisman

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.

@interact def _(k=(1,[-5..25])): f(x,y)=y^2-x^3-k p = implicit_plot(f,(x,-3,3),(y,-6,6),plot_points = 200) lattice_pts = [[i,j] for i in [-3..3] for j in [-6..6]] plot_lattice_pts = points(lattice_pts,rgbcolor=(0,0,0),pointsize=2) curve_pts = [coords for coords in lattice_pts if f(coords[0],coords[1])==0] if len(curve_pts)==0: show(p+plot_lattice_pts, figsize = [5,5], aspect_ratio=1) else: plot_curve_pts = points(curve_pts, rgbcolor = (0,0,1),pointsize=20) show(p+plot_lattice_pts+plot_curve_pts, figsize = [5,5]) html("Solutions of $x^3+%s=y^2$ in this viewing window"%(k,))

## 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 20th-century 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 $9-1=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^2-1=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?

end_range=10 [(x,p,y,q) for x in range(1,end_range) for y in range(1,end_range) for p in range(2,end_range) for q in range(2,end_range) if x^p+1==y^q]
 [(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.

• A positive integer $p$ greater than 1 is called prime if the only positive divisors of $p$ are $1$ and $p$ itself.
• If an integer $n>1$ is not prime, it is called composite.

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.

is_prime(5); is_prime(6) # Is my number a prime'?'
 True False True False
is_prime_power(25);is_prime_power(26) # Is my number a prime power'?'
 True False True False
prime_range(100) # What are all primes up to but not including 100'?'
 [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]
primes_first_n(100) # What are the first 100 primes'?'
 [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]
factor(2*3*(2*3+1)*(2*3*(2*3+1)+1)*(2*3*(2*3+1)*(2*3*(2*3+1)+1)+1))
 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.

• To check whether a number $n>1$ is composite or prime, it suffices to divide by all primes $p\leq \sqrt{n}$.
• Proof: If $n$ is not prime (composite), we can write $n=de$ for integers $d$ and $e$ both strictly between $1$ and $n$.  If both $d,e>\sqrt{n}$, then $$n=de>\left(\sqrt{n}\right)^2=n\; ,$$ a contradiction.

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:

• Every $n>1$ has a factorization (way to write it as a product) into prime numbers.
• Every such factorization of a given $n$ is the same if you put the prime factors in increasing order (uniqueness).

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:

• If a number is prime, that is the prime factorization.
• If a number is not prime (that is, composite), then it is divisible by some prime. (This requires an axiom equivalent to induction.)
• This process can be continued and is finite.  (This requires some axiom equivalent to induction as well.)
• Any other way in which you can write the same number as a product of primes is just a reordering of the one obtained in the previous step. (This step requires that if a prime $p$ divides a product $ab$, then $p$ divides at least one of $a$ or $b$; Euclid proves it here.)

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:

• Lots of theorems now have reasons, not just proofs.  This is an important point about math!  You will reprove a few things to see this.
• Computing all kinds of things becomes easier, e.g. all the computations like lcm, gcd, powers, etc. on page 23.
• It can help us do in a systematic way results that were probably first obtained by extremely ad-hoc methods, e.g. Corollary 2.5.
• It gives us a canonical way to describe every integer in terms of simpler integers, and gives a measure of simplicity.

As an example, let's prove with it (on the board) two things I used for the proofs about Pythagorean triples last time:

• If $a^2|z^2$, then $a|z$.
• If $gcd(m,n)=1$ and $mn$ is a perfect square, then so are $m$ and $n$.

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.

prime_divisors(693)
 [3, 7, 11] [3, 7, 11]
factor(693)
 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).

• We say that $p^k\parallel n$ precisely when $p^k|n$ but $p^{k+1}$ does not divide $n$.

As an example, $5^2\parallel 75$.  The prime factorization of a number clearly gives you information about this.

factor(factorial(20))
 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:

factorial(20)
 2432902008176640000 2432902008176640000

Well, now it's time for some homework!

1. Find a (fairly) obvious solution to the equation $m^n=n^m$ for $m\neq n$.  Are there other such solutions?
2. A number such as 11, 111, 1111 is called a repunit.  Clearly eleven is a prime repunit.  Find another one.
3. Find the prime numbers less than 100 using the Sieve of Eratosthenes - make sure you actually draw it!  Every math student should do this once - and only once.
4. Reprove Corollary 1.11 and Theorem 1.12 using the FTA.
5. Prove using the FTA that if $gcd(a,b)=d$ then $gcd\Big(\frac{a}{d},\frac{b}{d}\Big)=1$.
6. Do Exercise 2.19.
7. Show that if $a$ and $b$ are positive integers and $a^3\mid b^2$, then $a\mid b$.
8. Show that if $p^a\parallel m$ and $p^b\parallel n$, then $p^{a+b}\parallel mn$.
9. Is it possible for $n!$ to end in exactly five zeros?
10. Show that $\log_{10} (5)$ is irrational.
11. Show that $3^{2/3}$ is irrational.
12. By hand, find the prime factorizations of 36, 756, and 1001.  Use these to find their pairwise GCDs and LCMs.
13. By hand, find the GCD and LCM of $2^2\cdot 3^5\cdot 7^2\cdot 13\cdot 37$ and $2^3\cdot 3^4\cdot 11\cdot 31^2$.
14. By any method you like, find the prime factorizations of $2^{24}-1$ and $10^8-1$, as well as their GCD.