CryptoBook
Search…
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
aa
divides
bb
if 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 = 3
such 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 = 16
      such that
      48=31648 = 3 \cdot 16
    aba | b
    and
    bc b | c
    implies
    ac a | c
    if
    aba|b
    and
    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, b
    as arguments
1
q, r = divmod(6, 2)
2
print(q, r)
3
# 3 0
4
5
q, r = divmod(13, 5)
6
print(q, r)
7
# 2 3
8
# Note that 13 = 2 * 5 + 3
Copied!
    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
1
q = 13 // 5
2
print(q)
3
# 2
4
5
r = 13 % 5
6
print(r)
7
# 3
Copied!
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 | a
and
dbd | b
Notation:
gcd(a,b)=d\gcd(a, b) = d
Examples:
1
# In python we can import math to get the GCD algo
2
import math
3
print(math.gcd(18, 12)) # -> 6
4
# Sage has it already!
5
print(gcd(18, 12)) # -> 6
Copied!
Remark:
    for all other common divisors
    cc
    of
    a,ba, b
    we have
    cdc | d

Things to think about

What can we say about numbers
a,b a, b
with
gcd(a,b)=1\gcd(a, b) = 1
? How are their divisors?
Last modified 5mo ago
Export as PDF
Copy link