Colorado State University, Pueblo; Spring 2014
Math 319 — Number Theory
Course Schedule & Homework Assignments
Here is a link back to the course syllabus/policy page.
In the following, the image
means that class was videoed that day and you can get a link by e-mailing me.
Note that if you know ahead of time that you will miss a class, you should
tell me and I will be sure to video that day.
This schedule is will be changing very frequently, please check it at
least every class day, and before starting work on any assignment (in case the
content of the assignment has changed).
irrational examples of possible side lengths for a right
triangle -- e.g., proof (by contradiction) that
$\sqrt{2}$ is irrational
rational solution would give integer solution by clearing all
the denominators
a single solution gives many others by multiplying all side
lengths by the same number; if the first solution was integral,
we can use this to get an infinite number of new integral
solutions by multiplying by an integral scale factor
$\{3, 4, 5\}$ is an integral solution!
terms we defined
rational number, set of which being denoted $\QQ$.
triangular numbers... maybe also square/cube/higher power
numbers
some basic mathematical notation:
"there exits" $\exists$ and "for all" $\forall$
set membership, as $x\in\RR$.
"$P$ implies $Q$", $P\Rightarrow Q$
a little on what makes for good defintion, e.g., for
various types of numbers -- observation that it is surprisingly
hard to define $\NN$; one way is the Zermelo-Frankel approach which
starts with $1$ and has a "successor" function which outputs the
next natural number given any particular one as input
a basic Number Theoretic problems is the existence of numbers of
various "shapes", e.g., triangular numbers; this is not so
interesting after Gauss's forumla for the $n$th triangular number
$$T_n=\sum_{j=1}^n j = \frac{n(n+1)}{2}$$
starting to analyze PPTs: first, we saw that a PPT $(a,b,c)$
cannot have all numbers being even (violates primitivity), nor even
just $a$ and $b$ being even (because then $c$ would be as well, so
they would all be even). started looking at the case of $a$ and $b$
being odd.
one thing that seemed to go by in the "$a$ and $b$ cannot both be
even" proof was the following part
Lemma: If $c^2$ is even, then so must be $c$.
which seems intuitively obvious but should probably be explained
more carefully...
Submit T&Q1 on Chapter 1 of
A Friendly
Introduction[at least an hour before class, as
always!]
Following Silverman, examining properties of PPTs. Along the way,
he seems to use, without satisfactory proof, the following lemmata:
Lemma: If $a\in\NN$ is such that $a^2$ is even, then
$a$ is also even.
Lemma: If $a,b\in\NN$ have no common factors and if
$ab$ is a square, then also $a$ and $b$ are squares.
Silverman's explanation (of the second of these) is to a later
chapter, basically to the Fundamental Theorem of Arithmetic.
We got the statement of
The Pythagorean Triples Theorem. Note that this
implies that there are an infinite number of PPTs, and gives
a complete description of all of them.
Another way to see that there are an infinite number of PPTs: Theorem: For $n\in\NN$, let $a=2n^2+2n$, $b=2n+1$. Then
$(a,b,a+1)$ is a PPT. [Notes: This amounts to letting $b$ be any odd
number, so $b^2$ is also odd, and setting
$a=\frac{b^2-1}{2}$. Here we give a version suggested by a
question in a student's T&Q2 ... but actually, this
approach is the one Euclid used to prove that there are an
infinite number of PPTs.] Proof: Well, just check that $a^2+b^2=(a+1)^2$, it's easy
algebra. Also, $a$ and $a+1$ have no common factors -- if $d$ is
a factor of $a$, then $d$ goes into $a+1$ with a remainder of $1$
so is not a divisor. $\Box$
There were lots of possible definitions, use one that
you will then be happy working with in the proof you were
asked to do — often, the easiest definition to work
with turns out to be the one which at first seems the
most complicated ... because all the moving parts of the
definition give you something to grab a hold of.
Don't forget when you are asked to prove an "if and only
if" that there are two directions to prove: i.e., to
prove $A\Leftrightarrow B$, you need to prove both
$A\Rightarrow B$ and $B\Rightarrow A$.
Sometimes, proving $A\Rightarrow B$ is not appealing,
so you might consider instead proving
$\neg B\Rightarrow \neg A$ [where $\neg A$ is the read "not
$A$"]. This second statement is the contrapositive
of the original, and from basic logic it is in fact
entirely equivalent to the original.
HW1:
This statement has some relationship to the Twin
Prime Conjecture: if there are an infinite number of
prime triples, then certainly there are an infinite number
of twin primes. On the other hand, there could be only a
finite number of prime triples and that would not imply
that the Twin Prime Conjecture was true: it is much
harder to be a prime triple than to be a twin prime.
the solution involves fiddling with the possibilities of
the number of a potential prime triple being multiples of
$3$, by thinking of any $n\in\ZZ$ as equalling $3m$, $3m+1$,
or $3m+2$, for some $m\in\ZZ$.
good careful proofs
some proof strategies:
direct verification ["unpacking"]
contradiction
induction ... and therein lies the Well-Ordering
Principle
The Well-Ordering Principle; note it doesn't always apply,
e.g., it doesn't hold if you are working in $\ZZ$ instead
of in $\NN$.
The Pigeonhole Principle
The Principle of Mathematical Induction, Versions 1 and 2
example of a proof by induction: problem 1.2 from HW1
Write down the steps of the proof of the Primitive Pythagorean
Triples Theorem from A Friendly Introduction as clearly and completely as
you can ... but for cubes, not squares. That is, you are
attempting to prove a similar theorem but for triples $(a,b,c)$
satisfying $a^3+b^3=c^3$. Do this by making an outline of the
proof following Silverman, stating the version for cubes, and then
trying to prove each of the steps for cubes.
[You will not be able to prove all of the steps — the
cube version of the theorem is false, it's a case of the
result know as Fermat's Last Theorem— but more
steps along the way are possible that you might at first
think.]
Can you think of a number system which would not satisfy
the Well-Ordering Principle? (Other than $\ZZ$, mentioned in
class.)
What we're looking for here is a set $\Uu$ of mathematical
objects which we'll call "unnatural numbers" which have two
operations "${}+{}$" and "${}\cdot{}$" called "unnatural addition"
and "unnatural multiplication", both of which take a pair of
unnatural numbers and produce another unnatural number, and which
together satisfy the same rules that integers satisfy as given
in PaR1 §1.2.
Also, on $\Uu$ we have a notion of "${}<{}$" in the sense that
given $a,b\in\Uu$, it is always the case that $a<b$, $b<a$,
or $a=b$. This is needed to define the word "least" in the
Well-Ordering Principle: given a set $S\subset\Uu$, $\ell\in S$ is
a least element of $S$ if $\forall x\in S,$ either $x=\ell$
or $\ell<x$.
An Unwell-Ordering example would be a non-empty subset $S\subset\Uu$
for which a least element did not exist.
Try to think of a set of unnatural numbers with an Unwell-Ordering
example, in the above sense. That is, write down what will be
your set $\Uu$, the operations ${}+{}$ and ${}\cdot{}$, the
relation ${}<{}$, and the set $S\subset\Uu$ which has no least
element (prove that it has none!).
another proof of The Division Algorithm, this time using
the Principle of Mathematical Induction.
use the Division Algorithm repeatedly on a number and
its successive quotients by the same number $b\in\ZZ$, $b>1$,
putting it back together to get the base-$b$ representation of
a number $n\in\ZZ$
Submit T&Q5 also on PaR1 §1.3 [think and
question more deeply!]
Maxiquiz 2 was handed out, please hand it in next Monday; when
you do it over the weekend, do not consult anything outside your head
(do it like a real quiz!)
for $n,m\in\ZZ$, $\gcd(n,m)$ as the smallest positive integral
linear combination of $n$ and $m$ (think Well-Ordering)
several integers being mutually relatively prime or
pairwise relatively prime and the relationship
Submit T&Q7 on PaR1 §1.5
Miniquiz 4
Hand in HW3: in PaR1, problems
1.3.8, 1.3.9 [Hint: you may want to use the result from Maxiquiz
2], 1.4.5 [Hint: convert each hexadecimal digit to four bits
— explain what are the possibilities and why this works.]
there was no Miniquiz 5 in class; had there been, it would
probably have asked you to state the Euclidean Algorithm or the
theorem which characterizes the gcd of two numbers as the minimal
element of a particular set of natural numbers.
Hand in HW4: in PaR1, problems
1.6.1, 1.6.4, 1.6.5
another version of working modulo $n$ and linear congruences:
equations in "mod $n$ land"
defining equivalence relation and sets of
equivalence classes
definition, basic properties of $\ZZ_n$ (also written $\ZZ/n\ZZ$)
restatement of work in §§2.1&2.2 of PaR2 in
terms of $\ZZ_n$.
Submit T&Q13 on PaR2 §2.4
Hand in HW6: in PaR2, problems
2.3.3 & 2.3.4 (2.3.4 is only in the most recent version of
PaR2, go to the online version if you have an older version
without that problem)
hand in the take-home part of Midterm I, following
these steps:
Read your favorite religious or philosophical text for 10 minutes
to engage your moral sense.
Write up a solution to problem 2 or 3 from
PaR3 §3.
You may use any of the readings assigned for this class (which
were Chapters 1 & 2 of A Friendly Introduction and our own in-house
readings PaR1, PaR2,
and PaR3) and your notes but you may not
use any other resource, animate or inanimate! (E.g.,
do not ask any other human about these problems — e-mail
me if you get stuck! — or look at any books or web
pages other than the ones specifically permitted.)
You will have a much nicer end-product if you write a rough draft
of your solution before you write the one you will hand in.
Along with the solution you hand in, please attach a signed sheet
where you say "I have understood and followed the rules for this
take-home test problem."
Send me an e-mail encrypted with my public key, which can be
found here. To do this, you will have
to download, install, and learn how to use some crypto software:
e.g.,GnuPG is a great choice, available at
gnupg.org, or there are lots of
other options, including perhaps your current mail program. So
poke around a little in your mail service's help pages, ask
google, etc.
Send me an e-mail which you sign digitally. You will again need
some software to do this — and you will have to get me your
public key somehow, so that I can verify the signature. So you
will have to run the key-generation part of your crypto software,
export the key to an ASCII file, and e-mail that file to me also.
don't forget to turn in Maxiquiz 9 if you chose to do one which
is on paper — for details of this maxiquiz, see the entry above
for the Friday class before Spring Break.
W:
more review for Midterm II
please have handed in all outstanding HW assignments and be
ready to discuss those (and other) problems
Maxiquiz 11 turned into a take-home quiz. Please do it in
full quiz-like formality: consult no other resource (human, electronic,
paper, ...) than is on the quiz sheet itself, and work on it for
about 20/25 minutes at the most. Then hand it in on Monday.
means that class was videoed that day and you can get a link by e-mailing me.
Note that if you know ahead of time that you will miss a class, you should
tell me and I will be sure to video that day.