# Algorithm

Definition: An integer b is divisible by a
non zero integer a if there is an integer c
such that ac = b.

Note: Saying that b is divisible by a is
equivalent to saying any of the following:
a is a divisor of b.
a divides b.
a is a factor of b.

Notation: aІb denotes that a divides b.

Theorem 1: For any  integers a, b, and c:

a. aІ0, 1Іa, and aІa.
b. aІ1 if and only if a = ±1.
c. If aІb and cІd, then acІbd.
d. If aІb and bІc, then aІc.
e. aІb and bІa if and only if a = ±b.
f. If aІb and aІc, then aІ(bx + cy) for any
integers x and y.

Some proofs of Theorem 1

Th 1a: aІ0, 1Іa, and aІa.

Recall: aІb
<=> ac = b for some integer c.

Proof: a·0 = 0, 1·a = a, and a·1 = a.
So it fol lows from the def . of “is

a divisor of” that aІ0, 1Іa, and aІa.

Th 1b: aІ1 if and only if a = ±1.

Proof: By the definition of “is a divisor of,”
aІ1 => ac = 1 for some integer c.
But the only integers whose product
is 1 are 1·1 and (-1)·(-1). So a = ±1.

On the other hand,
a = ±1 => a·(±1) = 1 => aІ1.

Th 1d: If aІb and bІc, then aІc.

Scratch work:
aІb and bІc => ap = b and bq = c
=> a(pq) = (ap)q = bq = c
=> aІc

Th 1d: If aІb and bІc, then aІc.

Proof: By the def. of “is a divisor of’” there
are integers p and q such that
aІb and bІc => ap = b and bq = c
=> a(pq) = (ap)q = bq = c

It now follows from the def. of “is a
divisor of that aІc.

Th 1e: aІb and bІa if and only if a = ±b.

Sketch of Proof in one direction :

Greatest Common Divisor

d is the greatest common divisor of
integers a and b if d is the largest integer
which is a common divisor of both a and b.

Notation:
d = gcd(a, b)

Example: ±2, ±7, and ±14 are the only
integers that are common divisors of both
42 and 56. Since 14 is the largest,
gcd(42, 56) = 14.

Use of the gcd

Reducing fractions

Not all fractions are easily reduced.

The Division Algorithm

For integers a and b, with b > 0, there
exist integers q and r such that

a = qb + r and 0 ≤ r < b.

Euclidean Algorithm

To find gcd(a, b) where b < a:

Divide b into a and let r1 be the remainder.
Divide r1 into b and let r2 be the remainder.
Divide r2 into r1 and let r3 be the

remainder.
Continue to divide the remainder into the
divisor until you get a remainder of zero.

gcd(a, b) = the last nonzero remainder.

Find gcd(8633, 8051)

Theorem 2

For any nonzero integers a and b, there
exist integers x and y such that

gcd(a, b) = ax + by.

Here’s how you use the Euclidean
Algorithm to write gcd(8633, 8051) as a
linear
combination of 8633 and 8051.

• Use the Euclidean Algorithm to find
gcd(8633, 8051).

Solve each division problem, except the
last one, for the remainder (r = a – bq) .
Take note of the quotient in each solution .

• Use these equations
in reverse order to find
the linear combination .

 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 February 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!

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

 "It really helped me with my homework.  I was stuck on some problems and your software walked me step by step through the process..." C. Sievert, KY

 Sofmath 19179 Blanco #105-234San Antonio, TX 78258 Phone: (512) 788-5675Fax: (512) 519-1805