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)