Basics of number theory

In this section, we’ll introduce the basic concepts of number theory, which are later used to determine the properties of algebraic structures. We denote the set of integers by the symbol

Z={,2,1,0,1,2,}\mathbb{Z} = \{\cdots,-2,-1,0,1,2,\cdots\}. The following statements hold for the usual addition, subtraction, and multiplication:

Lemma 1: closure property

Let a, b ∈ Z\mathbb{Z}.

Then, the following hold:

  1. a+bZ a+b \in \mathbb{Z}
  2. abZ a-b \in \mathbb{Z}
  3. abZ a \cdot b \in \mathbb{Z}

This means that the common addition, subtraction, and multiplication operations yield an integer as a result. We say that the set of integers is closed under these operations (we’ll learn this concept in detail in the next lessons).

In contrast, the division of two integers a and b isn’t necessarily yielding an integer as a result, thus, the integers aren’t closed with respect to the division. For example, we can’t divide 33 by 22 because 32Z\frac{3}{2} \notin \mathbb{Z}. As a consequence, we need a fundamental concept of divisibility in number theory.

Divisibility

Let a,b ∈ Z with b ≠ 0. We say that bb divides aa, or aa is divisible by bb, if there exists an nn ∈ Z such that: a=nba=n⋅b

If b divides a, we write bab \mid a, otherwise, we write bab \nmid a.

Example: It holds that 133913 \mid 39, since 39=31339 = 3 *13 . On the other hand, 134013 \nmid 40.

The following lemma states some elementary divisibility properties.

Lemma 2: properties of divisibility

Let a,b,cZa, b , c \in \mathbb{Z}⧵{0}.
Then:

  1. If aba \mid b, then acbcac \mid bc, and vice versa.
  2. Transitive property: If aba \mid b and bcb \mid c, then aca \mid c.
  3. If nan \mid a and nbn \mid b, then n(a+b)n \mid (a+b) and n(ab)n \mid (a-b).

Proof:

  1. Since aba \mid b, there exists an nZn \in \mathbb{Z} such that b=nab=n \cdot a. It follows that bc=nac=n(ac)b \cdot c=n \cdot a \cdot c=n \cdot(a \cdot c) and hence acbca c \mid b c. For the reverse direction, we observe that acbca c \mid b c requires an nZn \in \mathbb{Z} so that bc=n(ac)=nacb \cdot c=n \cdot(a \cdot c)=n \cdot a \cdot c. Since c0c \neq 0, it follows that b=nab=n \cdot a and hence aba \mid b.
  2. aba \mid b and bcb \mid c imply that there exist m,nZm, n \in \mathbb{Z} so that we can write b=mab=m \cdot a and c=nbc=n \cdot b, respectively. It follows that c=nb=nma=c=n \cdot b=n \cdot m \cdot a= (nm)a(n \cdot m) \cdot a, and thus aca \mid c.
  3. nan \mid a and nbn \mid b imply the existence of m1,m2Zm_{1}, m_{2} \in \mathbb{Z} so that a=m1na=m_{1} \cdot n and b=m2n.b=m_{2} \cdot n . This yields a±b=m1n±m2n=(m1±m2)na \pm b=m_{1} \cdot n \pm m_{2} \cdot n=\left(m_{1} \pm m_{2}\right) \cdot n and hence n(a±b)n \mid(a \pm b).
# isDivisible : returns 1, if a divides b (a|b)
# parameters a and b
def isDivisible(a, b):
if b%a == 0:
return 1
else:
return 0
# Feel free to change value of a and b
a = 13
b = 39
print(a , " | ", b, " = ", 'true' if isDivisible(a,b)== 1 else 'false' )

Greatest common divisor

A positive integer nn \in N\mathbb{N} is called a common divisor of two integers aa and bb, if nn divides both of them. The greatest common divisor of a and b is the largest integer nn such that nan \mid a and nbn \mid b and is denoted by gcd(a,b)gcd(a, b).

