Prime Number

(1) Definition (Prime Number) A prime number is a positive integer greater than 1 that is divisible by no positive integers other than 1 and itself.

(2) Definition (Composite Number) A positive integer greater than 1 that is not prime is called a composite number.

(3) Example (Sieve of Eratosthenes) Using the sieve of Eratosthenes, find the prime numbers less than 100.

    Solution.    
    

(4) Proposition (Prime Divisor) Every positive integer greater than 1 has a prime divisor.

(5) Proposition (Infinitude of Primes) There are infinitely many primes.

    Proof. Assume that the prime numbers are listed in ascending order with and so on; and assume (for a contradiction) that is the last prime. Consider the integer,



Since every positive integer greater than 1 has a prime divisor, has a prime divisor, say However, can not divide since is of the form, Therefore, , the last prime number cannot exist.

(6) Proposition (Bounding Factors) If is a composite integer, then has a prime factor not exceeding

(7) Definition (Greatest Common Divisor) Let and be two integers that are not both zero. Then the greatest common divisor of and is the largest integer that divides both and The greatest common divisor of and is denoted by or sometimes by

(8) Example (Greatest Common Divisor) The integers 4 and 8 have greatest common divisor of 4 and we write since 4 is the largest integer that divides both 4 and 8. Also and

(9) Definition (Relatively Prime) If then and are said to be relatively prime.

(10) Example (Relatively Prime) Note that and so 2 and 5 are relatively prime. But and so 8 and 24 are not relatively prime.  

(11) Definition (Linear Combination) A linear combination of and is an integer of the form where and are integers.

(12) Example (Linear Combination) Note that given 2 and 51 we can form many different linear combinations, here are three examples: and

(13) Proposition (Properties of Greatest Common Divisors)  Let and be integers, then

    (i) for some integers and
    
    (ii) the set of linear combinations of and is the set of multiples of
    
    (iii) if and only if there exists integers and such that
    
    (iv) is the least positive integer that is a linear combination of and
    
    (v) if then
    
    (vi) if and only if and if is another common divisor then
    
    Proof. (i) Consider the set



Since is nonempty, ( are in ), the Well-Ordering Principle yields a least positive integer such that for some integers   and The idea is to show that To do this we use the Division Algorithm obtaining and such that where If then is in because   But we can not have is in S because and is the least in Therefore and so Using the same argument with replaced by it is shown that To show it remains to show that is greater than any other common divisor of and and so let be a common divisor of and Then using Properties of Divisibility, that is and so
     (ii) By part (i), if then for some integers and Thus every multiple of is also a linear combination of and Conversely, let be a linear combination of and Then using Properties of Divisibility, and so   is a multiple of
     (iii) If then by there exists integers and such that Conversely, suppose and that for some integers and Then because and so
     (iv) This follows from the Well Ordering Principle as in the proof of (i).
     (v) If then for some integers and Since and we have and by (ii)
     (vi) If then by definition, and Let be a common divisor of and with and for some integers and   By (i), there exists and such that and therefore we have   Whence,

(14) Example (Showing Relatively Prime) Show that and are relatively prime.

    Solution. Since it follows that

(15) Definition (Mutually Relatively Prime) The integers are called mutually relatively prime when

(16) Example (Mutually Relatively Prime) The integers 3, 5, 7 are mutually relatively prime and the integers 4, 19, 27 are mutually relatively prime.  

(17) Definition (Pairwise Relatively Prime) The integers are called pairwise relatively prime when for every possible and with

(18) Example (Pairwise Relatively Prime) The integers 3, 5, 7 are pairwise relatively prime because and The integers 4, 19, 27 are pairwise relatively prime because and
    The integers 10, 14, and 35 are mutually relatively prime because (there is no common divisor for all three) however they are not pairwise relatively prime because    

(19) Example (Great Common Divisors) What is where and are relatively prime integers that are not both 0?

    Solution. Let be a prime dividing Then



Now if then since But so Similarly, Therefore, and so or If and have the same parity, then and and so But if and have opposite parity, then and

