Patrick (patrickwonders) wrote in math_class,
Patrick
patrickwonders
math_class

  • Mood:

NumberTheory101 (#0): Introduction

How is this going to go?

My name is Patrick (patrickwonders on LiveJournal). I've tutored many folks one-on-one and I've written a few articles on PlanetMath. This, however, is my first foray into lecturing (on math) to a group of people that I don't already know pretty well. So, make it to bring to my attention anything that I pass over too lightly or beat into the ground.

I'm going to shoot for a new lecture every Thursday evening (GMT). Some of the lectures will be longer than others depending upon the depth of the material being discussed. I will give problems for people to practice with when appropriate. I'll post the solutions to the problems on Monday evening (GMT). On LiveJournal, I will keep the body of the lessons and all problem solutions behind <lj-cut> tags.

What are we going to learn?

I'm going to work mostly out of two books called Elementary Number Theory---one by Burton, the other by Jones and Jones. I will probably follow along through the topics of Burton spritzing in other stuff in appropriate places. I will keep a running bibliography here:

  • Burton, David M. Elementary Number Theory: Fifth Edition. McGraw-Hill Higher Education, Boston, 2002. ISBN 0-072-32569-0.
  • Jones, Gareth A. and J. Mary Jones. Elementary Number Theory. Springer-Verlag, London, 1998. ISBN 3-540-76197-7.
  • Singh, Simon. Fermat's Enigma: The Epic Quest to Solve the World's Greatest Mathematical Problem. Walker and Company, New York, 1997. ISBN 0-802-71331-9.

You will not need any particular textbook for this class.

I'm more than willing to take requests. But, at the very least, I hope to cover divisibility in the integers, the Fundamental Theorem of Arithmetic, Fermat's Little Theorem, RSA Encryption, a survey of Prime Factorization methods, an intro to the Discrete Logarithm problem, continued fractions, partitions, the Riemann Zeta Function, and some information about Fermat's Last Theorem. I plan on liberally sprinkling the lectures with mentions of unsolved problems in Number Theory.

Links to all of the classes

  1. (#1): Modular Arithmetic and answers
  2. Euclidean Algorithm and answers
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

  • 26 comments
If you were to recomend just one of these books for someone who has never studied number theory before which would it be?

Also, how did you choose these books?

I wish that I could say that I've surveyed a bunch of number theory books and distilled it to these two. The truth of the matter however is this:

The Burton book was the text for the number theory class I took as an undergraduate. That text was chosen for that class by a teacher whose opinions on such matters carry great weight. I also found it quite an enjoyable text. Adding to its strength, I had to borrow a copy of the text for a short while from another teacher. The teacher which I borrowed it from was the biggest number-theory geek at my school. He had editions 1, 2, 3, 4, and 5. One other bit of anecdotal support for it is that I tried to borrow it from our school library, but it was the only number theory text which was checked out already---and it wasn't one of my classmates who had it.

The Jones and Jones book is the one that I mistakenly ordered from Amazon during the period in which I was borrowing the book from the number-theory geek.

As for recommendations... between these two books, there's no doubt one should go with Burton for an introduction. It's in a more coherent order and it gives lots of historical tidbits. The other book goes into great depth in some areas and skips some other areas and isn't as generally friendly. It's a good book for what it's got. But, it doesn't have as much as Burton.

Unfortunately, Burton's expensive. I needed it for class and Amazon was telling me 4-6 weeks at $110. So, I called the publisher to get a copy faster for $120. I'll try to hit Borders or Barnes & Noble in the next couple of days to look for comparable, available, cheaper books.

Deleted comment

How much does the edition matter for the Burton book? Would you recommend getting both books or should we just follow along?

I should have mentioned that... I will organize my lectures so that you don't need either book. If you want to study faster than I lecture, then it shouldn't much matter which edition of Burton you grab. I wouldn't bother buying the $110 version if you're only planning on using it for this class.

When I give problems for you to work on, I'll be making them up myself. I won't be referring you to a particular page in a particular book.

Sounds exciting!

I do have one question though:

What sort of knowledge is going to be a pre-requisite for this? I have no idea what knowledge structure the elementary ideas of number theory are based on, or if it is built from the ground level up, so to speak (If you don't care to elaborate now, I'll most likely figure that out once you start anyway).

For the most part, the only pre-requisite knowledge assumed is a good grasp of arithmetic (addition, subtraction, multiplication, division, and exponentiation by positive-integer powers). If you're uncomfortable with simple high-school algebra notation, then it could be tough to follow some lines of argument.

Pretty much, if you could take the equation 3x + 5 = x/4 - 5^2 and solve it for x, then you should be in-like-Flynn.

Sounds good. I look forward to getting started then! :)
Thank you!

One question: Does the recent paper hoping to prove that PRIMES is in P fall under this category (Number Theory)? If so, would you be touching on that?

Thanks...h

That paper is relevant both to Number Theory and to Computational Complexity Theory. The algorithm will be quite understandable somewhere shortly into this course. The fact that the algorithm is in P is apparent, but it depends on how verbose I'm feeling when we get there whether I'll spend much time explaining P. And, that paper uses one theorem about the distribution of a special-class of prime numbers that I am not sure yet whether we'll have enough information to prove it. We'll definitely have enough information to state it, at least.

Great idea, and I'll be following along.

I haven't taken a formal number theory class, although I'm two classes from a math degree and I've read quite a few 'light' introductions (A Journey into Mathematics by Durham and a few others), so I think it will be quite interesting.

Just wanted to introduce myself and give you my background.

Thanks,
-Lyle
Okay, I'm now definitely watching this community. I've always loved number theory, and have taken a couple classes on it, but both were done before i "finished" calc, which pretty much every program requires before you move on to more interesting maths. Because of this, most of the interesting stuff i learned each time was very quickly forgotten, much to my dismay. Not only will this give me a chance to relearn it, but i'll be able to refer back to this set of lessons whenever I want to remind myself of something.

Oh, and will this start today, or next thursday?
can't wait for the refresher... it's been years.

Deleted comment

It will be a collection of lectures, but they won't each be complete without the others. Some will depend upon earlier lectures.

I hadn't planned on a final exam at all. I suppose that I could give that a whirl.

The first lesson was supposed to be out yesterday afternoon. My apologies to all. It will be out in the next hour or two.

i took an intro number theory class last year that used the Burton book, and it was the best math class i've ever taken! it's the *only* class i willingly took at 9am =)
k, just found this. I'm really interested cause I'm in AP Calc but I really want to learn other types of math esp. number theory. so, yeah. I'm excited!
where are you know?
as in college ish and are you planning on studying math?
i recommend modern algebra
Just noticed you list the solutions to 10x==15(mod 25) as {2, 9, 14, 19, 24}, replace that 2 with a 4. Also a good book is the Handbook of Applied Cryptography which, fortunately, is available from the author in pdf and ps forms for free. Although not the explicit focus of the book it does have the fundamentals of discrete math and the associated algorithms. -Priebel
Just noticed the livejournal version is correct but check the one on your webpage http://www.csh.rit.edu/~pat/math/series/nt/20020926/

