Question 1C - GCD & Ideals

Question 1

Definition : Greatest common divisor

Answer 1

Let m, n ∈ Z(bar). The greatest common
divisor of m and n, denoted gcd(m, n), is the largest positive integer d such that
d | m and d | n.
If there is no largest such integer then m = n = 0 and we define gcd(0, 0) = 0.

We say m and n are coprime if gcd(m, n) = 1.

Question 2

Proposition : GCD (pf not on exam)

Answer 2

Let m, n ∈ Z(bar).
Then d = gcd(m, n) is the unique integer d ≥ 0 such that mZ(bar) + nZ(bar) = dZ(bar).

Question 3

Corollary : Be´zout’s Identity (LEARN)

Answer 3

Let m, n ∈ Z(bar).
Then there exist λ, µ ∈ Z(bar) such
that λm + µn = d,
where d = gcd(m, n).

Question 4

Corollary : Minimum set (GDC) (LEARN)

Answer 4

Let m, n ∈ Z(bar). The greatest common divisor of m and n can be
written as a minimum of a set of integers as follows
gcd(m, n) = min{λm + µn | λ, µ ≥ 0, λm + µn > 0}.

Question 5

Proposition : invertible mod n iff gcd = 1 (PF ON EXAM)

Answer 5

Let x, n ∈ Z(bar), n > 0. Then x is invertible mod n iff gcd(x, n) = 1.

PROOF:

Suppose [x] is a unit.
Then there is some y ∈ Z(bar) such that [x]·[y] = [1], that is,
xy ≡ 1 (mod n), that is, 1 = xy + qn for some q ∈ Z(bar), and this implies gcd(x, n) = 1.

Conversely, if gcd(x, n) = 1 then by Be´zout’s identity we have
λx + µn = 1
for some λ, µ ∈ Z(bar).
It follows that [λ]·[x] = [1],
so [x] is invertible with inverse [λ].

Question 6

Definition : Ideal

Answer 6

Let R be a ring.

A left-ideal is a subset I⊆R such that (I,+) is a subgroup of (R,+) and
r∈R and x∈I= ⇒ rx∈I.
write I ◁_l R.

A right ideal is a subset I ⊆R such that (I,+) is a subgroup of (R,+) and
r∈R and x∈I= ⇒ xr∈I.
write I ◁_r R.

An ideal is a subset I ⊆R such that (I,+) is a subgroup of (R,+) and
r∈R and x∈I= ⇒ rx∈I and xr∈I.
write I ◁R.
We say I is a proper ideal if I <> R.

In a commutative ring we only talk about ideals.

Ideals are not subrings!!!
If I⊆R is both a subring and an ideal then I = R.

Question 7

Equivalence Lemma (pf not on exam)

Answer 7

Let R be a ring and I ◁R. Then the following are equivalent:
(1) I= R,
(2) I contains 1,
(3) I contains a unit.

Question 8

Addition of ideals Lemma (pf not on exam)

Answer 8

Let I,J be left ideals of a ring R. Then I+ J is a left ideal of R.