Number Theory

Number theory is one of the oldest branches of pure mathematics, and one of the largest. Of course, it concerns questions about numbers, usually meaning whole numbers or rational numbers (fractions).

Elementary number theory involves divisibility among integers, the Euclidean algorithm (and thus the existence of greatest common divisors), elementary properties of primes (the unique factorization theorem, the infinitude of primes).

Divisibility

 

Divisibility Test

 

Are there easy ways to tell when one whole number is divisible by another? 

 

Divisibility is a relation on the set of whole numbers. So we  can examine the relation to see what properties of a relation it possesses. 

 

Is  divisibility reflexive on W?   

Does a ¸a return a result that is an element of W for every aÎW?

              Yes, (if a ¹ 0 )  

 

Is  divisibility reflexive on N?    Yes

   

Is divisibility symmetric on W?  No, because if a divides b, b does not divide a (and return an element in W).

 

Example:   2 divides 4 (4¸2) (and returns an element in W) but 4 does not divide 2(2¸4) (and return an element in W.)

 

Is divisibility symmetric on N?  No

Is divisibility transitive on W, N?  Yes, since no counter example exists.

If a divides b and b divides c, then a must divide c.

Example:

2 divides 4 and 4 divides 8, so 2 divides 8.

Thus, divisibility is not an equivalence relation.

 

Divisibility Tests

 

Divisibility by 2: A number a is divisible by 2, if and only if the units digit of x is divisible by 2.

 

 

Divisibility by 3: A number a is divisible by 3, if and only if the sum of the digits of x is divisible by 3.

 

 

Divisibility by 4: A number a is divisible by 4, if and only if the number  represented by the last two digits of x is divisible by 4.

 

 

Divisibility by 5: A number a is divisible by 5, if and only if its units digit is divisible by 5 or if its units digit is zero.

 

 

Divisibility by 6: A number a is divisible by 6, if and only if it is divisible by both 2 and 3.

 

 

Divisibility by 7:  Too complicated

 

 

Divisibility by 8: A number a is divisible by 8 if and only if the number formed by the hundreds, tens, and units digit of a is divisible by 8.

 

 

Divisibility by 9:  A number a is divisible by 9, if and only if the sum of the digits of x is divisible by 9.

 

 

Divisibility by 10: A number a is divisible by 10, if and only if the units digit is zero.

 

 

 

Factors

 

Consider the relationship between the number 3 and the set {0, 3, 6, 9, 12 …}

If any number in this set is divided by 3, the remainder is zero.

 

For 12, we would say “3 is a divisor of 12” or “3 divides 12” or “12 is a multiple of 3” or  “3 is a factor of 12”.

 

Definition:    If a & c Î N and if there exists a whole number, b, such that such that a´b = c. then we say:

 

     “a is a factor of c”

or “a is a divisor of c”

or “”a divides c

or “c is a multiple of a”

 

Example:

 

Is 7 a factor of 42?  Yes because 7´6 = 42.

 

Zero is a special case

 

Is 5 a factor of zero? yes because 5´0 = 0 (zero is a whole number but  not a natural number)

 

Is 0 a divisor of 5? No, because 0´n¹5.

 

 does not exist.

 

Zero is a multiple of every natural number, but zero is not a divisor of any number

 

Example: list all of the factors of 36

 

1,2,3,4,6,9,12,18,36

 

list all factors of 20

1, 2, 4, 5, 10, 20

list all of the common factors of 20 and 36

 

1,2,4

 

list the greatest common factor of 20 and 36

 

4

 

notation GCF(20,36) = 4

 

One use of GCF is reducing fractions

 

=  =  = 1´

 

writing in lowest terms or simplified form  =

 

Prime Numbers

 

A natural number, n, is said to be prime if n has exactly two factors, 1 and itself.

 

Is 1 a prime number?

 

No,  1 has only 1 factor.

 

If a number is not prime, it is composite.

 

Prime numbers are infinite.

 

p = {x|x is a prime number},

 

 = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,…}

 

Prime numbers are the building blocks of number theory.

 

Sieve of Eratosthenes

 

Greek mathematician (276 – 195 B.C.)

 

http://www.math.utah.edu/~alfeld/Eratosthenes.html

 

X

2

3

42

5

62

7

82

93

102

11

122

13

142

153

162

17

182

19

202

213

222

23

242

255

262

273

282

29

302

31

322

333

342

355

362

37

382

393

402

41

422

43

442

453

462

47

482

497

502

513

522

53

542

555

562

573

582

59

602

61

622

633

642

655

662

67

682

693

702

71

722

73

742

753

762

777

782

79

802

813

822

83

842

855

862

873

882

89

902

917

922

933

942

955

962

97

982

993

1002

Primes Less Than 100

 

Fundamental Theorem of Arithmetic.

 

Every natural number greater than 1 is either prime or can be factored into a product of prime numbers, if the primes are placed in increasing order.

 

Every integer N > 1 can be written uniquely as a product of finitely many prime numbers.

 

 

Examples of factoring into prime numbers: 

 

   6 = 2´3

 12 = 4´3 = (2´2)´3 = 22´3

 36 = 6´6 = (2´3)´2´3) = (2´2)´(3´3) = 22´32

 72 = 2´6´6 = 2´(2´3)´2´3) = (2´2´2)´(3´3) = 23´32

 

 

