SolitaryRoad.com

Website owner:  James Miller


[ Home ] [ Up ] [ Info ] [ Mail ]

Divisors, factors and multiples of integers; common divisor, greatest common divisor, common multiple, least common multiple, division algorithm, Euclid’s algorithm, unique factorization theorem




a divides b. We say an integer a divides an integer b (written "a | b") if there exists an integer c such that b = ac. When a | b we say that a is a factor of b, a is a divisor of b, or b is a multiple of a.


Example. 2 | 10 since 10 = 2·5 . The integer 10 is a multiple of 2.


Note the following: 3 divides 0 and, in general, a | 0 for all a ε I . Why? It follows as a direct consequence of the above definition since 0 = a·0 . This is a case of a result that would not be expected from the general concept of b as being a multiple of a, but which follows as a consequence of the axiomatic style definition.

 

Theorem 1. If a | b and a | c then a | (bx + cy) for all integers x,y.



Prime number. An integer p which is not 0 or +1 and is divisible by no integers except +1 and +p.



Common divisor of two or more quantities. A quantity which is a factor of each of the quantities. A common divisor of 10, 15, and 75 is 5; a common divisor of x2 - y2 and x2 - 2xy + y2 is x - y , since x2 - y2 = (x - y)(x + y) and x2 - 2xy + y2 = (x - y)2.

Syn. common factor, greatest common measure.



Greatest common divisor (g.c.d.) of two or more quantities. A common divisor that is divisible by all other common divisors. For positive integers, the greatest common divisor is the largest of all common divisors e.g. the common divisors of 30 and 42 are 2, 3, and 6, the largest being the greatest common divisor 6. If we consider negative integers the common divisors of 24 and 60 are ole.gif 1, ole1.gif 2, ole2.gif 3, ole3.gif 4, ole4.gif 6, and ole5.gif 12. and the greatest common divisors are ole6.gif 12. Syn. greatest common factor, greatest common measure.


The greatest common divisor of a and b is denoted by (a,b).




Common multiple of two or more quantities. A quantity which is a multiple of each of two or more given quantities. The number 6 is a common multiple of 2 and 3. x2 - 1 is a common multiple of x - 1 and x + 1.





Least common multiple (l.c.m.) of two or more quantities. The least quantity that is exactly divisible by each of the given quantities; 12 is the l.c.m. of 2, 3, 4, and 6. The l.c.m. of a set of algebraic quantities is the product of all their distinct prime factors, each taken the greatest number of times it occurs in any one of the quantities; the l.c.m. of x2 - 1 and x2 - 2x + 1 is (x - 1)2(x + 1) .


Tech. The l.c.m. of a set of quantities is a common multiple of the quantities which divides every common multiple of them.

 



Division Algorithm. For any integer a and any positive integer b, there exist unique integers q and r such that


                                                a = bq + r,       0 ole7.gif r < b


The integer a is the dividend, b is the divisor, q is the quotient and r is the remainder. [Note. This theorem could be stated differently as “the quotient a/b equals q plus a remainder of r” – which explains the terminology.] For polynomials, the division algorithm states that, for any polynomial f and any non-constant polynomial g, there exist unique polynomials q and r such


                                                 ole8.gif


where either r = 0 or the degree of r is less than the degree of g. The polynomials f, g, q, and r are the dividend, divisor, quotient, and remainder.




Euclid’s algorithm. A method of finding the greatest common divisor (g.c.d.) of two numbers – one number is divided by the other, then the second by the remainder, the first remainder by the second remainder, the second by the third, etc. When exact division is finally reached, the last divisor is the greatest common divisor of the given numbers (integers). In algebra, the same process can be applied to polynomials. E.g., to find the greatest common divisor of 12 and 20, we have 20 ole9.gif 12 is 1 with remainder 8; 12 ole10.gif 8 is 1 with remainder 4; and 8 ole11.gif 4 = 2; hence 4 is the g.c.d.



Theorem 2. Any two integers a ≠ 0 and b ≠ 0 have a positive greatest common divisor (g.c.d.) which can be expressed as a “linear combination” of a and b in the form d = au + bv for integers u and v.


Theorem 3. If p is a prime, then p | ab implies p | a or p | b.


Theorem 4. If p is a prime and if p is a divisor of the product a∙b∙c∙ .... ∙t of n integers, then p is a divisor of at least one of these integers.



Relatively prime integers. Two integers a and b are said to be relatively prime if

(a,b) = 1.



  

The unique factorization Theorem. Every integer a > 1 has a unique factorization, except for order, into a product of primes


                                     ole12.gif





References.

1. James/James. Mathematics Dictionary.



More from SolitaryRoad.com:

The Way of Truth and Life

God's message to the world

Jesus Christ and His Teachings

Words of Wisdom

Way of enlightenment, wisdom, and understanding

Way of true Christianity

America, a corrupt, depraved, shameless country

On integrity and the lack of it

The test of a person's Christianity is what he is

Who will go to heaven?

The superior person

On faith and works

Ninety five percent of the problems that most people have come from personal foolishness

Liberalism, socialism and the modern welfare state

The desire to harm, a motivation for conduct

The teaching is:

On modern intellectualism

On Homosexuality

On Self-sufficient Country Living, Homesteading

Principles for Living Life

Topically Arranged Proverbs, Precepts, Quotations. Common Sayings. Poor Richard's Almanac.

America has lost her way

The really big sins

Theory on the Formation of Character

Moral Perversion

You are what you eat

People are like radio tuners --- they pick out and listen to one wavelength and ignore the rest

Cause of Character Traits --- According to Aristotle

These things go together

Television

We are what we eat --- living under the discipline of a diet

Avoiding problems and trouble in life

Role of habit in formation of character

The True Christian

What is true Christianity?

Personal attributes of the true Christian

What determines a person's character?

Love of God and love of virtue are closely united

Walking a solitary road

Intellectual disparities among people and the power in good habits

Tools of Satan. Tactics and Tricks used by the Devil.

On responding to wrongs

Real Christian Faith

The Natural Way -- The Unnatural Way

Wisdom, Reason and Virtue are closely related

Knowledge is one thing, wisdom is another

My views on Christianity in America

The most important thing in life is understanding

Sizing up people

We are all examples --- for good or for bad

Television --- spiritual poison

The Prime Mover that decides "What We Are"

Where do our outlooks, attitudes and values come from?

Sin is serious business. The punishment for it is real. Hell is real.

Self-imposed discipline and regimentation

Achieving happiness in life --- a matter of the right strategies

Self-discipline

Self-control, self-restraint, self-discipline basic to so much in life

We are our habits

What creates moral character?


[ Home ] [ Up ] [ Info ] [ Mail ]