Number Theory
Getting Started
A little terminology:
• A theorem is an important result.
• A proposition is less important than a theorem.
• A lemma is a small result, generally proved before its use in a theorem.
• A corollary is a small result, generally a consequence of a recently proved theorem.
These distinctions are necessarily subjective.
Integers and Counting

Number theory is the study of integers (the 'whole' numbers):

\mathbb$Z$=\lbrace \ldots, -4, -3, -2, -1, 0, 1, 2, 3, 4, \ldots \rbrace

The natural numbers are the non-negative integers:

\mathbb$N$ = \lbrace 0, 1, 2, 3, 4, \ldots \rbrace
Many number theorists omit 0 from the natural numbers. We do not.
Not all number are integers. If we need to round such numbers to integers, we use floor or ceiling functions. The floor of a number is the integer less than or equal to the number: the floor of 3.142 is 3 . The ceiling of a number is the nearest integer greater than or equal to the number: the ceiling of 1.414 is 2 . We write \lfloor 3.142 \rfloor = 3, \quad \lceil 1.414 \rceil = 2 \\~\\ \lfloor 42.0 \rfloor = 42, \quad \lceil 42.0 \rceil = 42
(Counting Multiples.)  Let n and m be positive integers. Then the number of multiples of m between 1 and n is \lfloor \frac nm \rfloor .
The number of multiples of m=3 between 1 and 17 is \lfloor \frac$17$$3$ \rfloor = 5 . (\text$They are$3, 6, 9, 12 \text$and$ 15.)
The number of multiples of m=4 between 1 and 24 is \lfloor \frac$24$$4$ \rfloor = 6 . (\text$They are$4, 8, 12, 16, 20 \text$and$ 24.)
When we use the term 'between,' we mean it inclusively. The numbers between 21 and 23 are 21, 22 \text$and$ 23 .
The number of multiples of m=7 between 1 and 1024 is \lfloor \frac$1024$$7$ \rfloor = 146 .
(Counting Squares.)  Let n be a positive integer. The number of squares between 1 and n is \lfloor\sqrt$n$\rfloor .
The number of squares between 1 and 39 is \lfloor \sqrt$39$\rfloor=6 . (\text$They are$1, 4, 9, 16, 25 \text$and$ 36.)
Find the number of squares between 100 and 200 .
The number of squares between 100 and 200 is the number of squares between 1 and 200 minus the number of squares between 1 and 99. (Note that if we subtract the number of squares between 1 and 100 , where 100 is a square, we are removing one of the squares that we should be counting between 100 and 200 .) \lfloor \sqrt$200$\rfloor - \lfloor \sqrt$99$\rfloor = 14-9=5 The squares are 100, 121, 144, 156 \text$and$ 169 .
(Counting Digits.)  If n is a positive integer, then the number of digits in the decimal representation of n is $\lfloor \log_\[10$(n) \rfloor + 1\]
(Counting Bits.)  If n is a positive integer, then the number of digits in the binary representation of n is $\lfloor \log_\[2$(n) \rfloor + 1\]
No proof provided.
Divisibility
(Division with Remainder.)  Let a and b be integers, with b positive. Then there exist integers q and r satisfying a=q\cdot b+r \textit$and$ 0\le r \lt b
q is known as the quotient and r the remainder.