§1 Preliminaries (Proofs)

Proposition 1.1:

• For a,b ∈ A, if [a]∩[b] ≠ 0, then [a] = [b]. In other words, either [a]=[b], or [a]∩[b]=0.
• Proof:
• Let c ∈ [a]∩[b]. Let us prove [a]⊆[b].
• Let d∈[a]. By definition of [a] we have d~a. We also have a~c. Then by transitivity we have d~c.
• As c∈[b] we have c~b. By transitivity again we have d~b and the d∈[b].
• Thus [a]⊆[b].
• We show similarly that [b]⊆[a], which implies [a]=[b].
• ∎

Theorem 1.1:Long division, Euclidean divisors

• m∈Z, m>0 & n∈Z. Then n=q∙m+r for some q,r∈Z with 0≤r<m. Moreover, q & r are unique.
• Proof:
• Note first that n=mq+r iff -n=m(-q)-r iff -n=m(-q-1)-(m-r). Furthermore if r>0 then 0<(m-r)<m. Therefore we can suppose without loss of generality that n i positive, as the theorem for n negative can be deduced from the theorem for n positive.
• Suppose n≥0.
• Write n, n-m, n-2m, ... , n-q∙m until n-q∙m≥0 & n-(q+1)m<0.
• Set r=n-q∙m.
• Want to show 0≤r<m.
• By assumption, r=n-q∙m≥0
• Suppose r≥m ⟹ n-qm ≥ m
• ⟹n-qm-m ≥ 0
• ⟹n-(q+1)m ≥ 0. Contradiction.
• ∴ 0≤r<m

Corollary of Theorem 1.1:

• If p,q∈Z, g.c.d(p,q)=1, then there are a,b∈Z such that ap+bq=1.
• Proof:
• Set S={Ap + Bq : A,B∈Z, Ap+Bq > 0}
• Suppose ap+bq is the smallest in S. Suppose ap+bq>1.
• Because g.c.d(p,q)=1, ap+bq cannot divide both p and q. W.L.O.G, assume ap+bq∤P.
• (see image), 0<R<ap+bq
• R = P - Q(ap+bq)
• = (1-aQ)p - Qbq ∈ S
• But, 0<R<ap+bq. Contradiction (ap+bq is meant to be the smallest in S).
• Thus, ap+bq=1.
• ∎
• 

Lemma 1.1: Euclid's lemma

• If p is a prime, and p|ab (for a,b∈Z), then p|a or p|b.
• Proof:
• Suppose there are integers a,b∈N*� such that p divides ab but p divides neither a nor b. For a and p fixed, W.L.O.G we can consider that bis the smallest such that p|ab but p∤b. In particular we can suppose b < p. Indeed, if b > p consider (using Euclidean division) some b'� < p such that b ≡ b'� mod p. We then have ab = a(pq + b'�) = apq + ab'� for some integer q. Then if p divides ab it must divide ab'�.
• So suppose 1 < b < p. By Euclidean division we have integers b'� < b and q such that p = bq + b'�. Also we must have b'� > 0 as otherwise p would not be prime. We then have ap = abq + ab'� and then ab'� = ap − abq. As p divides ab then also p divides ap−abq and thus ab'�. But we have 0 < b'� < b < p and then p does not divide b'� which contradicts the minimality of b. Then p must divide a or b.
• ∎