(20) Example (Great Common Divisors) Show that if is an integer, then the integers and are relatively prime.

    Solution. Suppose that Then We have so if it follows that Hence To show that it is sufficient to show that neither 2 nor 3 divides If or and then and However, there are no such pairs in the set     

(21) Example (Great Common Divisors) Show that every positive integer greater than 6 is the sum of two relatively prime integers greater than 1.

    Solution. By the previous example, we know that   and are pairwise relatively prime. To represent as the sum of two relatively prime integers greater than one, let We now examine the twelve cases, one for each possible value of in the following table:
    

Number Theory Books

A Beginner's Guide to Constructing the Universe: Mathematical Archetypes of N... List Price: $18.95 Buy New: $10.45 You Save: $8.50 (45%) New (37) Used (28) from $8.49The Universe May Be a Mystery,But It's No SecretMichael Schneider leads us on a spectacular, lavishly illustrated journey along the numbers one through ten to explore the mathematical principles made visible (more)

Bayesian Computation with R (Use R) List Price: $49.95 Buy New: $33.51 You Save: $16.44 (33%) New (32) Used (8) from $33.51There has been a dramatic growth in the development and application of Bayesian inferential methods. Some of this growth is due to the availability of powerful simulation-based algorithms to summarize (more)

e: The Story of a Number List Price: $19.95 Buy New: $8.23 You Save: $11.72 (59%) New (42) Used (32) Collectible (1) from $3.25The interest earned on a bank account, the arrangement of seeds in a sunflower, and the shape of the Gateway Arch in St. Louis are all intimately connected with the mysterious number e. In this informal (more)

Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathem... List Price: $16.00 Buy New: $8.91 You Save: $7.09 (44%) New (35) Used (15) from $7.49In 1859, Bernhard Riemann, a little-known thirty-two year old mathematician, made a hypothesis while presenting a paper to the Berlin Academy titled ?On the Number of Prime Numbers Less Than a Given Quantity.? (more)

Euler's Gem: The Polyhedron Formula and the Birth of Topology List Price: $27.95 Buy New: $17.00 You Save: $10.95 (39%) New (27) Used (3) from $14.99Leonhard Euler's polyhedron formula describes the structure of many objects--from soccer balls and gemstones to Buckminster Fuller's buildings and giant all-carbon molecules. Yet Euler's formula is so (more)

Dr. Euler's Fabulous Formula: Cures Many Mathematical Ills List Price: $29.95 Buy New: $17.98 You Save: $11.97 (40%) New (36) Used (10) from $17.98I used to think math was no fun'Cause I couldn't see how it was doneNow Euler's my heroFor I now see why zeroEquals e[pi] i+1--Paul Nahin, electrical engineer In the mid-eighteenth century, Swiss-born (more)

The Fabulous Fibonacci Numbers List Price: $28.98 Buy New: $15.00 You Save: $13.98 (48%) New (35) Used (11) Collectible (1) from $14.50The most ubiquitous, and perhaps the most intriguing, number pattern in mathematics is the Fibonacci sequence. In this simple pattern beginning with two ones, each succeeding number is the sum of the two (more)

Killer Poker By the Numbers: Mathematical Edge for Winning Play (Killer Poker) List Price: $14.95 Buy New: $7.69 You Save: $7.26 (49%) New (35) Used (13) from $7.69Killer Poker By the Numbers: Mathematical Edge for Winning Play (Killer Poker) (more)

Sacred Number: The Secret Quality of Quantities (Wooden Books) List Price: $12.00 Buy New: $5.59 You Save: $6.41 (53%) New (30) Used (13) from $5.59Numbers permeate every aspect of our lives; very little happens without a basic ability to manipulate the simple whole numbers we all take for granted. Beautifully illustrated with old engravings as well (more)

The Music of the Primes: Searching to Solve the Greatest Mystery in Mathematics List Price: $13.95 Buy Used: $0.98 You Save: $12.97 (93%) New (28) Used (29) from $0.98In 1859, German mathematician Bernhard Riemann presented a paper to the Berlin Academy that would forever change the history of mathematics. The subject was the mystery of prime numbers. At the heart of (more)

• print this page
• pages linking here
• related pages