Number Theory Flashcards
(25 cards)
What does a|b mean?
a divides/is a divisor/ a factor/ a multiple of b
Division Algo
a = bq+r where q is the quotient and r is the remainder
Congruence Modulus
if m divides (a-b)
also known as a ≡ b (mod m)
Congruence Modulus Theorem
If a ≡ b (mod m) and c ≡ d (mod m)
then:
a + c ≡ b + d (mod m)
a -c ≡ b - d (mod m)
ac ≡ bd (mod m)
a^n ≡ b^n (mod m)
Corollary for the Congruence Modulus Theorem
(a + b) mod m ≡ ((a mod m) + (b mod m)) mod m
(a x b) mod m ≡ ((a mod m) x(b mod m)) mod m
Arithmetic Addition
a ⊕ b = (a + b ) mod m
Arithmetic Multiplication
a ⨂ b = (a x b) mod m
Commutative property for arithmetic addition and multiplication
a ⊕ b = b ⊕ a
a ⨂ b = b ⨂ a
Associative property for arithmetic addition and multiplication
a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c
a ⨂ (b ⨂ c) = ( a ⨂ b) ⨂c
Identity property for arithmetic addition and multiplication
a ⊕ 0 = a
a ⨂ 1 = a
a ⨂ 0 = 0
The distributive property for arithmetic addition and multiplication
a ⨂ ( b ⊕ c) = ( a ⨂ b) ⊕ (a ⨂ c)
Modular Subtraction
a ⊖ b = (a - b) mod m
Modular Reciprocal
a^-1 = b
Modular Division
a ⨂ b ^ -1
Prime Number
has exactly two positive divisors 1 and itself
Relatively Prime
if a and b’s only GCD is 1
Pairwise Relatively Prime
if gcd(a₁, a₂) = 1 whenever 1 ≤ a sub 1 value ≤ a sub 2 value ≤ n
Prime Lemma
a = bq+r then gcd(a,b) = gcd(b,r)
Steps for Euclid Algo
- Divide two numbers and find the remainder
- Remainder becomes the new second number in GCD
- Repeat step 1 until the second number is 0
- The first number when the second is 0 is the GCD of the two OG numbers
Steps for extended Euclid Algo
- Do Euclid
- Apply the following recursive algo
Base Case:
s sub 0 = 1
s sub 1 = 0
t sub 0 = 0
t sub 1 = 1
Recursive Case:
s sub j = s sub j-2 - q sub j-1 x s sub j-1
t sub j - t sub j-2 - q sub j-1 x t sub j-1
j and q sub j are the quotient in the divisors from Euclid’s - gcd(a,b) = s sub n a + t sub n b
Bea
