Class 7

Only project #1 from last week's quiz will be graded.

Review of homework:

Section 2.3 #17

Section 2.4 2 8 (was also assigned)

Section 2.5 10(b), 12

2.3 #17:

Show that if n has t divisors, then the product of all the positive divisors of n is n^t/2.

Solve by induction.

First consider the case where n has only one prime factor. And prove that the product of the divisors is n^t/2.

Then assume that the formula is true where n has k prime factors. Show that it is true when n has k+1 prime factors.

Section 2.4 #2:

Describe the algorithm to do trial division by 2, 3 and the numbers in the sequences 6k-1 and 6k+1, k=1,2,...

2, 3, 5, 7, 11, 13, 17, 19, ...

Section 2.4 #8:

Determine the possible remainders of a perfect square when it is divided by 16.

n = 16q + r with r between 0 and 15

n² = 16²q² + 32 qr + r²

The first two terms are evenly divisible by 16. So we only need to find the possible remainders or r² mod 16, where r is between 0 and 15.

0² mod 16 = 0

1² mod 16 = 1

2² mod 16 = 2

3² mod 16 = 3

4² mod 16 = 0

and at this point, the pattern clearly repeats.

So r² can be 0, 1, 4 or 9

Section 2.5, #10(b)

Prove the following identity:

[a, (b,c)] = ([a,b], [a,c])

See proposition 2.5.10 on pg 40.

You end up needing to prove that:

max(a,min(b,c)) = min(max(a,b),max(a,c))

For any three a, b, and c.

Consider all six cases for the ordering of a, b and c.

a ≤ b ≤ c

a ≤ c ≤ b

b ≤ a ≤ c

b ≤ c ≤ a

c ≤ a ≤ b

c ≤ b ≤ a

Section 2.5 #12

Prove that 6n-1, 6n+1, 6n+2, 6n+3 and 6n+5 are pairwise relatively prime.

Use the Euclidean algorithm:

6n+1 = 1(6n-1)+2

6n-1 = (3n-1)2 +1

2 = 2x1 + 0

Linear Diophantine Equations

Find the integer solutions for x and y

ax+by=m

where a, b and m are integers

There are solutions if and only if (a,b) | m.

If there are solutions, and x0 and y0 is a solution, then

x=x0+(b/(a,b))k and y=y0-(a/(a,b))k

are also solutions.

If a and b have a gcd of 1, then there are infinitely many solutions for any m.

ex: 17x+3y=101 or anything

ex: 39x+51y = 7

gcd is 3 and 3 does not divide 7, so no solutions

ex: 119x-29y=8

use the euclidean algorithm to solve

119=4x29+3

29=9x3+2

3=1x2+1

2=2x1+0

GCD is 1.

3=119-4x29

2=29-9x3 = 29-9x(119-4x29) = -9x119 + 37x29

1=3-2 =119-4x29 - (-9x119+37x29) = 10x119-41x29

thus, we can express the gcd as a linear combo of the two coefficients

since our m is 8, multiply by 8

8 = 80x119 - 328x29

this method allows us to find one solution.

Class 6

Class 6 was a group quiz - Chapter 2, Project 1 a & b on pg 54 (Pythagorean Triples) and Project 2 on pg 55 (sum of divisors function)

Class 5

Section 2.3 Exercise 17 - Show that if n has t divisors, then the product of all the positive divisors of n in n^t/2.

Look at some examples:

Let n=6

Divisors are 1, 2, 3, and 6. Multiplying, 1x2x3x6 = 6² = 36 which is n^t/2 because in our case t=4.

In general, the prime factorization of n=p1^a1p2^a2...pk^ak

any divisor of n, d=p1^b1p2^b2...pk^bk for bi btwn 0 and ai

The total number of divisors, t = (a1+1)(a2+1)...(ak+1)

Do it by induction...

1) k=1, just 1 prime factor

then n=p^a

divisors are p, p², p³, ... ,p^k

the number of divisors is a+1

take as an example 3⁴

the product of the divisors is 1 x 3 x 3² x

we left this exercise open

Exercise 2 - Determine the set of integers for which the number of divisors is odd. Make a general conjecture and prove your claim.

t=(a1+1)(a2+1) ... (ak+1)

Conjecture is that all such numbers is a perfect square.

Exercise 4 - it's just an exercise in plugging into the algorithm.

Exercise 11 - Show that any positive integer n can be written uniquely as n = 2^rS, where S is odd.

Prove by construction.

Consider 2 cases: n is even, n is odd.

If n is odd, then n = 2⁰n, so S = n

If n is even ,then...

Let n/2=n1; n=2n1

Consider 2 case: n1 is even, n1 is odd.

Thursday's class will be a group project, relevant to today's and yesterday's lesson. Similar to the projects on pp 53-54. The group project will count as the quiz.

Lesson

Fermat's factoring method - takes advantage of the difference of two squares n=a²-b²

See exercise on pg 35 - Factor 517 using Fermat's method.

Find the smallest square greater than 517.

23² = 529

difference is 12

12 is not a perfect square, so go up on more

24² = 576

difference is 59

59 is not a perfect square, so go up one more

25² = 625

difference is 108

108 is not a perfect square

...

29² = 841

difference is 324, which is a perfect square 18²

so 517 = 29²-18²

517 = (29+18)(29-18)

517 = 47x11

An aside... in a problem that states "if two number are both of the form 4k+1, show that their product is also of the form 4k+1" you can't start by saying (4k+1)(4k+1). because the numbers are not equal, they just both have the same form. instead, say (4k+1)(4m+1)

This method does not work for numbers of the form 4k+2. because the process would continue forever.

Any perfect square m² will only have remainder 0 or 1 if divided by 4. 0 if m is even, 1 if m odd.

a² mod 4 = 0 or 1

b² mod 4 = 0 or 1

so a²-b² can only have remainder 0, 1 or 3. There's no way for it to have remainder of 2.

That means if n=4k+2, then it can never be written as the difference of 2 squares.

Take k=86, then n=4x86+2=346.

n=4k+2 is always even.

So, to solve this, taken n/2 which is always odd. In our example, n/2=173. This will be able to be factored by Fermat's method.

Next section: 2.5 - GCD and LCM - Greater common divisor and least common multiple.

Notation: gcd(a,b) is also noted as just (a,b) ; lcm(a,b) is also noted as [a,b]

Lemma 2.5.4

(a, b) = (-a, b)

(a, b) = (a-b, b)

If (a, b) = d then (a/d, b/d) = 1

This is also called a/d and b/d being relatively prime

Theorem 2.5.6

For any two integers a and b there exist m and n such that ma+nb = (a, b)

Proposition 2.5.10

To find (a, b), take the prime factorization and take product of the min of each power of each prime factor.

To find [a, b], take the prime factorization and take the product the of max of each power of each prime factor.

It is clearly true that (a, b) = (b, a) and similarly [a, b] = [b, a]

Exercise 1

Compute the gcd of the following pairs of numbers by (i) prime factorization and (ii) Euclidean algorithm.

(c) (6963, 7385)

6963 = 3 x 11 x 211

7385 = 5 x 7 x 211

(a, b) = 211

[a, b] = 3 x 5 x 7 x 211 = 243,705

Euclidean Algorithm

See pg 43 and the example there.

(7385, 6963)

x=7385

y=6963

7385 = 1 x 6963 + 422

6963 = 16 x 422 + 211

422 = 2 x 211 + 0

r=0, so we're done. and gcd=211

This allows you to find the gcd without factoring.

Class 4

Section 2.3 - Problem 1 - pg 31

1. Show that a number is a square if and only if all the exponents in its prime factorization are even.

Part one: show that if all the exponents are even, then it's a square

Let a1, a2, a3, ... be even

therefore there exist b1, b2, b3, ... in Z such that ai = 2bi for all i from 1 to k

hence, n=p^2b1p^2b2p^2b3...

since n=(p^b1p^b2p^b3...)²

and

m=(p^b1p^b2p^b3...) is in Z

so

n=m2 and n is a square

Part two: show that if it's a square, then the exponents are even

Let there exist an m in Z such that n=m²

Let m have prime factorization

m=(q^c1q^c2q^c3...)

therefore

m2 =(q^c1q^c2q^c3...)²

= (q^2c1q^2c2q^2c3...)

Since All the exponents 2c1, 2c2 and 2c3 are all even and the prime factorization is unique, all exponents in the factorization of n are even.

Exercise 10

Prove that the square root of n is irrational if n is not a perfect square.

In other words: If n is not a perfect square, then square root of n is irrational.

Formulate the contrapositive. I.e. not q implies not p

If the square root of n is rational then n is a perfect square.

Proof:

Suppose sqr(n) is rational. Then there exist a, b in Z such that

sqr(n) = a/b

Square both sides

n=a²/b²

and further,

a² = nb²

Let p1, p2, p3, ... , pk be the combined set of primes in the factorizations of a, b and n.

and let a = p1^a1p2^a2p3^a3... and similarly for b and n.

Therefore p1^2a1p2^2a2... = p1^2b1+d1p2^2b2+d2...

Hence, for all i, 2a_i = 2b_i + d_i

and

d_i = 2a_i - 2b_i = 2(a_i-b_i)

and

d_i is even for all i

Therefore n is a perfect square.

Exercise 12

Determine the prime factorization of 61! and 100!

Refer to proposition 2.3.8 (pg 30): if p less than or equal to n, the exponent of p in the factorization of n! is floor(n/p) + floor(n/p2) + floor(n/p3) + ...

61! = 2⁵⁶ 3²⁸ 5¹⁴ 7⁹ 11⁵ 13⁴ 17³ 19³ 23² 29² 31 (rest of the primes to the first power) 37 41 43 47 53 57 59 61

Section 2.4 - Elementary Factoring Methods

Factoring algorithm - by trial division

Fermat's factoring method - based on the assumption that if a number can be expressed as a difference of squares: a2-b2, then it can be factored into (a+b)(a-b)

Class 3

Went of homework problems and had homework quiz.

Next homework:

2.3 - 2, 3, 6, 11, 17

