- if n is even, then 3n
^{2}+ 5 is odd.

n is even n = 2k

direct:

if n^{2} + 8 is even, then n is even.
n^{2} is even if n is odd, then n^{2} + 8 is odd
n^{2} = 2k n is odd
. n = 2k + 1
. .
. .
n = 2(___) contrapositive

If A is an underlined subset of B, then A (upside down U) is an underlined subset of B (upside down U) C Assume A underlined subset B. direct

New Topic: 15 = 3 * 5

3 is a factor if 15 3 is a divisor of 15 15 is a multiple of 3 15 is divisible by 3

**Definition:** For integers a and b with b != 0, we say
that b divides a if a = bc for some integer c. We write b|a

3 divides 15 because 15 = 3 * 5 3 15 5 15 2 / 15 (char needs to be replaced with a bar with a slash through it)

All of these statements mean the same thing:

b is a divisor of a

b is a factor of a

a is a multiple of b

a is divisiable by b

-3 divides 15 since 15 = (-3)(-5) 4|0 0 = 4 * 0 7|0 12|0 -42|0

not allowed: 0|0 because: 0 = 0 * x where x is not unique.

Example: Find all positive divisors of 12. 1, 2, 3, 4, 6, 12

1 * 12 = 12 2 * 6 = 12 3 * 4 = 12

**Definition of a prime**

- A prime is any
**non-zero****positive****integer**that is**only**divisible by 1 and itself. - A integer is prime if its only positive divisors are 1 and itself.
**An integer p is prime if it has exactly two different positive divisors.**- An integer n > 1 is prime if and only if for all positive integers r and s, if n = rs, then r = 1 or s = 1.

**Primes**
2, 3, 5, 7, 11, 13, 17…

**Definition of a composit**

- An integer n > 1 is composit if it is not prime.
- An integer n is composit if there exist integers a and b with 1 < a < n and 1 < b < n such that n = ab.
- There exit positive integers r and s such that n = rs and r != 1 and s != 1.

Is 5377 prime? 2 /| 5377 3 /| 3577 5 + 3 + 7 + 7 = 22 3 /| 22 5 /| 5377 7 /| 5377 7 root(5377) root(5377) is roughly equal to 73

```
boolean isPrime(int n) {
if (n <= 1) {
// Fail fast if n is zero or negative
return false;
}
for (int d = 2; d <= (int)Math.sqrt(n); d++) {
if (n % d == 0) {
return false;
}
}
return true;
}
```

**Result:** For all n > 1, if n is **not** divisible by any positive integer
that is greater than 1 and less than or equal to sqrt(n), then n is prime.

**Proof:** (by contrapositive)
Let n > 1 be an integer. Assume n is composite. Then there exist
integers r and s with 1 < r < n and 1 < s < n such that n = rs.
Furthermore it is imposible for both r > sqrt(n) and s > sqrt(n) for
otherwise n = rs > sqrt(n) * sqrt(n) = n. So either 1 < r <= sqrt(n) or
1 < s <= sqrt(n)> Thus n **is** divisible by a positive integer that is
greater than 1 and less than of equal to sqrt(n).

**The Sieve of Eratosthenes**

**History:**