Class 2

Continuation of problem that we left unsolved. Pg 13, problem 9. Show that a perfect square is never of the form 3k+2, for any k.

Use indirect proof, i.e. proof by contradiction:

Assume that there does exist a k and n in Z such that 3k+2=n

Focus on n. when dividing by 3, the remainder can be 0, 1 or 2.

Divide it into 3 cases:

Case 1: n=3m

Case 2: n=3m+1

Case 3: n=3m+2

Case 1: n=3m

3k+2=3m2

2=3(3m2-k)

Implying that 3 divides 2, which is a contradiction.

Case 2: n=3m+1

3k+2=(3m+1)2

1=3(3m2+2m-k)

Implying that 3 divides 1, which is a contradiction.

Case 3: similarly...

Therefore, the assumption is false.

Hence, there are no integers k and n such that 3k+2=n2

See #13 on page 14.

Suppose a and b are real numbers, give a formula for the number of integers in the open interval (a,b).

Take an example (-3.5,4.5)

If neither a or b is integer (as in our example),

N=floor(b)-ceiling(a)+1

Also, N=floor(b)-floor(a) works if both are non-integer.

But this doesn't work if a or b is an integer.

Prime Numbers

Methods for determining if a number is prime.

Algorithm 2.2.5 Sieve of Eratosthenes. Input is a list of primes less than or equal to the square root of N.

If there is a number, n, and you want to determine if it's prime, you try dividing it by all the primes... until you get to square root of N.

The sieve of Eratosthenes basically eliminates all the multiples of the primes less than the square root of N.

Algorithm 2.2.6 to determine if N is prime, when N is less than 1012,...

Theorem 2.2.2: There is no largest prime number. Euclid proved it. Proof by contradiction. Construct a number that is 1 larger than the product of the largest two primes.

Definition 2.2.7: Pi(x) = the number of prime numbers less than or equal to x. Goes to infinity as x goes to infinity.

Intervals between prime numbers are unpredictable.

See table of the discover of prime numbers.

Mersenne primes: those of the form 2p-1, where p is prime

Mersenne conjectured that these numbers are prime when p=2,3,5,7,13

Pi(x)

Pi(x), there are some approximating formulas for Pi(x) for large x. See page 22.

Pi(x) ~ x/log(x)

Exercise 10

f(x)=a_nxn+...+a1x+a0

Show that if a0 not equal 1, then f(x) is composite for some x.

Answer: Just let x=a0.

a0 becomes a common factor that can be factored out.

For part 2 of this problem, see the hint in the back of the book.

Exercise 7

Show that there are infinitely many primes in the sequence 3n+2: 0, 5, 11, 13, 17,...

Proof by contradiction. Assume there is a largest prime number, P, that can be expressed as 3n+2.

Let p1, p2, ... , pk be the list of all the primes greater than 2 up to P

Let N=3(p1p2p3...pk)+2

1) N is greater than P

2) N is of the form 3n+2

3) N is prime. How do we know? Suppose not.