Triangular numbers are those that can be written as the sum of a consecutive
series of (whole) numbers beginning with 1. Thus 6 is triangular
because it is the sum of the first three numbers: 6 = 1 + 2 + 3. The first
few triangular numbers are 1, 3, 6, 10, 15, 21, 28, 36, 45, and 55. We
denote the nth triangular number by tn. Thus t5 = 1 + 2 + 3 + 4 + 5 =15.
More generally,
tn =1+2+3+ ... + (n−2) + (n−1) + n
The nth triangular number is given by the formula:
tn =1+2+3+ ... + n = n(n+1)/2
It should be noted that
tn − tn − 1 = n
The sum of any two consecutive triangular numbers is a square:
tn + tn − 1 = n2
A positive integer of the form n(n + 1) is called oblong. The nth oblong
number is the sum of the first n even numbers. To see this, observe that
the nth even number is 2n. Then we have 2 + 4 + 6 + ... + 2n =
2 (1+2+ ... + n) = 2(n (n+1)/2)= n (n+1) , the nth oblong number.
The sum of the first n odd numbers: The nth odd number is 2n − 1.
So 1+3+5+ ... + (2n−1) = (2×1−1) + (2×2−1) + (2×3−1) + ... + 2n−1 , in which -1 appears n times.
We then get
2 (1+2+3+ ... + n) - n = 2(n (n+1)/2) - n = n (n+1) - n = n2 + n - n = n2
So the sum of the first n odd numbers is n2
The Pythagoreans classified all numbers as deficient, abundant, or perfect. Given a number, find all of its proper factors, that is, all numbers that go into it (with the exclusion of the given number). The proper factors of 30, for example, are 1, 2, 3, 5, 6, 10, and 15.
If the sum of the proper factors of n is less than n, we call n deficient. If the sum exceeds n, it is called abundant. If the sum equals n, we call it perfect. For example, 8 is deficient since 1 + 2 + 4 < 8, 18 is abundant since 1 + 2 + 3 + 6 + 9 > 18, and 28 is perfect since 1 + 2 + 4 + 7 + 14 = 28. The smallest perfect number is 6. The first few perfect numbers are 6, 28, 496, and 8128.
A prime number is a number that has no divisors other than itself or 1.
A number that has divisors (or factors) other than itself and 1 is called composite.
A composite number must have a prime divisor.
In the sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,…, each term is the
sum of the preceding two terms. We denote these Fibonacci numbers by
u1, u2, u3, …. Thus, un is the nth Fibonacci number. Now, u1 = 1 and
u2 = 1 are the seed since they determine the rest of the terms.
The relationship between the general term and the two preceding terms is called the recursive relation and is
written as
un + 2 = un + un + 1
The sequence of ratios of the form
un + 1/ un, that is, the ratios consisting
of each term divided by its predecessor approach a limit. The limit is the famous irrational
number, denoted by the Greek letter Φ, known as the golden ratio (its approximate value is 1.618).
An equation of the form
x2 − ky2 = ±1
where k ≥ 2, is called a Pell equation.
Goldbach's conjecture:
Goldbach conjectured that every even number
greater than 4 is the sum of two odd primes.
n! or n factorial, is the product of the first n
positive integers, that is,
n! = n × n−1 × n−2 × ... × 3 × 2 × 1
\[
n! = \prod_{i=1}^{n}i
\]
We define 0! to be 1. There are n! permutations of n distinct objects.
Using recursion, factorial is
\begin{align}
0! = 1 \\
n! = n \cdot (n-1)! \hspace{1em} when \hspace{1em} n \geq 1
\end{align}
Given n distinct objects, in
how many ways can we select k of them where order does not matter?
We can deduce the following expression
\begin{align}
\binom{n}{k} = \frac{n!}{k!\left ( n-k \right )!} \\
equivalence: \hspace{1em} \binom{n}{n-k} = \binom{n}{k} \\
\end{align}
Each entry is the sum of the two entries immediately above it.
The Pascal's Triangle has many interesting properties.
the entries of the nth row of Pascal’s triangle
consist of the n + 1 combinatorial numbers:
\begin{align}
\binom{n}{0},\,\binom{n}{1}, \,\binom{n}{2}, ... , \binom{n}{n-2}, \,\binom{n}{n-1},\,\binom{n}{n}
\end{align}
These combinatorial numbers are the coefficients in the expansion
of (a + b)n and are often called binomial coefficients.
The Catalan numbers are defined by \[ c_{n} = \frac{1}{n+1}\binom{2n}{n} \] and are useful in combinatorics, number theory, and computer science. They satisfy the recurrence relation \[c_{n} = \frac{2(2n-1)}{n+1}c_{n-1}\] Find the first 100 Catalan numbers (i) using this recurrence and (ii) using the definition. Which is faster?
A factor of a number is called a divisor. Thus, 10 has the divisors 1, 2, 5, and 10. The divisors of n other than n are called proper divisors. The proper divisors of 10 are, therefore, 1, 2, and 5, while its divisors are 1, 2, 5, and 10. A divisor of n is said to divide n. Thus, 5 divides 10, while 7 does not divide 10. The symbol for “divides” is a vertical line. When a divides b, we write a | b. Whenever a divides b, observe that b is a multiple of a, that is, b = ka, for some integer k. Thus, 5 | 10, while 10 = 2 × 5. In fact, this is an “if and only if” statement: a divides b if and only if b is a multiple of a.
Here are a few laws of divisibility. All letters represent integers (whole numbers) unless otherwise stated:
Given a and b, we call d the greatest common divisor of a and b, denoted gcd(a,b), if:
If gcd(a,b) = 1, we say that a and b are relatively prime, that is, they have no common divisor other than 1.
Division: Given integers a and b, where a is positive, there exists a pair of numbers, q (for quotient) and r (for remainder), where 0 \( \leq \)r < a, such that b = qa + r.
So we can state gcd(a,b) = gcd(a, b − qa)
Euclid's algorithm pseudocode for finding the gcd of two numbers:
Division-based version
function gcd(a, b)
while b ≠ 0
t = b
b = a mod b
a = t
return a
Subtraction-based version
function gcd(a, b)
while a ≠ b
if a > b
a = a − b
else
b = b − a
return a
Recursive version
function gcd(a, b)
if b = 0
return a
else
return gcd(b, a mod b)
Given integers a and b, the smallest positive integer, c, such that a | c and b | c is called their least common multiple and is denoted lcm (a,b).
Relation LCM and GCD: \[ lcm(a,b) = \frac{a \times b}{gcd(a,b)} \]
Modular arithmetic sheds light on the relation of integers to their remainders when they are divided by a given positive integer.
ax = b (mod n), where a, b, and n are given, is a modular equation
The function \(\tau (n)\) counts how many divisors \(n\) has. This count includes 1 and \(n\).
The sum of the divisors of \(n\) is denoted \(\sigma (n)\).
The first few values of \(\sigma (n)\) are given by \(\sigma (1)\) = 1, \(\sigma (2)\) = 1 + 2 = 3, \(\sigma (3)\) = 1 + 3 = 4, \(\sigma (5)\) = 1 + 5 = 6, \(\sigma (6)\) = 1 + 2 + 3 + 6 = 12, \(\sigma (7)\) = 1 + 7 = 8, and \(\sigma (9)\) = 1 + 3 + 9 = 13.
A multiplicative function, f, satisfies:
1. f(1) = 1.
2. f(mn) = f(m)f(n) whenever gcd(m,n) = 1.
\(\tau (n)\) and \(\sigma (n)\) are examples of multiplicative functions.
Recall that a perfect number is the sum of its proper divisors. It follows that \(n\) is perfect if and only if \(\sigma (n) = 2n\), since \(\sigma\) counts \(n\) as a divisor.
For example, the perfect number 6 satisfies \(\sigma (6) = 1 + 2 + 3 + 6 = 12 = 2 × 6\)
Recall that a perfect number is the sum of its proper divisors. It follows that \(n\) is perfect if and only if \(\sigma (n) = 2n\), since \(\sigma\) counts \(n\) as a divisor.
For example, the perfect number 6 satisfies \(\sigma (6) = 1 + 2 + 3 + 6 = 12 = 2 × 6\)
The Riemann zeta function is defined by
\[ \zeta (s) = \sum_{n=1}^{\infty }\frac{1}{n^{s}}=1 +\frac{1}{2^{s}}+\frac{1}{3^{s}}+\frac{1}{4^{s}}+\cdots \]where \(s \) is a complex number with certain restrictions. If we restrict \(s \) to positive integer values, for example when s = 1, we obtain a divergent series. The eighteenth-century mathematician Euler showed, using calculus, that \( \zeta (2) = \frac{\pi^{2}}{6} \)
The number of positive integers less than \(n\) that are relatively prime to \(n\) is denoted \( \phi (n) \). The first few values of this important function, called the Euler \( \phi \) function, are given by \( \phi (1)=1 \), \( \phi (2)=1 \), \( \phi (3)=2 \), \( \phi (4)=2 \), \( \phi (5)=4 \), \( \phi (6)=2 \) (since only 1 and 5 are relatively prime to 6), \( \phi (7)=6 \), \( \phi (8)=4 \), \( \phi (9)=6 \), and \( \phi (10)=4 \).
Computing the Euler phi function from the definition can be done using a gcd function.
Fermat developed the following method of factoring large numbers:
If we wish to factor a large even number, \(n\), we observe that 2 is a factor and therefore divide by 2 and consider \( \frac{n}{2} \). If \( \frac{n}{2} \) is even, divide it by 2, note that \(4 = 2^{2} \) is a factor of \(n\), and consider \( \frac{n}{4} \). After k divisions by 2, we will reach an odd number, \(m\), and realize that \(n = 2^{k}m \). If m = 1, we are done. Otherwise, the problem of factoring \(n\) boils down to factoring the odd number \(m\). So Fermat dealt exclusively with the problem of factoring a large odd number.
If \(m = a^{2} - b^{2}\), where \(a - b \gt 1\), we have the nontrivial factorization \(m = (a + b)(a − b)\). Fermat developed a way to express m as the difference of two squares. That is, he tried to find \(a\) and \(b\) such that the given odd number \(m = a^{2} - b^{2}\) or \(a^{2} - m = b^{2}\). To do this, he found the smallest \(N\) for which \(N^{2} \gt m\). Then he considered the sequence \(N^{2} - m\), \((N + 1)^{2} - m\), \((N + 2)^{2} - m\),…, until he found a square. This enabled him to write \(m = a^{2} - b^{2} = (a + b)(a − b)\).
Example: Factor 119 using Fermat’s method. The smallest N for which \(N^{2} \gt 119\) is 11. Now, 112 − 119 = 121 − 119 = 2, which is not a square. We then examine 122 − 119 = 144 − 119 = 25, which is a square. Then 119 = 144 − 25 = (12 − 5)(12 + 5) = 7 × 17.