Glossary

Binary quadratic form
Common factor
Coprime
Division
Euler totient function ( $\phi$ function)
Factorial
Function
Highest common factor
Integers
Irrational numbers
Jacobi symbol
Legendre symbol
Multiplicative function
Pascal’s triangle
Pigeonhole principle
Prime factorisation
Prime number
Primitive root
Proof by contradiction
Proof by induction
Quadratic residue
Rational numbers

Binary quadratic form
A binary quadratic form is a quadratic polynomial in two variables with integer coefficients: $f(x,y) = ax^2 + bxy + cy^2$ , where $a$ , $b$ and $c$ are integers (and we are usually interested in integer values of the variables $x$ and $y$ . We also represent this form by its triple of coefficients $(a,b,c)$ , and by the $2 \times 2$ matrix $\begin{pmatrix} a & b/2 \\ b/2 & c \end{pmatrix}$ .

Common factor

A whole number is a common factor of two whole numbers $m$ and $n$ if it divides both $m$ and $n$ exactly (with no remainder). That is, it is a factor (or divisor) of both $m$ and $n$ .

For example, let’s find the common factors of 12 and 32. The factors of 12 are 1, 2, 3, 4, 6 and 12. The factors of 32 are 1, 2, 4, 8, 16 and 32. So the common factors of 12 and 32 are 1, 2 and 4.

Coprime

Two whole numbers $m$ and $n$ are coprime if their highest common factor is 1.

Division

We say that the non-zero integer $a$ divides the integer $b$ if there is an integer $k$ such that $b = ka$ . In this case we write $a | b$ (read as “ $a$ divides $b$ ”). We say that $a$ is a divisor or factor of $b$ , and that $b$ is a multiple of $a$ .

Euler totient function ( $\phi$ function)

For each natural number $n$ , we define $\phi(n)$ to be the number of elements of the set $\{1, 2, \dotsc, n-1 \}$ that are coprime to $n$ . Equivalently, $\phi(n)$ is the size of the multiplicative group $(\mathbb{Z}/n\mathbb{Z})^{\times}$ . This function $\phi$ is called the Euler totient function, or sometimes simply the Euler $\phi$ function. For example, if $p$ is prime then $\phi(p) = p-1$ , and more generally $\phi(p^j) = p^{j-1}(p-1)$ . It turns out that $\phi$ is multiplicative, in the sense that if $m$ and $n$ are coprime then $\phi(mn) = \phi(m)\phi(n)$ , so it suffices to study the behaviour of $\phi$ on prime powers. (Note that the condition that $m$ and $n$ are coprime is really important here!)

Factorial
The factorial function is a very useful shorthand. If $n$ is a positive integer, then we write $n!$ , read as “ $n$ factorial”, for $n! = n \times (n-1) \times (n-2) \times \dotsm \times 3 \times 2 \times 1$ . For example, $7! = 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 5040$ . It turns out to be convenient to define $0! = 1$ .

Function

A function is a map that takes members of one set and maps them to members of another set. The input set is called the domain, and the output set the codomain. The one rule is that the function must map each element of the domain to exactly one element in the codomain. (Every element gets sent somewhere, and no element gets sent to more than one place.)

One point to note is that two elements of the domain may be sent to the same element of the codomain. Another is that there can be elements of the codomain that are not outputs of the function. Thirdly, the function doesn’t have to be be given by any tidy formula.

Technically, one has to specify the domain and codomain as well as the map when defining a function. In practice, sometimes one doesn’t specify the domain and codomain, because it is implicitly clear.

Here are some examples of functions.

Domain: the whole numbers. Codomain: the real numbers. Map: $n$ gets sent to $n^2$ . (Note: $4$ and $-4$ both get sent to $16$ . That’s fine. Also, there’s no point that gets sent to $\pi$ . That’s also fine.)

Domain: the positive whole numbers. Codomain: the set {RED, BLUE}. Map: an odd number gets sent to RED, an even number gets sent to BLUE.

Domain: the positive whole numbers. Codomain: the positive whole numbers. Map: 1, 3, 5 and 7 get sent to 17. Prime numbers greater than or equal to 11 get sent to 101. Composite numbers and 2 get sent to 100000000. (An entirely artificial function, just to try to demonstrate that the map doesn’t have to be specified by a single rule. As long as each element of the domain gets sent to a unique point of the codomain, it’s a function.)

Highest common factor

A number is the highest common factor of two whole numbers $m$ and $n$ if it is a common factor of $m$ and $n$ , and any other common factor is smaller.

For example, the common factors of 12 and 32 are 1, 2 and 4, so the highest common factor is 4.

Integers

The integers are the whole numbers, …, -3, -2, -1, 0, 1, 2, 3, …. The set of integers is usually denoted by $\mathbb{Z}$ , from the German word “Zahlen” (meaning numbers).

Irrational numbers
The irrational numbers are those numbers that are not rational.

Jacobi symbol
This is a generalisation of the Legendre symbol. For an odd natural number $n$ with prime factorisation $n = p_1 p_2 \dotsb p_k$ (primes $p_i$ not necessarily distinct) and for any integer $a$ , we define the Jacobi symbol to be $\genfrac{(}{)}{}{}{a}{n} = \genfrac{(}{)}{}{}{a}{p_1} \genfrac{(}{)}{}{}{a}{p_2} \dotsb \genfrac{(}{)}{}{}{a}{p_k}$ , where each $\genfrac{(}{)}{}{}{a}{p_i}$ is the Legendre symbol. Note that this definition means that knowing that $\genfrac{(}{)}{}{}{a}{n}$ is 1 does not tell us that $a$ is a quadratic residue modulo $n$ .

Legendre symbol
For a prime $p$ and for any integer $a$ , we can define the Legendre symbol, which we write as $\genfrac{(}{)}{}{}{a}{p}$ . This is defined to be $1$ if $a$ is a quadratic residue modulo $p$ , $-1$ if $a$ is a quadratic non-residue modulo $p$ , and $0$ if $a$ is divisible by $p$ .

Multiplicative function

A function $f: \mathbb{N} \to \mathbb{N}$ from the natural numbers to the natural numbers is said to be multiplicative if it satisfies $f(mn) = f(m) f(n)$ whenever $m$ and $n$ are coprime. If a function satisfies this condition, then it suffices to understand its behaviour at prime powers $p^j$ .

If the function satisfies the stronger condition that $f(mn) = f(m) f(n)$ for all natural numbers $m$ and $n$ , then we say that $f$ is strictly multiplicative.

Pascal’s triangle

A triangle of numbers arranged in rows. Each number is the sum of the two above it (one number just to the left, one just to the right). Here are the first few rows of Pascal‘s triangle.

1 1

1 2 1

1 3 3 1

1 4 6 4 1

Pigeonhole principle

The pigeonhole principle is sometimes called Dirichlet‘s box principle. It says that if you have $k$ pigeonholes and $k+1$ pigeons, then at least one pigeonhole contains at least two pigeons.

For example, imagine that I have seven pairs of socks, each pair being of a different colour. I have been too lazy to pair the socks before putting them into my sock drawer. When I get up in the morning, I want to get a pair of matching socks. If I take out eight socks, then I must have two that are the same colour. Here, the “pigeonholes” are the colours, and the “pigeons” the socks.

The pigeonhole principle was Theorem 11, so you can read more about it there.

Prime factorisation

Every positive whole number can be written as a product of prime numbers. Moreover, there’s a unique way to do this (if we don’t count reorderings of the factors as different expressions). The resulting factorisation is called the prime factorisation. The fact that there is a unique factorisation is a theorem in itself, the Fundamental Theorem of Arithmetic.

For example, the prime factorisation of 12 is $2\times 2\times 3$ , and the prime factorisation of 2009 is $7\times 7\times 41$ .

Prime number

A positive whole number greater than 1 that is divisible only by itself and by 1 is called a prime number. We define 1 not to be prime, because that turns out to be a convenient definition.

For example, the primes less than 100 are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, and 97.

Primitive root

We say that $a$ is a primitive root modulo $n$ if it generates the multiplicative group $(\mathbb{Z}/n \mathbb{Z})^{\times}$ . That is, every element of this group is a power $a^j$ for some suitable $j$ . Whether or not there is a primitive root depends on the value of $n$ ; not every multiplicative group is cyclic.

Proof by contradiction

This is a method of proof, also called reductio ad absurdum. If you want to read about it, I suggest this NRICH article. But if you’re in a hurry, here’s a very quick summary. Suppose that the thing you want to prove is false. Deduce some things from that supposition that somehow lead to a contradiction. Since the supposition led to a contradiction, it must itself have been false. That is, the thing you wanted to prove must be true.

Proof by induction

This is a method of proof. Rather than try to give a description here, I’ll refer you to a short article that I wrote for NRICH.

Quadratic residue

This is a fancy name for a square in the modular arithmetic world. Let $a$ be an integer coprime to the integer $n$ . Then we say that $a$ is a quadratic residue modulo $n$ if there is a solution to the congruence $x^2 \equiv a \pmod{n}$ , and a quadratic non-residue if there is not a solution to that congruence. The Legendre symbol gives a convenient way to record this in the case when $n$ is prime.

Rational numbers

The rational numbers, or rationals, are those that can be expressed as ratios of integers. Informally, they are the fractions. For example, $1/2$ , $-123456/789$ , $17=17/1$ and $0$ are all rationals, but $\sqrt{2}$ is not — it is irrational. The set of rationals is usually denoted by $\mathbb{Q}$ , for quotients.

Like this:

Be the first to like this page.

28 Responses to “Glossary”

Theorem 1: Bézout’s Theorem « Theorem of the week Says:
August 5, 2009 at 9:52 pm
[...] we get litres in the pond, and that’s certainly a multiple of 3. The problem was that the highest common factor of the capacities was 3, and that doesn’t divide our target amount [...]
Theorem 3: Vinogradov’s Three Primes Theorem « Theorem of the week Says:
August 10, 2009 at 9:36 pm
[...] Conjecture (Goldbach) Every even number greater than 2 can be written as the sum of two primes (a prime plus a [...]
Theorem 4: van der Waerden’s theorem « Theorem of the week Says:
August 18, 2009 at 8:51 pm
[...] We had and proved the cases and . (The case of is not very interesting!) The proof of the general theorem uses the same ideas that we used above, using the result for smaller values of and to deduce the next step up. (This is a rather vague description of proof by induction.) [...]
Theorem 5: the square root of 2 is irrational « Theorem of the week Says:
August 24, 2009 at 8:29 pm
[...] think about the power of 2 in the prime factorisation of each side. (This is assuming the Fundamental Theorem of Arithmetic, which tells us that [...]
Theorem 6: the Binomial Theorem « Theorem of the week Says:
September 3, 2009 at 9:25 pm
[...] noticed a similarity between the first few powers of 11 and the first few rows of Pascal’s triangle? I’ll write them out, so that you can compare them. Here are the first few powers of [...]
Theorem 7: the Banach-Tarski paradox « Theorem of the week Says:
September 7, 2009 at 9:03 pm
[...] we can define a proper notion of mass. So what’s the problem? I rather glossed over the domain of the function. That is, I didn’t tell you which sets have masses. The measure that mathematicians use [...]
Theorem 8: Eulerian circuits « Theorem of the week Says:
September 29, 2009 at 10:02 pm
[...] not quite as easy to prove (although it’s not terribly difficult). One proof is by induction on the number of edges in the graph. That is, one shows that it’s true when there are no [...]
Theorem 10: Lagrange’s theorem in group theory « Theorem of the week Says:
October 18, 2009 at 2:49 pm
[...] integers under addition. (The identity is , and the inverse of is [...]
Theorem 11: the pigeonhole principle « Theorem of the week Says:
October 25, 2009 at 9:59 pm
[...] I mentioned above, Dirichlet used this principle to prove a result about approximating irrational numbers by rationals. The square root of 2 is irrational, but is it close to a rational? That’s a [...]
Theorem 12: there are infinitely many primes « Theorem of the week Says:
November 1, 2009 at 8:09 pm
[...] many primes By theoremoftheweek As you might have already gathered from this blog, the prime numbers are pretty key in mathematics, and in particular in number theory (roughly speaking, the study of [...]
Theorem 14: Fermat’s Little Theorem « Theorem of the week Says:
January 20, 2010 at 8:03 pm
[...] Let’s think about the numbers , , , …, . If we multiply them together, we get . (Here, means factorial.) [...]
Theorem 17: Dirichlet’s theorem « Theorem of the week Says:
February 16, 2010 at 10:20 pm
[...] immediately. But what if a and q have no common factor greater than 1: what if a and q are coprime? Then we have no obvious reason why there shouldn’t be infinitely many primes leaving [...]
Theorem 19: there is a transcendental number « Theorem of the week Says:
March 3, 2010 at 9:37 pm
[...] of a transcendental number is Liouville’s number, which is defined to be . (Here denotes factorial.) So its decimal expansion starts [...]
Theorem 27: Wilson’s theorem « Theorem of the week Says:
May 28, 2010 at 10:00 pm
[...] theorem, I suggested multiplying together the p-1 numbers a, 2a, …, (p-1)a (where a is coprime to the prime p), to get . (As usual, I’m writing (p-1)! for p-1 factorial.) But, as [...]
Theorem 30: Pythagorean triples « Theorem of the week Says:
June 27, 2010 at 6:47 pm
[...] aren’t all divisible by some number (they have no common factor bigger than 1: they are coprime). These are called primitive solutions. So I’m interested in (3,4,5) and (5, 12, 13), but [...]
Theorem 35: the best rational approximations come from continued fractions « Theorem of the week Says:
September 8, 2010 at 8:13 pm
[...] seen how to write certain rational numbers (namely ratios of consecutive Fibonacci numbers) as finite continued fractions. Is this a special [...]
Theorem 2: the Intermediate Value Theorem « Theorem of the week Says:
August 15, 2011 at 11:42 am
[...] be slightly more mathematical about all this. We have a function, , say, that takes the positions of the knob and maps them to how fast or slow the clock runs. If [...]
Theorem 18: the rational numbers are countable « Theorem of the week Says:
August 15, 2011 at 12:26 pm
[...] (whole numbers) as natural numbers (positive whole numbers)? And are there the same number of rational numbers (fractions) as natural [...]
Number Theory: Lecture 1 « Theorem of the week Says:
October 7, 2011 at 12:50 pm
[...] of divisor and prime number. Definition of the prime counting function (which records the number of primes [...]
Number Theory: Lecture 3 « Theorem of the week Says:
October 14, 2011 at 12:18 pm
[...] 11: The Euler totient function is multiplicative, in the sense that if and are coprime, then . (So we can sometimes reduce problems to studying [...]
Number Theory: Lecture 4 « Theorem of the week Says:
October 14, 2011 at 6:52 pm
[...] of primitive roots (in the statement of the above [...]
Theorem 29: the law of quadratic reciprocity « Theorem of the week Says:
October 20, 2011 at 11:26 am
[...] that 3 is a quadratic non-residue (mod 4) (because 3 is not a square (mod 4)). 0 and 2 are not coprime to the modulus 4, so we don’t call them quadratic residues or quadratic [...]
Theorem 38: There is a primitive root modulo a prime « Theorem of the week Says:
October 23, 2011 at 4:32 pm
[...] For each divisor of , there are exactly elements of order (where denotes the Euler totient function). [...]
Number Theory: Lecture 8 « Theorem of the week Says:
October 24, 2011 at 12:20 pm
[...] Jacobi symbol for an integer and an odd natural number . We noted the important point that does not mean [...]
Number Theory: Lecture 9 « Theorem of the week Says:
October 27, 2011 at 12:31 pm
[...] Definition of binary quadratic forms. [...]
Number Theory: Lecture 14 « Theorem of the week Says:
November 7, 2011 at 12:51 pm
[...] Is a multiplicative function? [...]
Theorem 39: Euler’s criterion « Theorem of the week Says:
February 4, 2012 at 9:32 pm
[...] Here the symbol on the right-hand side of the congruence is the Legendre symbol. [...]
Waring’s Problem: Lecture 7 « Theorem of the week Says:
May 11, 2012 at 12:05 pm
[...] time, we shall prove Lemma 16 and then that the function is multiplicative (in the usual sense), and we’ll then move on to show that the local factors are all positive (by showing that [...]

Theorem of the week

Glossary

Like this:

28 Responses to “Glossary”

Leave a Reply Cancel reply

Pages

Archives

Categories

Links

Meta

Follow “Theorem of the week”