Chapter 2 Definitions

Question 1

Congruent

Answer 1

m in Z^+.

For a,b in Z, we say a is congruent to b modulo m and write:

a ≡ b (mod m) ⇔ a-b is a multiple of m.

m is called the modulus.

[a ≡ b (mod m) is equvalent to saying a+mZ and b+mZ of mZ are equal]

Question 2

1. Least non-negative residues mudulo m
2. Least residues modulo m

Answer 2

1. The system of least non-negative residues modulo m is:
   { 0, 1, 2, …. , m-1 }
2. The system of least residues modulo m is:
   m odd: { 0, ±1, ±2, … , ±(m-1)/2 }
   m even: { 0, ±1, ±2, … , ±(m-1)/2, m/2 }

Question 3

A residue system modulo m.

Answer 3

Any set of m integers representing all m residue classes mod m is called a residue system modulo m.

Question 4

Z/mZ

Answer 4

Z/mZ is a ring of integers modulo m.

Question 5

U_m

Answer 5

Group of units of Z/mZ is U_m.

a ϵ U_m​ means a is invertible mod m .

Question 6

A unit in Z/mZ

Answer 6

A unit, u, in Z/mZ is satisfies gcd(u,m) = 1.

Question 7

The order of U_m

Answer 7

The order of U_m is φ(m).

φ:|N→|N is called the Euler phi function.

φ(m) = | { a | 0 ≤ a ≤ m-1 and gcd(a, m) = 1} |

Question 8

A reduced residue system modulo m

Answer 8

A reduced residue system modulo m is a set of φ(m) integers covering the residue classes in U_m.

[Standard one is: { a | 0 ≤ a ≤ m-1 and gcd(a,m)=1 }]

Question 9

1. |F_p
2. |F_p* and properties

Answer 9

For p prime, Z/pZ is denoted |F_p and U_p is denoted |F_p* which has order p-1 and is cyclic.

Question 10

Formula for φ(m)

Answer 10

φ(m) = ∏_(i=1)^k p_i^(e_i-1) (p_i-1) = m ∏_(i=1)^k (1 - 1/p_i )

∑_d|m φ(d) = m

Question 11

Primitive root modulo p

Answer 11

An integer which generates U_p=|F_p* is called a primitive root modulo p.

If U_m is cyclic then a generator of U_m is called a primitive root modulo m.