Number Theory

2.3 Euclidean Algorithm

This algorithm comes from one important fact. That fact is actually much important than
the algorithm, because that one fact has wides pread connotations . It is actually a very
simple fact : If d|a and d|b, then d|(ax + by), where x and y are integers. In particular:
d|a, b ) d|(a − b). We can apply this fact in many clever ways. One thing to do is to find
the gcd. Clearly (a, b)|a and (a, b)|b. Well at each step we have two numbers , starting with
a and b. We want to subtract the smaller number from the larger number and keep the two
smallest numbers of the three. Notice that the gcd still divides both of these numbers since
(a, b)|(a−b). We continue this process until we get to the fact that the gcd divides zero and
some other number. Notice however that euclid’s algorithm works backward too. That is to
say, anything that divides both of these numbers will also divide the original two numbers.
Thus, the gcd of the pair of numbers never changes. The gcd of zero and the last number
must therefore be the last number. That last number is the gcd of a and b. This is known
as Euclid’s algorithm and even though it is s lower than the prime factorization method in a
lot of small cases, often times it is much harder to factor large numbers.

2.4 Prime Stuff

Here are some quick facts that sometimes come up.

1. Infinitely many Primes Exactly as it sounds like . There are a bajillion proofs of
this out there. However, the classic one is still assuming there is a finite set of them
Now consider the number   What prime divides this
number?

2. Bertrand’s Postulate These things have such funny names. This has been proven
already, it is no longer a postulate. It basically states that there is always a prime
between n and 2n.

3. Dirichlet’s Theorem Not only are there infinitely many primes, but there are infinitely
primes in any reasonable arithmetic sequence of integers. (No, there aren’t
infinitely many primes in the sequence 2, 4, 6, · · ·.) I guess I should specify that reasonable
means (a, d) = 1, where a is the first term and d is the common difference ).
Most of the time, this is useful just to ensure there is one such prime.

4. Prime Number Theorem This is actually probably never going to be applicable,
but it is a triumph of number theory and has to do with primes. There are quite a few
open conjectures having to do with primes out there: twin primes conjecture, riemann
hypothesis, etc. However, this is one we’ve actually proven! What is says is that the
number of primes less than or equal to x approaches as x goes to infinity.

Primes become more special when we learn about mods and are special all over the place
such as in group theory and other things.

2.5 Some other systems

2.5.1 Gaussian Integers - Z[i]

The Gaussian Integers are interesting because they have division too! The statement is
almost exactly the same: Given a, and |r| < |b|. You’ll
notice that division can always be stated in this way, as long as we have some way of
comparing the sizes of r and b. p In this case, we use the norm in the complex sense |a+bi| =
. We can do all of the stuff we did in the integers with the Gaussian integers
now! This includes the fundamental theorem of arithmetic, with primes being defined as
any numbers whose only factors are units and unit multiples of itself and who are not units
themselves. A unit is any number with a multiplicative inverse, namely 1,−1, i,−i. Gaussian
integers allow us to prove a couple of quick things about integers.

1. The sums of two squares is multiplicative: (a² + b²)(c² + d²) = (ac − bd)² + (ad + bc)²
This is easily proven just by showing that norms are multiplicative in the Gaussian
integers. In this way we realize that we can always rewrite the product of two sums of
squares as one sum of squares.

2. Using other Gaussian integer trickery, we get a result due to Fermat. Let p be an odd
prime, p can be expressed as a sum of squares iff p ≡ 1 (mod 4).

3. Combining the last two things and the fact that 2 = 1² + 1², we can figure exactly
which positive integers can be expressed as the sum of two squares. To check if a
positive integer n can be expressed as the sum of two squares, we divide out all powers
of two and prime factors congruent to one mod four. What we have left must be a
perfect square.

2.5.2 Quaternions

I just wanted to mention them. They are essentially numbers of the form a + bi + cj + dk
where a, b, c, d are all real numbers. Also, addition is component wise but multiplication
is no longer quite commutative. We have that i² = j² = k² = ijk = −1. From this we
can derive the usual stuff. In fact quaternions are quite important for 3- d graphics . Where
do you think the the i, j, k unit vectors come from? By imposing restrictions on a, b, c, d
(I don’t remember if they have to be integers or something else, but it is chosen so that
division and therefore the fundamental theorem still hold). We can use the same ideas as we
used to prove the two squares stuff with the Gaussian integers and prove the Legendre’s four
squares theorem. This theorem states that all positive integers can be expressed as the sum
of four squares. I will also quickly mention a theorem due to Gauss, even though I don’t
know where it comes from: n = a² + b² + c² iff

2.5.3 Polynomials

3 Modular Arithmetic

4 Special Functions

5 Diophantine Equations

6 Tricks of the Trade

These were taken word for word from Melanie Wood’s MOSP lecture.

1. Plug in simple cases.

2. Check in modulo m, where m is carefully chosen.

3. Consecutive numbers are relatively prime.

4. If p|a and p|b, p|a + b and p|a − b

5. Divide into multiple cases.

6. Consider the order of k modulo m.

7. Go back and forth between writing a ≡ b (mod n) and n|a − b.

8. Don’t be afraid to use the quadratic formula .

9. Infinite Descent

10. Factoring

11. Build large numbers with the properties you want.
• Chinese Remainder Theorem (CRT)
• Always large enough primes (even in reasonable arithmetic progressions)

12. A rational is an integer if
• every prime power that divides the denominator divides the numberator.
• it is rational and the root of a monic polynomial with integer coefficients .
• it is the answer to a counting problem
• it is a term in a recursive sequence with integer initial values and integer coefficients

7 Acknowledgements and Other Reading

All of this is compiled from two summers at the Ross math program and MOSP lectures.

8 Unsolved Problems

If you are working on a problem and your proof relies on one of these, you should probably
reconsider it.

9 Practice