Division and Greatest common divisor

Author: Zademn

Introduction

Two of the skills a cryptographer must master are:

  1. Knowing his way and being comfortable to work with numbers.

  2. Understanding and manipulating abstract objects.

This chapter of fundamentals proposes to prepare you for understanding the basics of number theory and abstract algebra .We will start with the most basic concepts such as division and build up knowledge until you, future cryptographer, are able to follow and understand the proofs and intricacies of the cryptosystems that make our everyday life secure.

We will provide examples and snippets of code and be sure to play with them. If math is not your strongest suit, we highly suggest to pause and ponder for each concept and take it slow.

For the math-savy people we cover advanced topics in specific chapters on the subjects of number theory and group theory.

So what are we waiting for? Let's jump right in!

Division

Let Z={,1,0,1,2,3}\mathbb{Z} = \{\dots , -1, 0, 1, 2, 3 \dots \}be the set denoting the integers.

Definition - Divisibility

For a,b,Za, b, \in \mathbb{Z} we say that aadivides bbif there is some kZk \in \mathbb{Z}such that ak=ba \cdot k = b

Notation: aba | b

Example

For a=2,b=6a = 2, b = 6 we have 262 | 6 because we can find k=3k = 3such that 6=236 = 2 \cdot 3.

Properties

  • aa, 1a and a0a | a, \ 1 | a \text{ and } a | 0

  • aba | b and ac a | c implies a(bu+cv) u,v,Za | (bu + cv) \ \forall u, v, \in \mathbb{Z}

    • Example: Let b=6,u=5b = 6, u = 5 and c=9,v=2c = 9, v = 2

    • 363 | 6 and 393(65+92)3483 | 9 \Rightarrow 3 | (6 \cdot 5 + 9 \cdot 2) \iff 3 | 48 . We can find k=16k = 16such that 48=31648 = 3 \cdot 16

  • aba | b and bc b | c implies ac a | c

  • if aba|band bab|a then a=±ba = \pm b

Definition - Division with remainder

Let a,bZa, b \in \mathbb{Z}with b1b≥1,

There exists unique q,rZq, r \in \mathbb{Z}such that a=bq+r\boxed{a = bq + r}and 0r<b0 \leq r < b

qq is called the quotient and rr the remainder

Examples:

  • To find q,rq, r python offers us the divmod() function that takes a,ba, bas arguments

q, r = divmod(6, 2)
print(q, r)
# 3 0
q, r = divmod(13, 5)
print(q, r)
# 2 3
# Note that 13 = 2 * 5 + 3
  • If we want to find only the quotient qq we can use the // operator

  • If we want to find the remainder rr we can use the modulo % operator

q = 13 // 5
print(q)
# 2
r = 13 % 5
print(r)
# 3

Exercises:

  1. Now it's your turn! Play with the proprieties of the division in Python and see if they hold.

Greatest common divisor

Definition

Let a,bZa, b \in \mathbb{Z} be 2 integers. The greatest common divisor is the largest integer dZd \in \mathbb{Z}such that dad | aand dbd | b

Notation: gcd(a,b)=d\gcd(a, b) = d

Examples:

# In python we can import math to get the GCD algo
import math
print(math.gcd(18, 12)) # -> 6
# Sage has it already!
print(gcd(18, 12)) # -> 6

Remark:

  • for all other common divisors cc of a,ba, bwe have cdc | d

Things to think about

What can we say about numbersa,b a, b with gcd(a,b)=1\gcd(a, b) = 1? How are their divisors?