Introduction

There is a beauty to the ways in which numbers interact with one another, just as there is a beauty in the composition of a painting or a symphony. To appreciate this beauty, one has to be willing to expend a certain amount of mental energy. But the end result is well worth the effort.

Pure mathematics is the study of mathematical concepts independently of any application outside mathematics. These concepts may originate in real-world concerns, and the results obtained may later turn out to be useful for practical applications, but the pure mathematicians are not primarily motivated by such applications. Instead, the appeal is attributed to the intellectual challenge.

Number theory is a branch of pure mathematics devoted primarily to the study of the integers. It is the study of the set of positive whole numbers

1, 2, 3, 4, 5, 6, 7, ... ,

which are often called the set of natural numbers. The main goal of number theory is to discover interesting and unexpected relationships between different sorts of numbers and to prove that these relationships are true. Since ancient times, people have separated the natural numbers into a variety of different types. Here are some familiar and not-so-familiar examples:

odd 1, 3, 5, 7, 9, 11, . . .
even 2, 4, 6, 8, 10, . . .
square 1, 4, 9, 16, 25, 36, . . .
cube 1, 8, 27, 64, 125, . . .
prime 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, . . .
composite 4, 6, 8, 9, 10, 12, 14, 15, 16, . . .
1 (modulo 4) 1, 5, 9, 13, 17, 21, 25, . . .
3 (modulo 4) 3, 7, 11, 15, 19, 23, 27, . . .
triangular 1, 3, 6, 10, 15, 21, . . .
perfect 6, 28, 496, . . .
Fibonacci 1, 1, 2, 3, 5, 8, 13, 21, . . .

Many of these types of numbers are undoubtedly already known to you. Others, such as the 1 modulo 4 numbers, may not be familiar. A number is said to be congruent to 1 (modulo 4) if it leaves a remainder of 1 when divided by 4, and similarly for the 3 (modulo 4) numbers. A number is called triangular if that number of pebbles can be arranged in a triangle, with one pebble at the top, two pebbles in the next row, and so on. A number is perfect if the sum of all its divisors, other than itself, adds back up to the original number.

Example number theory questions:

  • Can the sum of two squares be a square? (Answer: YES)
  • Can the sum of two cubes be a cube? Can the sum of two fourth powers be a fourth power? In general, can the sum of two nth powers be an nth power? This famous problem is called Fermat’s Last Theorem (Answer: NO)

  • Which (odd) prime numbers are a sum of two squares?

    3 = NO, 5 = 12 + 22, 7 = NO, 11 = NO,
13 = 22 + 32, 17 = 12 + 42
19 = NO, 23 = NO, 29 = 22 + 52, 31 = NO, 
37 = 12 + 62, ...

    Do you see a pattern? Possibly not, since this is only a short list, but a longer list leads to the conjecture that p is a sum of two squares if it is congruent to 1 (modulo 4). In other words, p is a sum of two squares if it leaves a remainder of 1 when divided by 4, and it is not a sum of two squares if it leaves a remainder of 3!

The best known application of number theory is public key cryptography, such as the RSA algorithm. Public key cryptography in turn enables many technologies we take for granted, such as the ability to make secure online transactions. Trillions of dollars moves securely on internet due to Number Theory.

Order of a group

The order of a group is its cardinality, i.e., the number of elements in its set. If we have a group G, order of G is denoted by |G|

Order of an element

Order of an element a of a group is the smallest positive integer m such that am = e (where e denotes the identity element of the group, and am denotes the product of m copies of a). If no such m exists, a is said to have infinite order.

Group

A group G is a finite or infinite set of elements together with a binary operation (called the group operation) that together satisfy the four fundamental properties of closure, associativity, the identity property, and the inverse property. The operation with respect to which a group is defined is often called the “group operation,” and a set is said to be a group “under” this operation.

A group is a non-empty set (finite or infinite) G with a binary operator • such that the following four properties (Cain) are satisfied:

  • Closure: if a and b belong to G, then a•b also belongs to G
  • Associative: a•(b•c)=(a•b)•c for all a, b, c in G
  • Identity element: there is an element e in G such that a•e = e•a = a for every element a in G
  • Inverse element: for every element a in G, there’s an element a’ such that a•a’ = e where e is the identity element

We usually denote a group by (G, •) or simply G when the operator is clear in the context. One very common type of group is the cyclic groups. This group is isomorphic to the group of integers (modulo n), is denoted Zn, or Z/nZ, and is defined for every integer n > 1.

Cyclic groups

A cyclic group is a group that can be generated by a single element X (the group generator). It contains an element g such that every other element of the group may be obtained by repeatedly applying the group operation or its inverse to g. Each element can be written as a power of g in multiplicative notation, or as a multiple of g in additive notation. This element g is called a generator of the group.

Wait! Set of integers with identity element 0 and addition operation is not cyclic in any sense. How’s that a cyclic group?

I had the exact same question! The name “cyclic” is misleading. It is possible to generate infinitely many elements and not form any literal cycles; that is, every gn is distinct. (It can be thought of as having one infinitely long cycle)

Infinitely long cycle doesn’t make any sense! Why cyclic?

Please don’t argue. They had better things to do I guess. Read this for more information.