2.4 - 2, 8

On the half open interval (a,b], the number of integers between b and a is N= floor(b)-floor(a).

On the half open interval [a,b), N=ceiling(b)-ceiling(a)

On the open interval (a,b), consider 4 cases:

1. Both a and b are not integers N=floor(b)-floor(a).

2. a is an integer and b is not, N=floor(b)-floor(a), just like in 1. So we can generalize: if b is not an integer, N=floor(b)-floor(a).

3. a not an integer, b is an integer N=floor(b)-floor(a)-1

4. a is an integer, b is an integer, N=floor(b)-floor(a)-1, just like in 3. So we can generalize: if b is an integer, N=floor(b)-floor(a)-1

So we have two general formulas:

N=floor(b)-floor(a)

and

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

We want something that is 1 when b is an integer and 0 when it's not.

Notice that ceiling(b)-floor(b) = {1 if b is not an integer; 0 if b is an integer}

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

Unique Factorization

The fundamental theorem of arithmetic: Every positive integer greater than 1 can be factored uniquely into a product of primes.

n = p₁^a₁p₂^a₂p₃^a₃...

This is called the canonical form.

We can find the total number of divisors: first find the prime factorization.

252 = 2²3²7¹

# of divisors = (e1+1)(e2+1)(e3+1) = 3 x 3 x 2

i.e. multiply each of the exponents plus 1

see proposition 2.3.5 - square root of 2 is irrational

proved using unique factorization

see proposition 2.3.8 - find the exponent of p in the factorization of n!

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.

Class 1 - Introduction

Some mathematicians think number theory has little value. Others are fascinated by it.

There are limited applications. It's a great brain exercise. Uses simple objects (integers), yet there are many interesting results that can be proven.

Some topics:

divisibility

prime numbers

congruency relationships

There are some connections to abstract algebra

Assignment:

2.1 - 2, 6, 7, 10, 15

2.2 - 5, 10

Read the book before we cover the material. Read ahead a couple of sections.

Definitions:

square numbers - perfect squares. can be represented graphically with dots.

triangle numbers - same representation, but in a triangle: 1, 3, 6, 10, 15.

pythagorean triple - ppl try to develop a scheme that allows them to develop triples. some numbers cannot be in a triple. for instance, the hypotenuse must be the sum of two squares.

Chapter 2 is more formal. starts with definitions. pg 7 - divisibility.

a|b is read "a divides b".

a|b if there exists c in Z such that b=ac

there's also a symbol for "a does not divide b"

if a|b and x|y then ax|by

if a|b and b|c then a|c - transitivity

if a|b and b<>0 then |a|<=|b|

Follow the proofs that are given in the book and try to prove the others yourself.

Prime Numbers

Smallest prime number is 2. It's important that we do not consider 1 prime. Prime means that it is only divisible by itself and 1. I.e. the only divisors of p are 1 and p itself.

The opposite of prime is composite. Composite numbers can be written as a product of primes.

The division theorem: if we have two integers, b and a, there are two unique integers such that a=bq+r where r<|b|.

Q1: Divisors of 1 are... 1 and -1.

Positive integers are the natural numbers.

Whole numbers are the natural numbers plus 0.

2c. If a|b, then a|kb for all k in Z.

Proof:

Let a|b, then there is a c, such that b = ac.

Since b = ac, kb = kac or kb = a(kc)

Since k is in Z and c is in Z, then kc = n is in Z.

Therefore, kb = an where n is in Z.

Hence, a|kb.

Greatest integer function aka floor of x.

See definition on page 11.

The largest integer that does not exceed x.

[x] = n means

n<=x

n+1>x

n is in Z

Ceiling is the smallest integer that is greater than or equal to x.

If x is an integer, then x is equal to both its floor and its ceiling.

See lemma 2.1.13.

See also lemma 2.1.11 to find the number of positive multiples of a given integer within a given interval.

Number of multiples of d that are <=n is the floor of n/d.

Page 14, exercise 16:

Determine the number of integers between 200 and 400 that are divisible by 3.

[400/3]-[200/3] = 133-66 = 67

divisible by 7:

[400/7]-[200/3] = 57-28 = 29

by 3 or 7:

need to subtract out the multiples of 21. apply the union rule of the addition of sets:

n(AuB) = n(A)+n(B)-n(AintersectB)

[400/21]-[200-21] = 19-9 = 10

Therefore the answer is 67+29-10 = 86

exercise 8:

show that when n is odd, n2-1 is a multiple of 8

n is odd means n=2k+1

n2 = (2k+1)(2k+1) = 4k2+4k+1

n2-1 = 4k2+4k

n2-1 = 4k(k+1)

Case 1 - k is even

k=2L for some L in Z

n2-1 = 4(2L)(2L+1) = 8L(L+1)

Hence, 8|(n2-1)

Case 2 - k is odd

k+1=2L for some L in Z

n2-1 = 4k(2L) = 8kL

Hence, 8|(n2-1)

Exercise 9:

Show that a perfect square is never of the form 3k+2 for any k.

Assume that n2 = 3k+2.