Chapter 3

Question 1

a is congruent to b modulo n

Answer 1

Let a,b∈ℤ and n∈ℕ. We write a≡bmodn and say a is congruent to b modulo n if n|(a-b)

Question 2

a≡bmodn also means that => (there exists…)

Answer 2

there exists a k∈ℤ s.t. b=a+kn

Question 3

a≡bmodn also means that => (a and b leave)

Answer 3

a and b leave the same remainder when divided by n

Question 4

Lemma III.1.2 (congruence is an equivalence relation)

Answer 4

Let n∈ℕ and a,b,c∈ℤ

a) a≡amodn (reflexive
(b) if a≡bmodn then b≡amodn (symmetric)
(c) if a≡bmodn and b≡Cmodn then a≡cmodn

Question 5

Lemma III.1.3 (operations on congruences)

Answer 5

Let n∈ℕ and a,b,c,d∈ℤ. Suppose that a≡bmodn and c≡dmodn. Then,

(i) a+c≡b+dmodn
(ii) a-c≡b-dmodn
(iii) ac≡bdmodn

Question 6

complete set of residues

Answer 6

Let n∈ℕ. The a complete set of residues (CSR) modulo n is a subset S⊆ℤ with the property that every Integer is congruent modulo n to exactly one element of S.

Question 7

Lemma II.2.1. complete set of residues modulo n.

Answer 7

Let n∈ℕ. Then {0,1,…,n-1} is a complete set of residues modulo n.

Question 8

How to solve an equation of the form ax≡bmodn

Answer 8

1. write out a table with x, ax and what ax is congruent to modulo n
2. the solutions are given by the xs in the columns where the congruence is equal to b

Question 9

Theorem III.3.1 ax≡bmodn

Answer 9

Let n∈ℕ and a,b∈ℤ and consider the equation ax≡bmodn. Let h=hcf(a,n). Then the following holds
(i) () has solutions <=> h|b
(ii) if x₀ is a solution to () then all the solutions to (*) are of the form
x₀, x₀ + n/h, … ,x₀ + (h-1)n/h

Question 10

How to use the Euclidean algorithm to solve ax≡bmodn

Answer 10

1. use Euclidean algorithm to find hcf(a,n)
2. use extended Euclidean algorithm to find x,y s.t. h = xa +yn
3. multiply through by b/h
4. put into congruence modulo n
5. find other solutions (from theorem III.3.1)

Question 11

Corollary III.3.2 cancelling

Answer 11

Let n∈ℕ and a∈ℤ with a≢0modn. Let x₁,x₂∈ℤ suppose that
ax₁≡ax₂ modn and a and n are coprime. then x₁≡x₂ modn

i.e. you can cancel if a and n are coprime

Question 12

Corollary III.3.3 cancelling when mod prime

Answer 12

Let p be a prime and a,x₁,x₂∈ℤ. Suppose that ax₁≡ax₂modp and that a≢0modp. Then,
x₁≡x₂modp

Question 13

Corollary III.3.4 multiplicative inverse

Answer 13

let p be prime and a∈ℤ with a≢0modp. Then there exists a’∈ℤ such that aa’≡1modp

Question 14

Fermats Little Theorem (FlT)

Answer 14

Suppose that p is prime and that a∈ℤ. Then:

(i) If a≢0modp then aᵖ⁻¹≡1modp
(ii) aᵖ≡amodp

Question 15

How to determine the remainder when aᵇ is divided by p

Answer 15

1. we know that for some c∈ℤ we have aᶜ≡1modp by FlT
2. use the division theorem to divide b by c: b=dc + e
3. aᵇ = aᵈᶜ ⁺ᵉ = (aᶜ)ᵈaᵉ = 1ᵈaᵉ≡modp

Question 16

Eulers Theorem

Answer 16

Suppose that n∈ℕ and a∈ℤ with a and n coprime. then

aᵖʰᶦ⁽ⁿ⁾ ≡ 1 modn

Question 17

f(X) is congruent to g(X)

Answer 17

let f(X) g(X) be polynomials with integer coefficients and let n∈ℕ. We say that f(X) is congruent to g(X) if for each i≥0 the coefficients of xᶦ if f(X) are congruent modulo n to the coefficiant of xᶦ in g(X).

Question 18

in general f(X)≡g(X)modn =>

Answer 18

f(X)≡g(X)modn => for x∈ℤ f(x)≡g(x)modn

Question 19

Lemma II.5.2. root of polynomial

Answer 19

Let n∈ℕ and f(X) be a polynomial with integer coefficients. Let a∈ℤ and suppose that a is a root of f(X)modn (i.e. f(a)≡0modn) Then there exists a polynomial g(X) also with integer coefficiants s.t. f(X)≡(x-a)g(X)modn.

Question 20

degree modulo n of f(X)

Answer 20

Suppose that n∈ℕ and that f(X) is a polynomial with integer coefficients. The degree modulo n of f(X) is the largest d such that the coefficient of Xᵈ is not congruent to 0 modulo n. If all the coefficients are congruent to 0 modulo n then we define the degree to be -∞

Question 21

if a is a root of f(X)-f(a) then…

Answer 21

f(x)-f(a)=(x-a)g(x)

Question 22

Lagranges Theorem

Answer 22

Suppose that p is prime and that f(X) is a polynomial with integer coefficients and degree d≥0. Then the equation f(X)≡0modp has at most d distinct solutions modulo p.

Question 23

Theorem III.5.4. exactly d solutions.

Answer 23

suppose that p is prime and d∈ℕ is such that d|p-1. Then Xᵈ≡1modp has exactly d solutions modulo p.

Question 24

corollary III.5.6. exactly 2 solutions.

Answer 24

Suppose that p is prime and that p≡1mod4 Then

X²≡-1modp has exactly two solutions modulo p

Question 25

Theorem III.5.7. coprime exactly n solutions.

Answer 25

Suppose that p is prime and d∈ℕ.

(i) if hcf(d,p-1)=1 then Xᵈ≡1modp has exactly one solution modulo p
(ii) Xᵈ≡1modp has exactly h(d,p-1) solutions modulo p

Question 26

order

Answer 26

Let p be prime and a∈ℤ with a≢0modp then the order of a mod p is the smallest natural number d∈ℕ s.t. aᵈ≡1modp

Question 27

we know that the order is always at least 1 because..

Answer 27

fermats little theorem aᵖ⁻¹≡1modp

Question 28

Theorem

Answer 28

Suppose p is prime. Then there is an integer ω s.t. any integer z≢0modp is congruent to a power of ω modulo p. In other words, the multiplicative group of the integers modulo p is generated by ω

Question 29

a≡ a +- n mode n

Answer 29

true

Question 30

lemma III.6.1. distinct numbers modulo p.

Answer 30

Let p be prime a∈ℤ with a≢0modp and let d be the order of a modulo p. Then the integers a⁰,a¹,a²,..,aᵈ⁻¹ are all distinct modulo p

Question 31

Lemma III.6.2

Answer 31

Let p be prime and a∈ℤ with a≢0modp. Let d be the order of a modp. Let k∈ℕ. Then, aᵏ≡1modp <=> d|k

Question 32

corollary III.6.3

Answer 32

Let p be prime a∈ℤ with a≢0modp and let d be the order of a modulo p. Then d|p-1

Question 33

Theorem III.6.4

Answer 33

Suppose that p is a prime and that d|p-1 with d>0. Then there are precisely ϕ(d) integers that have order d modulo p.

Question 34

primitive root modulo p

Answer 34

suppose that p is prime. A primitive root modulo p is an integer ω with order p-1 modulo p.

Question 35

corollary III.6.5

Answer 35

suppose that p is prime. Then there are precisely ϕ(p-1) primitive roots modulo p

Question 36

if ω is a primitive root modulo p then a complete set of residues is given by

Answer 36

0, ω⁰, ω¹, ω², ωᵖ⁻²

Question 37

true or false primitive roots always exist

Answer 37

true