Definitions

1. if n is even, then 3n² + 5 is odd.

n is even n = 2k

direct:

if n² + 8 is even, then n is even. n² is even if n is odd, then n² + 8 is odd n² = 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

1. A prime is any non-zero positive integer that is only divisible by 1 and itself.
2. A integer is prime if its only positive divisors are 1 and itself.
3. An integer p is prime if it has exactly two different positive divisors.
4. 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

1. An integer n > 1 is composit if it is not prime.
2. An integer n is composit if there exist integers a and b with 1 < a < n and 1 < b < n such that n = ab.
3. 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: