## Let’s Explore the Integers, and Then Prove Things About Them!

### Multiples and Divisors of Integers

**Definition 2.4:**For n ∈ ℤ, the*set of multiples**of n*is: {n · t: t ∈ ℤ}; usually abbreviated as*n*ℤ. Each element in this set is called a*multiple of n.*

Example: 5ℤ = {….,-15, -10, -5, 0, 5, 10, 15….} Notice negative numbers are included!

**Definition 2.5:**For x,y ∈ ℤ, x ≠ 0, and t being some integer, x · t = y means that “x is a*divisor and a factor*of y”, which is usually written as “x|y”. *Zero is not a divisor of any integer.*Includes negative numbers.*

Example: 10|-30. 10 is a divisor of -30, because 10 x -30 = 30. *10|-30 is **not** a number, though. It’s a statement about the relationship between 10 and -30. It is not a fraction or an equation.

**Definition 2.6:**For*t*∈ ℕ, where t > 1, “t is a prime” means that t is a positive integer that only has divisors of t and 1. If t has more divisors, then t is a*composite number.*

*1 is not a prime or composite number, it’s just a chill no-name.

**Definition 2.7:**For x ∈ ℤ: x is*even*means that there is an integer*t*such that x = 2 · t. x is*odd*when there is an integer y such that x = 2 · y+1.

Exploration 1: Properties of Divisibility: what general statements can we make about divisibility?

- If a|b and a|c, b and c may or may not be divisors of one another.
- If a|c and b|c, a and b may or may not be divisors of one another.
- Prime numbers can be a divisor (x), but not divided (y).
- If a|b and c|d, I don’t think we can make any conclusions of the relationship between the two, other than the fact that b and d must be composite, and that a and c can be composite or prime. For example 2|6 and 5|20. We cannot make any general connection between the two statements that would apply to all divisibility statements, because what they might have in common may not apply to other statements, such as 3|9.

Exploration 2: Odd and Even Numbers: What general results can you state about odd and even numbers?

- odd + odd = even
- odd + even = odd
- even + even = even
- odd – odd = even
- odd – even = odd
- even – odd = odd
- even – even = even
- odd x odd = odd
- odd x even = even
- even x even = even
- odd/odd = odd
- even/even = even
- odd/even = fraction?
- even/odd = fraction?
- odd^rasied to any power = odd
- even^raised to any power = even

### Linear Diophantine Equations

Linear Diophantine Equations look like this:

ax + by = c.

A, b, and c are input into the equation as integers, and only integers can be input for x and y when trying to solve the equation. This whole topic just plays around with inputing different integers into this equation, and seeing when x and y are integers, and when x and y must be something else to solve the equation.

Exploration 3: Linear Diophantine Equations: For what integers a, b and c will the equation ax + by = c have integral solutions for x and y?

- If a,b and c, all equal 1, x and y can equal 0 and 1.
- If a, b share a common factor that is not shared with c, you can’t solve the equation with integers.
- If c is negative, the bigger out of ax and by must be negative, meaning either only x or only a must be negative if ax is bigger, and b or y must only be negative if by is bigger.
- If c is positive, the bigger of ax and by must be positive, meaning that a and x can both be negative or both positive if ax is bigger, and the same for by if by is bigger.

### Basic Facts About Divisors

**Theorem 2.9:**For integers a,b and c, if a|b and b|c, then a|c.

*Proof:*

We are proving that a|c. Since a|b, there is an integer, x, such that: ax = b. Since b|c, there is and integer, y, such that: by = c. We need to show that there is an integer, az = c. Define z = xy. From this, we can assume z is an integer, since it is the product of two integers. Since b = ax, (ax)y = c, or a(xy) = c. This shows that z = xy is a solution in az = c, proving the proof!

**Corollary 2.10:**Any multiple of an even number is even.**Theorem 2.11:**If a ∈ ℤ, than the set aℤ is closed under both addition and subtraction.**Theorem 2.12:**For a,b and c ∈ ℤ, if a and b are even, and c is not even, then the equation ax+by=c has no integral solution for x and y.

### Common Divisors

**Definition 2.8:**For x,y ∈ ℤ, “t is a common divisor of x and y” means: t|x and t|y.**Definition 2.9:**For x,y ∈ ℤ “t is the greatest common divisor of x and y” means that t is a common divisor of x and y, and every common divisor of x and y is less than or equal to t. (Written as: GCD(x,y))**Definition 2.10:**For x,y ∈ ℤ, “x and y are relatively prime” means: GCD(x,y) = 1.**Corollary 2.14:**Suppose a,b,c ∈ ℤ with a and b not both 0, and d = GCD(a,b). If d is not a divisor of c, then the equation ax + by = c has no integer solutions for x and y.

### Odd and Even Integers

**Theorem 2.15:**If u ∈ ℤ, then 2 · u ≠ 1.

**Theorem 2.16:**For x ∈ ℤ, if x is odd, then x is not even. And integer cannot be both odd and even.**Definition 2.11:**For x,y ∈ ℤ, “t is a common multiple of x and y” means that t is both a multiple of x and y.

I’m pretty sure that’s more than anyone ever really wanted to know about even numbers, odd numbers, multiples, and divisors. Now there’s the task of applying all these definitions and theorems to proofs – GYHD Problems, here I come! (But not right now, because I still have FOM Homework, and it’s Sunday. So I’ll think about them eventually.)