Exercises on integers

Exercise 1. Prove that the relation

define on ℕ x ℕ is an equivalence relation.

Exercise 2. Prove that addition and multiplication defined on ℤ are well-defined.

Exercise 3. Prove that in ℤ the following cancellation laws hold

Exercise 4. Let p a prime element of ℤ. Prove that if p divides a product of n factors then p divides at least one factor.

Exercise 5. Let (x̅,y̅) an integer solution of the equation ax + by = c, a, b, c ∈ ℤ. Prove that all solutions of this equation can be obtained by adding to a the particular solution (x̅,y̅) an integer solution (x₀, y₀) of the homogenous equation ax + by = 0.

Exercise 6. By using the fundamental theorem of arithmetic prove that if p is a prime number in ℤ then, √p is irrational.

Solution

1. 1. If (n,m) ∈ ℕ x ℕ (n, m) ρ (n, m) because n + m = m + n, (+ is commutative). This says that ~ is reflexive.

   2. (n, m) ρ (n', m') ⇒ (n', m') ρ (n, m). Indeed because (n,m) ρ (n',m')   ⇐⇒   n + m' = m + n' ⇐⇒ n' + m = m' + n ⇐⇒ (n',m') ρ (n, m). This says that ~ is symmetric.

   3. (n,m) ρ (p,q) ⇐⇒ n + q = m + p, (p,q) ρ (r,s) ⇐⇒ p + s = q + r. Summing up both equations we have n + q + p + s = m + p + q + r and by semplifying n + s = m + r i.e. (n,m) ρ (r,s). This says that ~ is transitive.

2. Let S be a set, ~ an equivalence relation over S, · : S × S ⟶ S, then we say · is well defined on S/~ if for x~x', y~y' we have x·y ~ x'·y'.

   Assume (a, b) ~ (a', b') and (c,d) ~ (c', d'), we must show that (a, b) + (c,d) ~ (a', b') + (c', d').

   (a, b) + (c,d) = (a + c, b + d).

   (a', b') + (c', d') = (a' + c', b' + d')

   (a + c, b + d) ~ (a' + c', b' + d') ⇐⇒ a + c + b' + d' = b + d + a' + c'

   which is true since

   (a,b) ~ (a', b') ⇐⇒ a + b' = b + a'   and   (c,d) ~ (c', d') ⇐⇒ c + d' = d + c'

   Let's show now that (a, b)(c, d) ~ (a', b')(c', d'); We start by showing that (a, b)·(c,d) ~ (a, b)·(c', d'). By expanding ·, it is equivalent to show that (ac + bd, ad + bc) ~ (ac + bd, ad + bc), which by the definition of ~ is the same as showing that ac + bd + ad' + bc = ad + bc + ac' + bd'.

Multiplying c + d' = d + c' by a yields

ac + ad' = ad + ac'.

Multiplying d + c' = c + d' by b yields

bd + bc' = bc + bd'

Summing up the two equations to get the original one.

We show now the product is commutative

(a, b)(c, d) = (ac + bd, cb + ad)

and (c, d)(a, b) = (ca + db, ad + cb)

Using commutativity on ℕ of + and · we have

(ac + bd, cb + ad) = (ca + db, ad + cb)

By commutativity of the product, we have also (a, b)·(c, d) ~ (a, b)·(c', d') = (c', d')·(a, b) ~ (c', d')·(a', b') = (a', b')·(c', d').

3. Since ℤ is an integral domain it has no zero divisor ac − bc = c(a − b) = 0 since c ≠ = 0 it follows that (a − b) = 0 ⇒ a = b.

4. We use induction on n. If n = 2, we have the definition of prime element. We suppose true that if p divides a product of n − 1 factors then p divides at least one factor. Considering now a product of n factors, if p|a₁a₂...a_n: then p | a₁(a₁a₂...a_n). Hence for the inductive hyphotesis p divides one of the two factors: p | a₁ or p|a₂...a_n.

5. Let (x₀, y₀) a solution of ax + by = 0. Then (x̅ + x₀,y̅ + y₀) is a solution of the complete equation, indeed we have

   a(x̅ + x₀),y̅ + y₀) = ax̅ + by̅ + ax₀ + by₀ = c

   Viceversa let (x̅ + y̅) and (x',y') two solutions of the complete equation. Then

   a(x̅ − x') + b(y̅ − y₀) = ax̅ + by̅ − ax' − bx' = c − c = 0

   hence (x',y') differs from (x̅ + y̅) by a solution of the homogenous equation. Let's express all solutions of the complete equation. Let d' = gcd(a,b) and let a',b',c' such that a = da', b = db', c = dc'. Then the complete equation can be written as a'x + b'y = c'. The solutions (x₀, y₀) of the homogenous equation are x₀ = −b'k, y₀ = a'k, k ∈ ℤ (se allso Example 2.3.2).
   Thus all solutions (x',y') of the complete equation x' = x̅ −(b/d)k, y' = y̅ + (a/d)t with k varying in ℤ.

6. If √p = r/s with r and s integers we would have ps² = r². In the left hand side of the equation p appears an odd number of time whilst in the right end side either it does not appear or it appears an event number of times. This contradicts the unicity of the factorisation in ℤ.