4 & 5 - Number Theory

Question 1

Modulo operation: 2 components

Answer 1

Quotient and remainder

Question 2

a ≡ c (mod b) means what?

Answer 2

a is congruent to c mod b

a mod b = c mod b

a and c have the same remainder divided by b; a-c is a multiple of b

Question 3

Divisibility

Answer 3

c such that a = bc then a is a multple of b and b is a divisor of a

Question 4

Prime numbers

Answer 4

No divisors other than 1 and itself

Question 5

Unique Factorisation

Answer 5

Any integer can be written as a product of primes in a unique way

Question 6

Greatest Common Divisor

Answer 6

Largest integer a factor of both numbers.

AKA Highest Common Factor
Euclid’s Algorithm is faster!

Question 7

If two numbers have no common factors other than one they are…

Answer 7

relatively prime.

Eg 9 and 20 are not prime themselves but relatively prime.

Question 8

Modular arithmetic WITH division

Answer 8

6/3 = 2 BUT 1/3 we cannot have 0.3333

Think of 1/3 being the num which when * by 3, gives 1.

so 3*7 = 21 then mod 20 is 1

Question 9

Multiplicative inverse of a number in a set (give an example for 3 in set Z20)

Answer 9

for example, 7 is the multiplicative inverse of 3 in Z20

(3*7 = 21 so mod 20 = 1)
7=3^-1 etc

Question 10

Multiplicative inverse of 2 in z20

Answer 10

This cannot exist.

Dividing an even number by an even number is always even

Question 11

Computing the inverse (not by trial and error)

Answer 11

for example 3

3 * d mod 20 =1
3 * d = 20 * c +1
20 * -c + 3 * d = 1

Use extended euclid gcd(a,b), u,v
20 = 20 * 1 + 3 * 0
3 = 20 * 0 + 3 * 1 (quotient 20/3 =6)
2 = 20 * 1 + 3 * -6 (qutoient 3/2 = 1)
1 = 20 * -1 + 3 * 7

d = 7 is the answer (20*-1 is irrelevant)

Question 12

When there is an inverse of a mod b, the gcd(a,b) is

Answer 12

1

Question 13

What if you compute a negative inverse? (Ie u or v is -3 and you need to use it in mod 20)

Answer 13

For example, -3 in mod 20 would be 17.F