S1, C5-6: Modular Arithmetic

Question 1

Positive integers written as a product of prime numbers

Answer 1

Every positive integer can be written as a product of prime numbers in exactly one way.

Question 2

How many prime numbers are there? (Euclid’s Theorem)

Answer 2

Infinitely many

Question 3

Coprime

Answer 3

Two integers, a and b, are said to be coprime or relatively prime if gcd(a, b)=1.

Question 4

Congruence

Answer 4

We say that a is congruent to b modulo m if

m|(a-b)

Question 5

Let a and b be integers. There is an integer b such that ab is congruent to 1 mod m iff…

Answer 5

gcd(a, m)= 1

Question 6

Modular inverse

Answer 6

When there is a number b such that ab is congruent to 1 (mod m), we call it the inverse of a mod m. And then a is invertible.

Question 7

Chinese Remainder Theorem

Answer 7

Let m1 and m2 be coprime, and let a1 and a2 be any integers. The simultaneous congruences
x (congruent to) a1 (mod m1)
x (congruent to) a2 (mod m2)
have a solution modulo m1m2.

Question 8

When can you find a +ve n s.t. a^n is congruent to 1 mod m?

Answer 8

When a and m are coprime.

Question 9

Fermat’s Little Theorem

Answer 9

Let p be prime, and let a be an integer coprime to p. Then

a^(p-1) is congruent to 1 mod p.

Question 10

Fermat-Euler Theorem. Let a and n be integers with

gcd(a, n) = 1. Then a^(ϕ(n)) is congruent to

Answer 10

a^(ϕ(n)) is congruent to 1 mod n.

Question 11

Euler’s function / Totient function: ϕ(n)

Answer 11

ϕ: N -> N is defined by taking ϕ(n) to be the number of integers between 1 and n (inclusive) which are coprime to n.

Question 12

Wilson’s Theorem. We have (n-1)! congruent to -1 (mod n) iff

Answer 12

n is prime