MAT 338 Day 1 2011

2497 days ago by kcrisman

Let's start!  Suppose you have as many postage stamps as you want numbered 2¢ and 3¢.  What denominations of postage can you get by combining those? (Or, perhaps, what denominations can you not get with just these two kinds?)

Let's try the same problem with 2¢ and 4¢ stamps.  What is the same, what is different?

What about with 3¢ and 4¢ stamps?  (What we are really asking, which might be clear by now, is what positive integers $n$ are impossible to write $n=3x+4y$ for some nonnegative integers $x$ and $y$.)  In this case, after some experimentation, it looks like only 1, 2, and 5 are not possible, so anything six or above is possible.  We call this number the conductor of the set $\{3,4\}$.

Spend some time trying this with different small pairs of numbers.  Pay attention to two things:

  • What is the conductor of the pair?  (You might want to ask whether there is such a number!)
  • How many numbers lower than the conductor cannot be written in this way?

Before going further, we need a bit of review.  

  • Well-Ordering:  This principle just says that any nonempty set of positive integers has a least/smallest element.  We can use it to prove the following fact.
    • There are no integers between 0 and 1.
    • Proof by contradiction: Assume there are some such integers, and let $S=\{x\in\mathbb{Z}\mid 0<x<1\}$.  This set must then have a least element $a$, and $0<a<1$.  Thus $a^2$ is another element such that $0<a^2<1$, but we also know that $a^2<a$ in this case.  But then $a^2$ should be in $S$ but is smaller than any element of $S$, a contradiction, so our original assumption was wrong, and there are no such integers. 
  • Induction:  Remember, this was a way to prove a statement for all integers $n$ after a certain point, for instance $n=1$.  
    • Essentially, (Base case $n=1$) and (Induction step: Case $n=k$ implies case $n=k+1$) combine to prove it for all cases $n\geq 1$.
    • Archetype is $\sum_{i=1}^n i=\frac{n(n+1)}{2}$.  The base case is that $1=\frac{1(1+1)}{2}$.  The induction step uses that if $\sum_{i=1}^k i=\frac{k(k+1)}{2}$, then to add just one more integer $k+1$ means $\sum_{i=1}^{k+1} i=\sum_{i=1}^k i+(k+1)=\frac{k(k+1)}{2}+(k+1)=(k+1)(\frac{k}{2}+1)=\frac{(k+1)(k+2)}{2}$, which is exactly what is required.
  • Divisibility:  If an integer $n$ can be written as a product $kd=n$ of two integers $k,d$, then we say that $d$ divides $n$, or that $n$ is divisible by $d$; we write $d\mid n$ for this concept.
    • So for instance, $n$ even just means $2\mid n$.
    • Or, the divisors of 6 are ... $\pm 1, 2, 3, 6$!  Don't forget negative divisors.
    • We can prove that $4\mid 5^n-1$, a somewhat unexpected statement, using induction.
      • If $n=0$ this is just that 4 divides $5^0-1=1-1=0$, which is definitely true.
      • Suppose $4\mid 5^k-1$.  Then, really, $5^k-1=4x$ for some integer $x$.  Hence $5^k=1+4x$.  Now, we need something to be true about $5^{k+1}-1$, so let's start with just $5^{k+1}=5^k\cdot 5=(1+4x)5$; this means that $$5^{k+1}-1=5(1+4x)-1=20x+4.$$  Certainly $20x+4$ is divisible by 4, so we are done with the proof.

What will we cover this semester?  We'll start by exploring basic integer questions like this for a week or two.  We'll be essentially forced to move to congruences by the material.  Next, we'll explore a more advanced point of view, including groups, to attack cryptography efficiently.  After break, geometry and how it infiltrates number theory will be up.  Finally, functions and limits will help us illuminate primes in depth, as well as show us how the ideas of calculus really do show up in number theory quite naturally.

Your homework is below.  Normally we would have homework handed in only about once a week, but please hand this one in so you can get feedback about how to write proofs and so on with respect to these topics.  Plus, coloring is fun!

  1. Read the text through the top of page 9.
  2. Do the in-line exercises through 1.8.
  3. Write up a proof of the facts we proved in class about the conductor idea with the pairs $\{2,3\}$, $\{2,4\}$, and $\{3,4\}$.
  4. Get your Sage account at the Gordon Sage server.
  5. Try Exercises 1.18 and 1.25.
  6. Prove that $2^n>n$ for all integers $n\geq 0$ by induction.
  7. Color the Foxtrot comic!

To help with the comic, you might want to use the following two Sage ideas.  The first cell lets you type in an integer and check its primality; the second allows you to check whether a number leaves a fraction when divided by (say) 19 or reduces to an integer.

 

is_prime(3169) 
       
True
True
38/19 
       
2
2