Note: Especially, gcd(1,n)=1gcd(1, n) = 1 and gcd(0,n)=ngcd(0, n) = n.

Example: gcd(48,72)=24gcd(48, 72) = 24 since 244824 \mid 48 and 247224 \mid 72, and there’s no larger number than 2424, which fulfils this property.

# GCD : Returns the GCD of a and b
# Parameters a and b
def GCD(a, b):
if (a == 0):
return b
elif (a == 1):
return 1
else:
return GCD(b%a, a)
# Feel free to change value of a and b
a = 48
b = 72
if (a > b):
print("invalid input, a must be <= to b")
else:
print("GCD of ", a, " and ", b ," = ", GCD(a,b))

Prime numbers:

Let pp be a positive integer p2p \geq 2. Then, pp is said to be a prime if its only divisors are 11 and pp itself, i.e.,

gcd(a,p)=1gcd(a,p) = 1

for all 0a<p0 \le a < p.

Note: 11 is a prime number because 1 can be divided by 1 and the number itself, which is also 1.

Example:

All the primes smaller than 2020 are 2,3,5,7,11,13,17,192, 3, 5, 7, 11, 13, 17, 19. For example, 66 is not a prime since 6=236 = 2 \cdot 3, and hence, 22 and 33 are divisors of 66.

Theorem 1: fundamental theorem of arithmetic

Every positive integer n2n \ge 2 can be represented as a product of prime powers

n=p1α1p2α2pkαk=i=1kpiαin=p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \cdots p_{k}^{\alpha_{k}}=\prod_{i=1}^{k} p_{i}^{\alpha_{i}}

This factorization is unique apart from the rearrangement of the prime powers.

Note: The greatest common divisor of two numbers aa and bb can be computed by determining their prime factorizations, whereas the greatest common divisor is the product of all common prime powers of aa and bb. This is depicted in the above figure using the prime factorization tree.

Example:

Consider the two numbers 4848 and 7272. Their prime factorizations are given by 48=24.3 48=2^{4} . {3} and 72=23.3272 = 2^3 . 3^2 . We observe that a and b have common prime powers 232^3 and 33, and therefore gcd(a,b)=23.3=24gcd(a, b) = 2^3 . 3 = 24.

Theorem 2: there are infinitely many primes

Proof:

Suppose that there’s a complete finite list of primes p1,p2,,pkp_{1}, p_{2}, \cdots, p_{k}. We construct the two integers n1=p1p2pkn_{1} = p_{1} \cdot p_{2} \cdots p_{k} and n2=p1p2pk+1n_{2} = p_{1} \cdot p_{2} \cdots p_{k}+1. By the fundamental theorem of arithmetic, every integer is a product of primes divisible by at least one prime. Since n1n_{1} is a product of all primes, there’s a prime pp such that pn1p \mid n_{1} and pn2p \mid n_{2}. According to Lemma 2: properties of divisibility, pn1p \mid n_{1} and pn2p \mid n_{2} imply that p(n2n1)p \mid (n_2 - n_1). Hence, p(p1p2pk+1p1.p2pk)=1p \mid (p_{1} \cdot p_{2} \cdots p_{k} + 1 - p_{1} . p_{2} \cdots p_{k} )=1, which means that pp divides 1. But this isn’t possible since pp is a prime, and therefore p2p \geq 2. Thus, a list of finite primes can’t exist as pp will not be a member of it.

Relatively prime (or coprime)

Two integers aa and bb are said to be relatively prime (or coprime) if gcd(a,b)=1gcd(a, b) = 1.

Example:

We consider the following two cases:

  1. 2121 and 2222 are relatively prime, since 21=3721 = 3 \cdot 7 and 22=21122 = 2 \cdot 11. Thus, they have no common prime factors, and therefore gcd(21,22)=1gcd(21, 22) = 1.
  2. 2121 and 2424 are not relatively prime, since 21=3721 = 3 \cdot 7 and 24=23324 = 2^3 \cdot 3, and therefore gcd(21,24)=3gcd(21, 24) = 3.

