## Glossary

Binary quadratic form

Common factor

Coprime

Division

Euler totient function ( 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: , where , and are integers (and we are usually interested in integer values of the variables and . We also represent this form by its triple of coefficients , and by the matrix .

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

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.

Two whole numbers and are *coprime* if their highest common factor is 1.

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

**Euler totient function ( function)**

For each natural number , we define to be the number of elements of the set that are coprime to . Equivalently, is the size of the multiplicative group . This function is called the *Euler totient function*, or sometimes simply the *Euler function*. For example, if is prime then , and more generally . It turns out that is multiplicative, in the sense that if and are coprime then , so it suffices to study the behaviour of on prime powers. (Note that the condition that and are coprime is really important here!)

**Factorial**

The factorial function is a very useful shorthand. If is a positive integer, then we write , read as “ factorial”, for . For example, . It turns out to be convenient to define .

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: gets sent to . (Note: and both get sent to . That’s fine. Also, there’s no point that gets sent to . 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.)

A number is the *highest common factor* of two whole numbers and if it is a common factor of and , 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.

The integers are the whole numbers, …, -3, -2, -1, 0, 1, 2, 3, …. The set of integers is usually denoted by , 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 with prime factorisation (primes not necessarily distinct) and for any integer , we define the Jacobi symbol to be , where each is the Legendre symbol. Note that this definition means that knowing that is 1 does *not* tell us that is a quadratic residue modulo .

**Legendre symbol**

For a prime and for any integer , we can define the *Legendre symbol*, which we write as . This is defined to be if is a quadratic residue modulo , if is a quadratic non-residue modulo , and if is divisible by .

A function from the natural numbers to the natural numbers is said to be *multiplicative* if it satisfies whenever and are coprime. If a function satisfies this condition, then it suffices to understand its behaviour at prime powers .

If the function satisfies the stronger condition that for *all* natural numbers and , then we say that is *strictly multiplicative*.

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

1 2 1

1 3 3 1

1 4 6 4 1

The pigeonhole principle is sometimes called Dirichlet‘s box principle. It says that if you have pigeonholes and 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.

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 , and the prime factorisation of 2009 is .

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.

We say that is a *primitive root* modulo if it generates the multiplicative group . That is, every element of this group is a power for some suitable . Whether or not there is a primitive root depends on the value of ; not every multiplicative group is cyclic.

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.

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.

This is a fancy name for a square in the modular arithmetic world. Let be an integer coprime to the integer . Then we say that is a *quadratic residue* modulo if there is a solution to the congruence , 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 is prime.

The rational numbers, or rationals, are those that can be expressed as ratios of integers. Informally, they are the fractions. For example, , , and are all rationals, but is not — it is irrational. The set of rationals is usually denoted by , for quotients.

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 […]

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 […]

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.) […]

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 […]

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 […]

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 […]

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 […]

October 18, 2009 at 2:49 pm

[…] integers under addition. (The identity is , and the inverse of is […]

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 […]

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 […]

January 20, 2010 at 8:03 pm

[…] Let’s think about the numbers , , , …, . If we multiply them together, we get . (Here, means factorial.) […]

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 […]

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 […]

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 […]

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 […]

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 […]

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 […]

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 […]

October 7, 2011 at 12:50 pm

[…] of divisor and prime number. Definition of the prime counting function (which records the number of primes […]

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 […]

October 14, 2011 at 6:52 pm

[…] of primitive roots (in the statement of the above […]

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 […]

October 23, 2011 at 4:32 pm

[…] For each divisor of , there are exactly elements of order (where denotes the Euler totient function). […]

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 […]

October 27, 2011 at 12:31 pm

[…] Definition of binary quadratic forms. […]

November 7, 2011 at 12:51 pm

[…] Is a multiplicative function? […]

February 4, 2012 at 9:32 pm

[…] Here the symbol on the right-hand side of the congruence is the Legendre symbol. […]

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 […]

July 31, 2012 at 10:41 am

[…] fix an odd prime , and some number that is coprime to . We’d like to know whether is a quadratic residue modulo . Putting that another way, we’d like to find the value of the Legendre symbol . […]

October 16, 2013 at 10:41 am

[…] which we study the Euler totient function and polynomial […]

October 18, 2013 at 10:23 am

[…] of a primitive root modulo […]

October 21, 2013 at 10:36 am

[…] of quadratic residues and quadratic […]

October 30, 2013 at 4:27 pm

[…] Definition of a binary quadratic form. […]

November 11, 2013 at 12:10 pm

[…] Is a multiplicative function? […]