What should I say about elementary number theory?

Question

I need to give an option talk (a 10 min talk given to students who are selecting their options for sophomore mathematics) about an elementary number theory module. The students will have completed a course in calculus, linear algebra and discrete mathematics so are familiar with mathematical proofs. I will discuss how it is the study of positive integers particularly the primes and give some cryptography applications. What is a good hook to stipulate in this talk regarding an introduction to elementary number theory?

Answer 1

I have so many ideas for this ... but will select one. I promise. But all my ideas about this satisfy this criterion:

Try talking about something they can start computing while you are talking, but that can quickly be connected to something interesting and mysterious (if not to say unsolved).

Today's suggestion is the "number of divisors" or "sum of divisors" functions, often called $\tau$ and $\sigma$ (or $\sigma_0$ and $\sigma_1$). It is easy to get people computing these for small positive integers, and perhaps to very quickly see patterns (e.g. $\tau(p)=2$, $\sigma(p)=p+1$ for $p$ prime). And prime numbers/factorization obviously are useful in computing them.

But one can quickly ask related questions. Such as, "What is the average number of divisors of a number?" Of course, that requires definitions, but for this kind of talk you can sweep that under the rug and say "here is a sample definition" - like $\frac{1}{n}\sum_{k=1}^n \tau(k)$. Turns out this is asymptotically $\log(n)+2\gamma-1$ - yes, that gamma-the-number. On the other hand, I don't think a hard error has been given - you may have to peruse Apostol, Stopple, or Hardy/Wright to see, I think it is only known to be between $O(1/\sqrt[4]{n})$ and $O(1/\sqrt[3]{n})$ but my info may be out of date.

Alternately, to show how quickly new questions can arise, one can make up functions like $\tau_{o}$ and $\tau_{e}$, the number of odd and even divisors, respectively - are they equally good? What is "good" here? They are easy to compute small values of, but different - can we ask/answer the same questions about formulas and so forth?

Or if the students are quite erudite you can talk about its Dirichlet series (number 19 here) but that probably is beyond what you can do ...

---

In any case, you don't have to take this example, but I very much recommend finding some topic that is very easy to investigate that leads really fast to unknown/hard questions. Whether you look for one related to cryptography, algebra, or geometry, you will find one! I hope they all pick number theory. And that many other people answer this question so it becomes a repository for ideas for talks advertising it!