neth_dugan

February 11 2008, 18:43:36 UTC 9 years ago Edited:  February 11 2008, 18:45:25 UTC

Is it okay to ask a question (I came across this com looking for a place that may have it, this seems like the best bet and hay, but it also looks interesting in general. Kinda wish I'd done A-Level math and not stopped at GCSE). In any case, I was looking up the number 1649 which as it turns out is a Leyland number. I tried to find out what they are, and got this but don't understand a word of it.

So, um, do you happen to know any online resources that explain it to a dunce who last did GCSE math four years ago? Sorry if this is out of line.



ETA: Well, 'cept for the bit about prime numbers, I'm not so daft to not know what they are.
Hm. I found this community just now, too.

Not that my "just now" is quite the same as yours -- they're almost two weeks apart. But given that this community seems (to me) to be at least five YEARS defunct, by comparison, two weeks apart seems like a small time interval.


May I ask what your icon is from? I now associate the line "Is it safe?" with Gandalf's "Is it secret? Is it safe?" from movie!"The Fellowship of the Ring" -- but clearly that's not what your icon is showing.
The icon is from Doctor Who, and I don't think he said that line there, it's just... a product of the scene, lol.

And yeah, know what you mean about the five years thing, thing I figured out what the wiki entry was on about but... *shrugs*

patrickwonders

February 24 2008, 05:24:48 UTC 9 years ago Edited:  February 24 2008, 05:25:27 UTC

Sorry, I forgot to reply right away when I first saw this comment, and then it drifted off of my radar. Do you have anything more specific that you wondering about?

For the very basics, I'm assuming you know the notation: xy for positive integers x and y, right? xy means take y copies of x and multiply them all together. So, a Leyland number is a number that can be expressed as xy + yx for some x and y, both greater than 1. The smallest possible Leyland number would then be 22 + 22 = 2 * 2 + 2 * 2 = 8. That, of course, is not prime. The second Leyland number then is 23 + 32 = 2 * 2 * 2 + 3 * 3 = 17. That one is prime.

There are a variety of algorithms for proving that a given number is prime. Most of them require a great deal of time and memory to determine if large numbers are prime. I'm not sure who Elliptic curve primality proving works. I will have to explore that. There are some tests, however, which don't take as long but don't prove that a number is prime. So, imagine there is some algorithm you can run on a number that spits out either 0 or 1 when the algorithm is done. And, imagine that you can prove that it always says 1 if the number is prime. And, imagine that you can prove that the odds are very small that the algorithm will say 1 if the number is not prime. Now, imagine you have a whole family of such tests. Now, say that you took a number and ran 100 of these tests on it, and they all said 1. Then, you've got a probable prime. You can't prove it's prime. But, there are incredibly few non-prime numbers that could pass all of these tests.

Obviously, Leyland numbers have a simple algebraic description. It's easy enough to make them until the cows come home. There are, however, some other number with simple algebraic description.... for example, the Mersenne numbers are numbers which can be expressed as 2n-1 for some positive integer n. It's easy to show that 2n-1 is not prime if n is not prime. On the other hand, when n is prime, 2n-1 may or may not be prime. There are algorithms which take advantage of this special form of number though to reduce the amount of computation required to prove the number is prime. That's the implication in the quote that Leyland numbers don't have this cyclotomic property.

The cyclotomic numbers are the complex roots of unity. What's that? Well, if you take the square root of 1, you get two answers... +1 and -1... because 1 * 1 = 1 and (-1) * (-1) = 1. If you take the fourth root of 1, you get four answers.... +1, -1, +i, and -i. Here, i is the imaginary unit... it is a number that when multiplied by itself gives you -1. So, i * i * i * i = (-1) * (-1) = 1. And, similarly for -i. Now, if you take the n-th root of 1, you get n answers. [If you know trigonometry at all, the n answers are cos(2*π*j/n) + i * sin(2*π*j/n) for j = 0, 1, 2, 3, 4, ..., n-1.] These numbers have all kinds of special properties... for example, when you multiply an n-the root of 1 by another n-th root of 1, the answer is an n-th root of one. These special properties can be exploited for n-th roots of other numbers, too... which is why there are special algorithms for factoring numbers that are close to a power of a small number.... and 2n - 1 is always close to a power of a small number. On the other hand, the Leyland numbers aren't necessarily close at all to a power of a small number. So, they are a bigger challenge for those trying to test their factoring algorithms.

neth_dugan

9 years ago

patrickwonders

9 years ago