## 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.

## A nasty difficult question.

basseykayAugust 27 2002, 18:40:31 UTC 14 years ago

Also, how did you choose these books?

## Re: A nasty difficult question.

patrickwondersAugust 27 2002, 19:49:05 UTC 14 years ago

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:

As for recommendations... between these two books, there's no doubt one should go with

Burtonfor 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 asBurton.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

## Re: A nasty difficult question.

patrickwonders14 years ago

ka3ytlAugust 27 2002, 20:26:16 UTC 14 years ago

## Yes, I should have mentioned...

patrickwondersAugust 27 2002, 21:10:26 UTC 14 years ago

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

Burtonyou 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.

## Quick question...

vertigooAugust 27 2002, 22:09:43 UTC 14 years ago

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).

## Re: Quick question...

patrickwondersAugust 28 2002, 06:39:28 UTC 14 years ago

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^2and solve it forx, then you should be in-like-Flynn.## Re: Quick question...

vertigooAugust 28 2002, 14:38:10 UTC 14 years ago

blakes_7August 27 2002, 22:45:26 UTC 14 years ago

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

## It does, mostly...

patrickwondersAugust 28 2002, 06:45:05 UTC 14 years ago

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.

gagerAugust 27 2002, 23:46:22 UTC 14 years ago

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

gmalivukAugust 29 2002, 08:24:13 UTC 14 years ago

Oh, and will this start today, or next thursday?

budhaboyAugust 29 2002, 08:54:32 UTC 14 years ago

Deleted comment

## A threaded collection of lectures...

patrickwondersAugust 30 2002, 07:10:14 UTC 14 years ago

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 examat 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.

pappiSeptember 11 2002, 11:04:47 UTC 14 years ago

norwegianblueApril 9 2003, 00:03:10 UTC 14 years ago

spimijanmanJanuary 8 2005, 22:50:47 UTC 12 years ago

as in college ish and are you planning on studying math?

i recommend modern algebra

## Correction to lesson 3 (CRT)

Anonymous

August 1 2005, 20:20:49 UTC 11 years ago

## Re: Correction to lesson 3 (CRT)

Anonymous

August 1 2005, 20:30:57 UTC 11 years ago

## Re: Correction to lesson 3 (CRT)

patrickwondersAugust 1 2005, 20:39:31 UTC 11 years ago

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

theyare, 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.

kvschwartzFebruary 23 2008, 17:14:35 UTC 9 years ago

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.

neth_duganFebruary 23 2008, 17:37:33 UTC 9 years ago

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

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

For the very basics, I'm assuming you know the notation: x

^{y}for positive integers x and y, right? x^{y}means take y copies of x and multiply them all together. So, a Leyland number is a number that can be expressed as x^{y}+ y^{x}for some x and y, both greater than 1. The smallest possible Leyland number would then be 2^{2}+ 2^{2}= 2 * 2 + 2 * 2 = 8. That, of course, is not prime. The second Leyland number then is 2^{3}+ 3^{2}= 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 . Then, you've got a . 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 2

^{n}-1 for some positive integer n. It's easy to show that 2^{n}-1 isnotprime if n is not prime. On the other hand, when n is prime, 2^{n}-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 . 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 2

^{n}- 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_dugan9 years ago

patrickwonders9 years ago