Number Theory

Question 1

How can you simplify modulo arithmetic with addition?

e.g. 44 mod 7

Answer 1

Question 2

What is -1 mod 7?

-14 mod 8?

Answer 2

6

2

(Negative modulos work like a clock going in reverse.)

Tip: If you have a negative number that you are performing a mod on (e.g. -1 mod 7), simply add what you are modding it with (7) to the negative number, and you get your answer (6).

Question 3

How can you simplify modulo arithmetic with multiplication?

e.g. 55 mod 7

Answer 3

Question 4

Define a prime number.

Answer 4

(Non-prime numbers are called composite numbers.)

1 is not a prime number.

Question 5

Define relative prime (or coprime) numbers.

Answer 5

e.g. 4 and 9 are coprime.

Question 6

Define what a least common multiplier is.

Answer 6

lcm(a, b) = a • b / gcd(a, b)

(gcd = greatest common divisor)

e.g. The LCM of 4 and 6 is 12.

Question 7

What does “a is congruent to r in the modulo b system” mean?

Answer 7

a mod b = r

Question 8

What does it mean if a is congruent to c mod b?

Answer 8

a mod b = c mod b

Question 9

Define the greatest common divisor.

Answer 9

The GCD is the largest possible c, such that c divides both a and b.

e.g. The GCD of 8 and 12 is 4.

Answer 10

e.g. 1200 = 2⁴ x 3¹ x 5² = 2 x 2 x 2 x 2 x 3 x 5

This theorem is stating two things: first, that 1200 can be represented as a product of primes, and second, no matter how this is done, there will always be four 2s, one 3, two 5s, and no other primes in the product.