1
1 Euclidean Algorithm
1.Learns Euclidean Algorithm which is anefficient process for finding greatest common divisor.
2.Familiarizes the Diophantine equations.Studies theorems and solve problems based on Euclidean algorithm and Diophantine equations
Lemma: If , then
Proof
If , then the relations and together imply that
, or .
Thus, d is a common divisor of both b and r.
On the other hand, if c is an arbitrary common divisor of b and r, then
,
and hence . This makes c a common divisor of a and b, so that . It now follows from the definition of that . Hence we conclude that.
Euclidean Algorithm
The Euclidean Algorithm may be described as follows.
Let a and b be two integers whose greatest common divisor is desired. Because , there is no harm in assuming that .
The first step is to apply the Division Algorithm to a and b to get
If it happens that , then and . When , divide b by to produce integers and satisfying
If , then we stop; otherwise, proceed as before to obtain
This division process continues until some zero remainder appears, say, at the th stage where is divided by (a zero remainder occurs sooner or later because the decreasing sequence cannot contain more that b integers).
The result is the following system of equations:
…(1)
now we prove , the last nonzero remainder, is equal to.
.
Using the result of the lemma above, we simply work down the displayed system (1) of equations, obtaining
as claimed.
We know can be expressed in the form, to determine the integers x and y. we use the Euclidean Algorithm. Starting with the next-to-last equation arising from the algorithm, we write
Now solve the preceding equation in the algorithm for and substitute to obtain
.
This represents as a linear combination of and . Continuing backward through the system of equations, we successively eliminate the remainders until a stage is reached where is expressed as a linear combination of a and b.
Example1 Using Euclidean Algorithm calculate. Also represent the greatest common divisor as a linear combination of 12378 and 3054.
Solution
By applying Division Algorithm we make the equations
.
The last nonzero remainder appearing in these equations, namely, the integer 6, is the greatest common divisor of 12378 and :
To represent 6 as a linear combination of the integers 12378 and 3054, we start with the next-to-last of the displayed equations and successively eliminate the remainders and162:
Thus, we have
where and.
Note 1 : the above is not the only way to express the integer 6 as a linear combination of 12378 and 3054; among other possibilities, we could add and subtract to get
Note 2 :The number of steps required in the Euclidean Algorithm is at most five times the number of digits in the smallest integer.
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
A Procedure to Reduce the Number of Steps
The number of steps in the Euclidean Algorithm can be reduced by selecting remainders such that
that is, by working with least absolute remainders in the divisions. If we use this procedure, finding can be simplified as below:
As the last nonzero remainder is , the scheme produces “greatest common divisor”as Hence the greatest common divisor is 6. (Note that this scheme produces the negative of the value of the greatest common divisor of two integers.)
Theorem 1 If , then
Proof
For a and b, the successive application of Euclidean Algorithm produces the following system of equations:
…(1)
If each of the equations appearing in the system (1) is multiplied by k, we obtain
But this is clearly the Euclidean Algorithm applied to the integers and, so that their greatest common divisor is the last nonzero remainder ; that is
.
Example2Assuming that prove that or 2.
Solution
Let Then
and
Hence
and
That is
and
Thus
Since
the above implies
Hence
or
Corollary For any integer,.
Proof
The case of is treated in the previous theorem.
When the result is obvious. Hence it suffices to consider the case in which the case in which.
When ,
and
, by
Theorem 1.
Definition An integer is said to be a common multiple of two nonzero integers and whenever and
Examples
- products and are both common multiples of and .
- By the Well-Ordering Principle of natural numbers, the set of all positive common multiples of and must contain a smallest integer. This leads to the following 0 is a common multiple of and .
The definition.
Definition The least common multiple of two nonzero integers and , denoted by is the positive integer satisfying the following:
(a) and .
(b) If and , with , then .
Example3The positive common multiples of the integers and 30 are 60, 120, 180, … ; hence 1cm .
Note:Given nonzero integers a and b, always exist and .
Example 4 Find least number which when divided by 9 gives the remainder 8, when divided by 8 gives the remainder 7, when divided by 7 gives the remainder 6, … , when divided by 3 gives the remainder 2, when divided by 2 gives the remainder 1.
Solution
We find the least common multiple of the numbers 9, 8, 7, 6, 5, 4, 3 and 2. It is 15120. Now this number is divisible by 9, 8, 7, 6, 5, 4, 3 and 2. Subtracting 1 from 15120 would give a number that leaves the remainder 8, 7, 6, 5, 4, 2 and 1, respectively, when divided by 9, 8, 7, 6, 5, 4, 3 and 2. Hence the required number is
Theorem 2 For positive integers a and b
.
Proof
Let
and write
for integers r and s.
If,
then.
Hence is a (positive) common multiple of a and b.
Now let be any positive integer that is a common multiple of and ; say, . Since is the gcd of and , there exist integers x and y satisfying
.
Hence
This equation states that
,
allowing us to conclude that
.
Thus, by the Definition of least common multiple, ; that is,
.
Hence
Example5 Find .
Solution
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
2.Diophantine Equation
The term Diophantine equation is applied to any equation in one or more unknowns that is to be solved in the integers. The simplest type of Diophantine equation that we shall consider is the linear Diophantine equation in two unknowns:
where are given integers and are not both zero. A solution of this equation is a pair of integers that, when substituted into the equation, satisfy it; that is, we obtain .
A given linear Diophantine equation can have a number of solutions, as the following example shows.
Example 1(Example of a linear Diophantine equation that have a number of solutions) Find some solutions of
Solution
Some set of solutions are and as
There are linear Diophantine equations that have no solution, as the following example shows.
Example 2 (Example of a linear Diophantine equation that has no solution) Find the solution, if there is any, of
Solution
There is no integer solution to the equation
because the left-hand side is an even integer whatever the choice of x and y, whereas the right hand side is not.
Example 3Solve the following epigram problem.
Diophantus’s boyhood lasted of his life; his beard grew after more; after more he married and his son was born 5 years later; the son lived to half his father’s age and the father died 4 years after his son. Then at what age Diophantus died?
Solution
If x was the age at which Diophantus died, the given data leads to the equation
with solution.
Theorem 1 The linear Diophantine equation has a solution if and only if where
Proof
We note that if then there are integers r and s for which and .
If a solution of exists, so that for suitable and, then
which simply says that.
Conversely, assume that, say. Since there are integers and such that
.
When this relation is multiplied by t, we obtain
.
Hence, the Diophantine equation has
and
as a particular solution. .
Theorem 2 The linear Diophantine equation has a solution if and only if where If is any particular solution of this equation, then all other solutions are given by
where is any arbitrary integer.
Proof
The first part is the content of Theorem 1. To establish the second assertion of the theorem, let us suppose that a solution, of the given equation is known. If is any other solution, then
which is equivalent to
.…(1)
As then so that and are relatively prime. Hence there exist relatively prime integers r and s such that
and
Hence
Substituting these values into Eq.(1) and canceling the common factor d, we find that
.
ie with.
or, in other words, for some integer t.
Substituting, we obtain
This leads us to the formulas
It is easy to see that these values satisfy the Diophantine equation, regardless of the choice of the integer t; for
.
Thus there are an infinite number of solutions of the given equation, one for each value of t.
Example 4 Find the complete solution of the linear Diophantine equation
.
Also find solutions in positive integers, if they exist.
Solution
Applying the Euclidean’s Algorithm to the evaluation of we find that
Hence. Because a solution to this equation exists. To obtain the integer 4 as a linear combination of 172 and 20, we work backward through the previous calculations, as follows:
Upon multiplying this relation by 250, we arrive at
so that and
provide one solution to the Diophantine equation in question. Since all other solutions are expressed by
for some integer t.
Now we try to find the solutions in the positive integers, if any happen to exist. For this, t must be chosen to satisfy simultaneously the inequalities
and
or the inequalities
and or
Because t must be an integer, we are forced to conclude that . Thus the given Diophantine equation has a unique positive solution corresponding to the value
When the coefficients are relatively prime integers, Theorem 2 provides the following result:
Corollary If and if is a particular solution of the linear Diophantine equation then all solutions are given by
for integral values of t.
Example 5 The equation has as one solution. Since this with corollary gives a complete solution
for arbitrary t.
Example 6 A customer bought a dozen pieces of fruit, apples and oranges, for . If an apple costs 3 rupees more than an orange and more apples than oranges were purchased, how many pieces of each kind were bought?
Solution
Let x be the number of apples and y be the number of oranges purchased; in addition, let z represent the cost (in rupees) of an orange. Then the conditions of the problem lead to
or equivalently we obtain
.or
, since
This simplifies to
Now the problem is to find integers x and z satisfying the Diophantine equation
… (1)
Since is a divisor of 44, by Theorem 2, there is solution to Eq. (1). Upon multiplying the relation
by 44 to get
it follows that
serves as one solution. By Corollary, all other solutions of Eq. (1) are of the form
,
where t is an integer.
Not all of the choices for t furnish solutions to the original problem. Only values of t that ensure should be considered. This requires obtaining those values of t such that
Now, implies that whereas gives The only integral values of t to satisfy both inequalities areand Thus there are two possible purchases: a dozen apples costing Rs.11 a piece (the case where ) , or 8 apples at Rs.12 each and 4 oranges at Rs.9 each (the case where ).
Assignments
1. Find and
.
2 . Find 1cm (143, 227), 1cm (306, 657), and 1cm (272, 1479)
.
3. In Exercises below, determine all solutions in the integers of the given Diophantine equation
(a)(b) (c).
4.A certain number of sixes and nines is added to give a sum of 126; if the number of sixes and nines is interchanged, the new sum is 114. How many of each were there originally?
5.(The problem of the ‘Hundred fowls’) If a cock is worth 5 coins, a hen 3 coins, and three chicks together 1 coin, how many cocks, hens, and chicks, totaling 100, can be bought for 100 coins?
Glossary
Euclidean Algorithm: Euclidean Algorithm is a systematic way for finding the g.c.d. of two composite numbers .
Diophantine Equation: An equation in one or more unknowns which is to be solved in the integers.
Least common multiple: the least common multiple of two non zero integers a and b is the positive integer m satisfying
(1) a|m and b|m
(2) if a|c and b|c with c>0 then
Quiz
1. What is the value of gcd(150,200)lcm(150,200).
(a) 150 (b) 200 (c)350 (d)30,000
2. Which of the following is not a Diophantine equation?
(a) (b) (c) (d)
3. Which of the following is a linear Diophantine equation?
(a) (b) (c)
(d)
4. Let gcd(a,b)=1 then which of the following is false?
(a) gcd(a+b,a-b)=1 or 2 (b) gcd(a+b,)=1 or 2 (c) gcd(a+b,1 or 3
(d) none of these
Answers
1. 30,000 2, 3.4.none of these
FAQ
1. Find the integers satisfying
2. Prove that is divisible by 2 for every integer n
.
3. what is the geometrical interpretation of linear Diophantine equation ?
4.Does all Diophantine equation has solution?
Answers
- Put .
Because,
first final integers u and v for which
2 . and either or is even
3 . Geometrically a linear Diophantine equation represents a line in the plane and a solution of the equation is a lattice point in the plane that satisfies it
4. No. for example consider a Diophantine equation y2=x3+k, it has no solution if k is of the form k=(4n-1)3-4m2 where m,n are integers such that no prime p congruent to
-1(mod 4) divides m
SUMMARY
In this module first we discussed the Euclidian algorithm which is a repeated application of division algorithm given in the seventh book of Euclid ‘s “ELEMENTS”. we discussed parallel concepts greatest common divisor and least common multiple of two integers and the relationships between them.Then we focused on the concept of Diophantine equations and its applications to solve problems where we used Euclidian algorithm.
1