Overview

The notion of divisibility 
One of the most important notions in (elementary) Number Theory is the one of divisibility. Given a natural number n (ie =1, 2, 3,...) when can one lay out n objects of the same kind and size evenly spaced in a rectangle? Eg for n=15, we can find a rectangle of the form 3x5 in which we can place our 15 objects neatly. In a sense, such a number like 15 can be thought of as occurring also as a "2-dimensional" size. If n=17, say, this is not possible--what about n=691? or n=323?

Primes
Numbers for which this is not possible (i.e. which only occur as a "1-dimensional size") are called primes--we exclude the number 1 here. These play a crucial role in NT as they are the building blocks of sorts for the set of numbers (multiplicatively speaking): it turns out that each natural number can be written as a product of primes, ie we can "decompose" or factor such a number into building blocks. 

Uniqueness
What is more, this decomposition is essentially unique (we will prove that soon), and this fact is a basic one (reflected by the name of the corresponding theorem, the "fundamental theorem of arithmetic"). 

Dangerous predictions
This decomposition can be rather hard to achieve, and one can easily misjudge the nature (i.e. being prime or not) of an integer--even one of the best Number Theorists of his time (Pierre de Fermat 1601-1665) fell into the trap: he saw a "prime pattern" in the following sequence 2, 3, 5, 17, 257, 65537, ... and guessed that this prime property would hold for each sequence member. But about a century later Euler (another NT hero) found a factorisation of the very next number in this sequence (Q: which is it? A: 4294967297= 2^(2^5)+1, divisible by 641 and 6700417).

Cryptography from discrepancy
Nowadays such a factorisation of a 10-digit number on a computer is instantaneous but even now if we want to achieve it for a, say, 100- or even 200-digit number we are often out of luck! 
In particular suppose we find two huge primes, of about 100 digits each, then it takes a computer an instant to multiply them together but it is in most cases practically impossible for someone else to decompose the result back into a product of primes.
This amazing "incongruence" between easy multiplication and hard "reverse operation" (ie factorisation) is actually used in cryptography in everyday life situations like secure data transmission or Internet banking etc.


But in order to understand what is behind this, we first need to get a good grip at the divisibility properties of the integers. On the other hand, we will also need to get a feel for how to encrypt messages and, more importantly, how to encrypt things publicly/in broad daylight ("public key cryptography")  in such a way that only someone with "extra knowledge" can actually decrypt it (without sneaking into the drawer/trash can of the sender, of course).

How many primes?
An immediate question is whether there are enough such primes at all; we will soon see that there are in fact infinitely many such. But proofs of this fact are "qualitative" in nature; in fact, so far no-one has ever found a closed formula which produces infinitely many primes, and primes only. Also, we will discover a sensible way to ask "how many" primes there are, which is the content of the famous prime number theorem (an analytic result which we will not prove, stating that the number of primes below a bound x is roughly of size  x/log(x)).

"Comparing divisibilities"
One further feature of divisibility will be prominent soon: while it can be very hard to decompose a given integer, it is very fast to "compare divisibilities" of two integers with each other. This goes back 2000 years to Euclid, and the resulting (Euclidean) algorithm is the prototype of a fast and efficient algorithm.

Working with congruences
We will need to get a good grip on working with remainders from divisions, leading to congruences and congruence classes/residue classes (e.g. "quarter past the hour" can be viewed as the class "15 modulo 60").

Quadratic reciprocity
One of the highlights of the term will be the exploration of a remarkable structural insight into the integers: divide the prime 37 by the prime 11, giving the remainder 4, a square; so 37 leaves the same remainder as a square number when dividing by the 11 --we will then say "37 is a square modulo 11".
Now the "quadratic reciprocity law" found [and proved] by Gauss says that one can readily say whether the reciprocal statement "11 is a square modulo 37" holds or not. (It does: try to divide 14^2 by 37)
We will state the underlying amazing law and prove it.


Computers:
This brings us to the use of computers: for the cryptographic parts of our course only few examples can be carried out by hand (in decent time); hence it is almost indispensable to rely on calculators (but the range in which they are useful is still rather small) or, better still, on computers. I strongly recommend that you familiarise yourselves with one of the standard packages:
* GP-PARI (free, slim, powerful, focussed on NT)
* Maple (cheap licenses via University, big, not mainly for NT; at times somewhat unintuitive; more powerful for symbolic calculations)
* Mathematica (not so cheap licenses(?), big, multipurpose; similar ball park as Maple, great graphics routines)
* SAGE (free, huge, very powerful, strong focus on NT; versatile, unifies [serves as a shell for other packages like the above, provided license for those is valid])
[possibly I will devote one lecture to give an impression of how to use GP-PARI (in our context)]