# Lecture Notes for Math 22: Divisibility

Abstract

1 Divisibility

• Take questions and review some concepts from homework.

• Theorem ( Division algorithm ): If a, b ∈ Z and a ≠ 0, there exist unique integers, q and
r, such that b = qa + r, where 0 ≤ r < |a|, or

Proof: Note that a = sgn(a)|a|, so we can consider the case of a and b both positive.
The quotient is how many times a may be subtracted from b before b becomes negative .
That is, q is largest integer n such that b - na is nonnegative; then r = b - qa.

– Let S = {b- na | n ∈ Z and b - na ≥ 0. Note that if b ≥ 0, then b - 0a = b ∈ S,
so S is not empty.

– Call r the smallest element of S. Note that r < |a|, since if r ≥ a, then 0 ≤
r - a = b - qa - a = b - (q + 1)a ∈ S, contrary to the as sumption that r is the
smallest
member of S.

– Uniqueness: Suppose that b = aq + r = aq' + r', where 0 ≤ r, r' < a. Then
r = b - aq and r' = b - aq' are both in S. Since elements of S differ by multiples
of a, only one member lies in [0, a). Because r and r' both fall in this interval, we
have r = r'. Then b - aq = b - aq', whence q = q'.

• Let be the set of divisors of n, and let be the set of positive divisors of n.

• Definition: A natural number p > 1 is prime if the only positive divisors of p are 1 and
p; that is, if  = {1, p}. Note that 1 is not prime.

• The set of prime numbers is often denoted by P.

• The set of natural numbers n > 1 that are not prime are called composite.

• The set of composite numbers is often denoted by C. Then N = {1} ∪ P ∪ C.

• Any composite number n can be written as a product of other numbers , each
of which may be prime or composite. Recurse until you have a product of primes,
so: Theorem: Any natural number > 1 can be factored as a product of primes, n =

• Theorem: There are infinitely many prime numbers. Proof (Euclid): Suppose, to the
contrary, that there is a largest prime number, so there are only a finite set of them,
{. The number is then not divisible by any of them, etc.
Note that this does not mean that 2 · 3 · 5 · 7 · 11· 13 + 1 = 30031 = 59 · 509 is prime!
(Also note that the prime factors of 30031 are both greater than 13.)

• Example: = {±1,±2,±3,±6,±7,±9,±14,±18,±21,±42,±63,±126}

• Example: = {±1,±2,±3,±5,±6,±10,±15,±25,±30,±50,±75,±150}

• Note that = {±1,±2,±3,±6} is the set of numbers that simultaneously
divide 126 and 150. The set has a greatest element , namely 6, called the greatest
common divisor of 126 and 150.

• Definition: Given integers m and n, not both zero , the greatest common divisor (GCD)
of m and n, denoted by gcd(m, n), is the natural number d such that

– d|m and d|n, and
– u|m and u|n => d ≥ u.

• Example: To compute gcd(m, 0), note that = Z\{0}, so = . The
greatest element of is |m|, so gcd(0,m) = |m|.

• Definition: Two integers m and n, not both zero, are relatively prime if gcd(m, n) = 1.
That is, m and n are relatively prime if they have no common factors other than ±1.
Note that two numbers do not need to be prime in order to be relatively prime; for
example, 14 and 15 are relatively prime, even though neither is prime.

• Note that the definition of gcd and of relatively prime can be extended to more than
two numbers. For example, gcd(30, 42, 66) is the maximum number in the set
, which is 6. Moreover, the numbers 30, 42 and 66 are not relatively prime,
but the numbers 30, 42 and 65 are relatively prime because .

• The least common multiple (LCM) of m and n, not both zero, is the smallest positive
integer that is a multiple of both m and n. It is denoted by lcm (m, n). We know that
mn is a multiple of both m and n, so lcm(m, n) ≤ mn, which shows that lcm(m, n)
always exists.

 Prev Next

Start solving your Algebra Problems in next 5 minutes!

2Checkout.com is an authorized reseller
of goods provided by Sofmath

Attention: We are currently running a special promotional offer for Algebra-Answer.com visitors -- if you order Algebra Helper by midnight of October 21st you will pay only \$39.99 instead of our regular price of \$74.99 -- this is \$35 in savings ! In order to take advantage of this offer, you need to order by clicking on one of the buttons on the left, not through our regular order page.

If you order now you will also receive 30 minute live session from tutor.com for a 1\$!

You Will Learn Algebra Better - Guaranteed!

Just take a look how incredibly simple Algebra Helper is:

Step 1 : Enter your homework problem in an easy WYSIWYG (What you see is what you get) algebra editor:

Step 2 : Let Algebra Helper solve it:

Step 3 : Ask for an explanation for the steps you don't understand:

Algebra Helper can solve problems in all the following areas:

• simplification of algebraic expressions (operations with polynomials (simplifying, degree, synthetic division...), exponential expressions, fractions and roots (radicals), absolute values)
• factoring and expanding expressions
• finding LCM and GCF
• (simplifying, rationalizing complex denominators...)
• solving linear, quadratic and many other equations and inequalities (including basic logarithmic and exponential equations)
• solving a system of two and three linear equations (including Cramer's rule)
• graphing curves (lines, parabolas, hyperbolas, circles, ellipses, equation and inequality solutions)
• graphing general functions
• operations with functions (composition, inverse, range, domain...)
• simplifying logarithms
• basic geometry and trigonometry (similarity, calculating trig functions, right triangle...)
• arithmetic and other pre-algebra topics (ratios, proportions, measurements...)

ORDER NOW!