NUMBER THEORY

FACTORS AND MULTIPLES

Integer a divisible by non-zero int n
if third int k such
a = kn

a, n, k are int such that
a = kn
then
a is multiple of n
n is a factor or divisor of a

HCF of two int
is greatest positive int n
that is a factor of both
a and b

DIVISION THEOREM

Given int a and postive int n
there are q and r such
$q = qn + r$
and
$0 \le r < n$

quotient of divisor of a by n is integer q

remainder of division is integer r

EUCLID ALGO

Find highest common factor
of positive integers a an b,
where a > b

Apply division theorem repeatedly

stop when remainder is 0

HCF is remainder is second to last

BEZOUT'S IDENTITY

a and b are integers,
not both zero, let d be HCF
The there are ints v and w
$av + bw = d $

CONGRUENCES

Two ints a and b are congruent modulo n
if they each have the same remainder
on division by n

$ a \equiv b (mod\ n) $

modular arithmetic uses congruences

Three Properties

Reflexivity $ a \equiv a (mod n) $

Symmetry if $a \equiv b (mod\ n) $ then $ b \equiv a (mod\ n) $

Transitivity If $ a \equiv b (mod\ n) $ and $b \equiv c (mod\ n) $
then $ a \equiv c (mod\ n) $

Residues

Residue class of a modulo n is
set of all integers congruent to a modulo n

least residue of a modulo n is the smallest
number greater than or equal to zero
in the residue class of a modulo n

combining

$ a \equiv b (mod\ n) $
$ c \equiv d (mod\ n) $

$ a + c \equiv b + d (mod\ n) $

$ ac \equiv bd (mod\ n) $

$a - c \equiv b -d (mod\ n) $

$ a^n \equiv b^n (mod\ n) $

Fermmat's little theorem

Let p be a prime number
Let a be a integer that is not a multiple of p
$ a^{p-q} \equiv 1\ (mod\ p) $

DIV TESTS

Sum div by 3

Sum div by 9

MULTIPLICATIVE
INVERSES

Mult inv of a modulo n
is int v
$ av \equiv 1\ (mod\ n) $

Two integers coprime
if HCF is 1

Int a has a multiplicative inverse mod n
if a and n are coprime,
else no multiplicative inverse

If a has multiplicative inv
mod n, then every number
congruent to mult inv modulo n
is also a mult inv of a mod n

If $a \equiv b (mod\ n) $
then every mult inverse of
a modulo n is
also a mult inverse of b mod n

Check

Find HCF

If a and n not coprime then no inv

find mult inv

$ n \le 13 $
Try range 1..n-1

$ n \ge 14 $
Use Euclid and back sub
Find $ av + nw = 1$
The v is mult inv of a mod n
$ av = 1 - nw $

LINEAR CONGRUENCE

Of the form $ax \equiv b\ (mod\ n) $
where a, b and n are known
x is not known

solving

If c is solution
every number cong mod n
is also solution

Solution is value of x that
satisfies congruence

Form $x \equiv c\ (mod\ n) $

solution
$ ax \equiv b\ (mod\ n)$

Let d be the highest
common factor of a and n

d = 1
$ x \equiv vb\ (mod n) $
where v is any mut inv of a mod n

If b not div by d
no solutions

If b div d
$ \frac{a}{d} x \equiv \frac{b}{d}(mod\ \frac{n}{d}) $

CIPHERS

Affine cipher

Rule E for enciphering int 0..25

$E(x) = ax + b\ (mod\ 26)$
a and b are int
a and 26 are coprime

Deciphering rule

$ D(x) \equiv v(y-b)\ (mod\ 26)$
where v is any multiplicative inverse of a mod 26