Important Properties:

  • Every cyclic group is Abelian1
  • Every infinite cyclic group is isomorphic to the additive group of Z, the integers.
  • Every finite cyclic group of order n is isomorphic to the additive group of Z/nZ, the integers modulo n.

A trivial example is the group Zn, the additive group of integers modulo n. In Zn, 1 is always a generator:

1 ≡ 1 mod n

1+1 ≡ 2 mod n

1+1+1 ≡ 3 mod n …

1+1+1+…+1 ≡ n ≡ 0 mod n

If a group is cyclic, then there may exist multiple generators. For example, we know Z5 is a cyclic group. 1 is a generator for sure. And if we take a look at 2, we can find:

2 ≡ 2 mod 5

2+2 ≡ 4 mod 5

2+2+2 ≡ 6 ≡ 1 mod 5

2+2+2+2 ≡ 8 ≡ 3 mod 5

2+2+2+2+2 ≡ 10 ≡ 0 mod 5

So all the group elements {0,1,2,3,4} in Z5 can also be generated by 2. So, 2 is also a generator for the group Z5.

However, not every element in a group is a generator. For example, the identity element in a group will never be a generator. No matter how many times you apply the group operator to the identity element, the only element you can yield is the identity element itself. For example, in Zn, 0 is the identity element and 0+0+…+0 ≡ 0 mod n in all cases.

Not every group is cyclic. For example, Zn*, the multiplicative group modulo n, is cyclic if and only if n is 1 or 2 or 4 or pk or 2*pk for an odd prime number p and k ≥ 1. So Z5* must be a cyclic group because 5 is a prime number. 2 is a generator.

21 ≡ 2 mod 5

22 ≡ 4 mod 5

23 ≡ 8 ≡ 3 mod 5

24 ≡ 16 ≡ 1 mod 5

If Zn* is cyclic and g is a generator of Zn*, then g is also called a primitive root modulo n

Order of a modulo n

Given a positive integer n > 1, and an integer a, such that gcd(a, n) = 1, the smallest possible integer d for which ad ≡ 1 mod n is called order of a modulo n. Since Euler’s theorem states that aφ(n) ≡ 1 mod n , d indeed exists. The order of a mod n is sometimes written as ordn(a)

Euler’s totient function

In number theory, Euler’s totient function counts the positive integers up to a given integer n that are relatively prime to n. It is written using the Greek letter phi as φ(n) or ϕ(n), and may also be called Euler’s ph function. It can be defined more formally as the number of integers k in the range 1 ≤ k ≤ n for which the greatest common divisor gcd(n, k) i s equal to 1

The following table shows the function values for the first several natural numbers:

n coprimes of n φ(n)
3 1, 2 2
4 1, 3 2
5 1, 2, 3, 4 4
6 1, 5 2
7 1, 2, 3, 4, 5, 6 6
8 1, 3, 5, 7 4
9 1, 2, 4, 5, 7, 8 6
10 1, 3, 7, 9 4
11 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 10
12 1, 5, 7, 11 4

Take some time and try to find a cool relationship between n and φ(n).

Here’s the relation: when n is a prime number (e.g. 2, 3, 5, 7, 11, 13), φ(n) = n-1.

How about the composite numbers?

You may also have noticed that,

15 = 3*5 and φ(15) = φ(3)*φ(5) = 2*4 = 8 This is also true for 14,12,10 and 6. However, it does not hold for 4, 8, 9.

For example, 9 = 3 * 3 , but φ(9) = 6 ≠ φ(3)*φ(3) = 2 * 2 =4

In fact, this multiplicative relationship is conditional: when m and n are coprime, φ(m*n) = φ(m)*φ(n)

The general formula to compute φ(n) is the following:

If the prime factorisation of n is given by n =p1e1 *…* pnen, then φ(n) = n *(1 - 1/p1)* … (1 - 1/pn)

For example:

  • 9 = 32, φ(9) = 9* (1-1/3) = 6
  • 4 =22, φ(4) = 4* (1-1/2) = 2

Euler’s theorem

Also known as Fermat-Euler theorem or Euler’s totient theorem

If n and a are coprime positive integers, then aφ(n) ≡ 1 mod n

The converse of Euler’s theorem is also true: if the above congruence is true, then a and n must be coprime

Primitive root modulo

Let p be a prime. We say that g is a primitive root of p (or sometimes modulo p), if the powers g1, g2, g3, …, gp-1 are congruent, in some order, to 1, 2, 3, …, p-1 (modulo p). Or in simpler terms, when we consider the remainders when gk is divided by p, all numbers between 1 and p-1 are remainders (0 can’t be).

Note that by Fermat’s Theorem, gp-1 ≡ 1 mod p, so after gp-1, the powers of g start all over again modulo p, so gp ≡ g, gp+1 ≡ g2 and so on.

Using our knowledge of group theory, we could alternately say that g is a primitive root of p if g is a generator of the multiplicative group on non-zero objects modulo p. It can be proved using elementary tools that every prime has a primitive root. The proof is not all that easy though. Large primes p have many primitive roots.

Credits

Footnotes

  1. An Abelian group is a group for which the elements commute (i.e., AB=BA for all elements A and B) ↩