Please enable JavaScript.
Coggle requires JavaScript to display documents.
NUMBER THEORY - Coggle Diagram
NUMBER THEORY
CONGRUENCES
-
-
-
Three Properties
-
-
Transitivity If \( a \equiv b (mod\ n) \) and \(b \equiv c (mod\ n) \)
then \( a \equiv c (mod\ n) \)
Residues
-
least residue of a modulo n is the smallest
number greater than or equal to zero
in the residue class of a modulo 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) \)
MULTIPLICATIVE
INVERSES
-
-
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
-
-
find mult inv
-
\( n \ge 14 \)
Use Euclid and back sub
Find \( av + nw = 1\)
The v is mult inv of a mod n
\( av = 1 - nw \)
EUCLID ALGO
Find highest common factor
of positive integers a an b,
where a > b
-
-
-
FACTORS AND MULTIPLES
-
a, n, k are int such that
a = kn
then
a is multiple of n
n is a factor or divisor of a
-
-
LINEAR CONGRUENCE
Of the form \(ax \equiv b\ (mod\ n) \)
where a, b and n are known
x is not known
-
-
-
-
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 \)