Number Theory

Question 1

What does a|b mean?

Answer 1

a divides/is a divisor/ a factor/ a multiple of b

Question 2

Division Algo

Answer 2

a = bq+r where q is the quotient and r is the remainder

Question 3

Congruence Modulus

Answer 3

if m divides (a-b)
also known as a ≡ b (mod m)

Question 4

Congruence Modulus Theorem

Answer 4

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)

Question 5

Corollary for the Congruence Modulus Theorem

Answer 5

(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

Question 6

Arithmetic Addition

Answer 6

a ⊕ b = (a + b ) mod m

Question 7

Arithmetic Multiplication

Answer 7

a ⨂ b = (a x b) mod m

Question 8

Commutative property for arithmetic addition and multiplication

Answer 8

a ⊕ b = b ⊕ a
a ⨂ b = b ⨂ a

Question 9

Associative property for arithmetic addition and multiplication

Answer 9

a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c
a ⨂ (b ⨂ c) = ( a ⨂ b) ⨂c

Question 10

Identity property for arithmetic addition and multiplication

Answer 10

a ⊕ 0 = a
a ⨂ 1 = a
a ⨂ 0 = 0

Question 11

The distributive property for arithmetic addition and multiplication

Answer 11

a ⨂ ( b ⊕ c) = ( a ⨂ b) ⊕ (a ⨂ c)

Question 12

Modular Subtraction

Answer 12

a ⊖ b = (a - b) mod m

Question 13

Modular Reciprocal

Answer 13

a^-1 = b

Question 14

Modular Division

Answer 14

a ⨂ b ^ -1

Question 15

Prime Number

Answer 15

has exactly two positive divisors 1 and itself

Question 16

Relatively Prime

Answer 16

if a and b’s only GCD is 1

Question 17

Pairwise Relatively Prime

Answer 17

if gcd(a₁, a₂) = 1 whenever 1 ≤ a sub 1 value ≤ a sub 2 value ≤ n

Question 18

Prime Lemma

Answer 18

a = bq+r then gcd(a,b) = gcd(b,r)

Question 19

Steps for Euclid Algo

Answer 19

1. Divide two numbers and find the remainder
2. Remainder becomes the new second number in GCD
3. Repeat step 1 until the second number is 0
4. The first number when the second is 0 is the GCD of the two OG numbers

Question 20

Steps for extended Euclid Algo

Answer 20

1. Do Euclid
2. 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
3. gcd(a,b) = s sub n a + t sub n b

Question 21

Bea