Danish division

when you get to 1 you’re finished

72 = 23´32

 

Class Exercise:

 

 

What are the prime factors of 108?

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

108 = 22´33

 

 

 

 

 

List all of the factors of 72?  How many factors are there for 72?

 

 

72 = 23´32

 

Answer: 12 factors,  four choices for 2’s (20, 21, 22, 23),  three choices (30, 31, 32)

 

 

 

Class exercise:

 

List all of the factors of 98.

 

 

 

 

 

 

 

 

 

 

 

Answer:

 

98 = 2´49 = 21´72

 

 

20´70 = 1

20´71 = 7

20´72 = 49

 

21´70 = 2

21´71 = 14

21´72 = 98

 

Least Common Multiple

 

If aÎN and cÎW and if there exists bÎW such that a´b = c, then c is a multiple of a.

 

Example:

 

List the multiples of 12

 

 = {12, 24, 36,48,60,72,84,96,108 …}

 

 

List the multiples of 18

 

 = {18,36,54,72,90,108,126 …}

 

List the common multiples of 12 & 18

 

 = {36, 72, 108 …}

 

Therefore the least common multiple of 12 and 18 is 36

 

 

 

Determine the LCM via prime factorization

 

12 = 4´3 = 2´2´3 = 22´31

18 = 2´9 = 2´3´3 = 21´32

 

select the largest multiple (prime factor with the largest exponent) from each number that is a prime factor of either number.

 

LCM(12,18) = 22´32 = 4´9 = 36

 

Example:

 

Find the LCM(54,60)

 

 

 

 

 

 

54 = 6´9 = 2´3´3´3 = 2´33

60 = 6´10 = 2´3´2´5 = 22´3´51

 

LCM(54,60) = 22´33´51 = 4´27´5 = 540

 

 

Greatest Common Factor

 

Definition:  The greatest common factor (GCF) of two whole numbers x and y, denoted by GCF(x,y) is the largest natural number that is a divisor of both x and y.

 

Determining the GCF using prime factorization:

 

determine GCF(20,36)

 

20 = 4´5 = 22´51

36 = 4´9 = 22´32

 

Modify so each prime number is common to both factorizations:

 

20 = 4´5 = 22´30´51

36 = 4´9 = 22´32´50

 

 

 

Select the least amount of each prime factor from both the factorizations:

 

The least number of 2’s is 2

 

The least number of 3’s is zero

 

The least number of 5’s is zero.

 

 

GCF(20,36) = 22´30´50 = 4´1´1 = 4

 

 

 

Class Exercise:

 

 

Find GCF(78, 198)

 

 

 

 

 

 

 

 

 

 

 

 

Answer:

78 =  2´39 = 21´31´131

198 = 2´99 = 2´9´11 = 21´32´111

 

 

GCF = 21´31´110´130 = 6

 

 

 

 

To summarize, for GCF or LCM:

 

Break number into prime components

 

For LCM, select all of the prime numbers from either factor with the largest exponents.

 

For GCF, select all of the prime numbers from either factor with the smallest exponent.

 

Example:  Find the LCM(45,72) and GCF(45,72)

 

45 = 9´5 = 3´3´5 = 32´51

72 = 8´9 = 2´2´2´3´3 = 23´32

 

LCM (45,72)= 23´32´51 = 8´9´5 = 360

 

GCF(45,72) = 32 = 9

 

Relationship between LCM and GCF

 

LCM(a, b)´GCF(a, b) = a´b

 

Example:

 

 

LCM(45,72)´GCF(45,72) = 360´9 = 3240

 

45´72 = 3240

 

So, if you have either the LCM or the GCF, you can find the other.

 

Example:

 

GCF(36,100) = 4

 

LCM´GCF = 36´100

 

LCM´4 = 3600

 

LCM = 3600/4 = 900

 

Some uses of LCM and GCF:

 

One rectangular swimming pool has an area of 24 square yards. Another rectangular swimming pool has an area of 90 square yards. What is the largest possible dimension common to both pools?

 

24 = 23´31

90 = 21´32´51

 

GCF(24, 90) = 21´31´50 = 6

 

 

 

 

 

Add the following fractions:

 

 +

 

Find LCM(12,18)

 

12 = 4´3 = 2´2´3 = 22´3

18 = 2´9 = 2´3´3 = 2´32

 

LCM(12,18) = 22´32 = 4´9 = 36

 

(´ ) + (´ ) =  +  =

 

 

 

 

 

Bill can paint a house in 6 hours and Mary can paint the same house in 4 hours.  How many hours will it take Bill and Mary working together to paint one house.

 

 

 

LCM(4,6)

 

4 = 22

6 = 21´31

 

LCM = 22´31 = 4´3 = 12

 

 

 

Bill’s time for multiple houses:  6,12,18,24,30,36

Mary’s time for multiple houses:  4,8,12,16,20,24

 

LCM(4,6) = 12

 

Bill can paint 12/6 = 2 houses in 12 hours

 

Mary can paint 12/4 = 3 houses in 12 hours

 

Together they can paint 5 houses in 12 hours   = 2.4 hours per house