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.