Lemma 3: Bézout’s identity

For any nonzero integers a,bZa, b \in \mathbb{Z}, let d be the greatest common divisor d=gcd(a,b)d = gcd(a, b). Then, there exist x,yZx, y \in \mathbb{Z} such that

ax+by=dax+by = d

Corollary 1

Two integers a,bZ{0}a, b \in \mathbb{Z} \setminus \begin{Bmatrix} 0 \end{Bmatrix} are co-prime if and only if there exist x,yZx, y \in \mathbb{Z} such that

ax+by=1ax+by = 1

Proof:

Two integers a,ba, b are relatively prime if and only if gcd(a,b)=1gcd(a, b) = 1. Then, it’s a direct consequence of Bézout’s lemma that there exists x,yZx, y \in \mathbb{Z} such that ax+by=gcd(a,b)=1ax+by = gcd(a,b) = 1.

Lemma 4

Let a,bZ{0}a , b \in \mathbb{Z} \setminus \begin{Bmatrix} 0 \end{Bmatrix} and nNn\in \mathbb{N}. If aa and bb are coprime to nn, then it’s also its product aba\cdot b, i.e., if gcd(a,n)=gcd(b,n)=1gcd(a, n) = gcd(b, n) = 1, then gcd(ab,n)=1gcd(ab, n) = 1.

Proof:

Suppose that gcd(a,n)=gcd(b,n)=1gcd(a, n) = gcd(b, n) = 1. As discussed earlier , there exist s,t,x,yZs, t, x, y \in \mathbb{Z} such that as+nt=1as + nt = 1 and bx+ny=1bx + ny = 1, and thus, in total

(as+nt)(bx+ny)=1(as + nt)(bx + ny) = 1

It follows that

absx+ansy+bntx+nnty=absx+n(asy+btx+nty)=1.a b s x+a n s y+b n t x+n n t y=a b \cdot s x+n \cdot (a s y+b t x+n t y)=1.

Here, sxZsx \in \mathbb{Z} and (asy+btx+nty)Z(a s y+b t x+n t y) \in \mathbb{Z}.

By applying again the corollary discussed earlier, we conclude that gcd(ab,n)=1gcd(ab, n) = 1.

Lemma 5

Let a,bZa, b \in \mathbb{Z}, and let d=gcd(a,b)d = gcd(a, b). Then, the two integers ad\frac{a}{d} and bd\frac{b}{d} are relatively prime, i.e., gcd(ad,bd)=1gcd ( \frac{a}{d} , \frac{b}{d} ) = 1.

Proof:

According to the fundamental theorem of arithmetic , we define aa and bb as a product of prime powers, i.e., a=i=1kpiαia = \prod_{i=1}^{k} p_{i}^{\alpha_{i}} and b=i=1lpiβib = \prod_{i=1}^{l} p_{i}^{\beta_{i}}. Then, d=gcd(a,b)=s=1tpsγsd=gcd(a,b)=\prod_{s=1}^{t} p_{s}^{\gamma{s}}, whereas psγsp_{s}^{\gamma{s}} are the common prime powers of aa and bb. As a consequence, the two integers ad\frac{a}{d} and bd\frac{b}{d} have no common prime powers, and hence gcd(ad,bd)=1gcd( \frac{a}{d} , \frac{b}{d} ) = 1.

# GCD : returns returns GCD of a and b.
# parameters a and b
def GCD(a, b):
if (a == 0):
return b
elif (a == 1):
return 1
else:
return GCD(b%a, a)
# isCoPrime : returns 1 when a and b are coprime to each other,
# otherwise returns 0
# parameters a and b
def isCoPrime(a, b):
if (a > b):
return 1 if GCD(b, a)==1 else 0
else:
return 1 if GCD(a, b)==1 else 0
# Feel free to change value of a and b
a = 18
b = 5
print(a," is ", 'coprime' if isCoPrime(a, b)==1 else 'not coprime' , " to ", b);