Application Of Euclidean Algorithm

Definition

Two integers a and b,not both of which are zero,are said to be relatively prime whenever gcd(a,b)=1.

Theorem 5 – Let a and b be integers,not both zero. Then a and b is relatively prime if and only if there exist integers x and y such that 1 = ax +by. (in other words,gcd(a,b)=1)

Theorem 6 – If gcd (a,b) = d,then
Theorem 7 – If a|c and b|c,with gcd (a,b)=1,then a|c.

Theorem 8 – If ab|c,with gcd (a,b)=1,then a|c.

Theorem 9 – Let a,b be integers,not both are zero. For a positive integer d,d=gcd(a,b) if and only if
a) d|a and d|b
b) whenever c|a and c|b,then c|d

Theorem 10 – If a=bq+r,then gcd(a,b)=gcd(b,r)

Theorem 11 – If k>0,then gcd (ka,kb) = k•gcd(a,b)

Theorem 12 – The linear Diophantine equation ax+by=c has a solution if and only if dc where d=gcd(a,b). If x0 and y0 is any particular solution of this equation,then all other solution are given by x = x0 + (b/d)t and y = y0 – (a/d)t where t is any integer.

Theorem 13 – If gcd(a,b)=1 and if x0 and y0 is a particular solution of the linear Diophantine equation ax+by=c ,then all solution are given by x= x0 + bt and y= y0 – at for any t.

Exercise

a) Given integers a,b,c,and d. Prove that if a|b and a|c,then
# Since ab and ac,then exist d and e such that b=ad and c=ae. Because bc= ad•ae = •de. Thus,

b) Given integers a,b,c,and d. Prove that if a|b and c|d,then ac|bd.
# Since a|b and c|d,then exist e and f such that b=ae and d=cf. Because bd=ae•cf=ac•ef,then ac|bd.

c) If gcd(a,b)=1 and c|a,then gcd(b,c)=1.
# Since gcd (a,b)is equal to 1,then exist x and y such that 1=ax +by and since ca,then exist d such that a=cd. Because 1=ax + by=cdx + by,thus gcd(b,c)=1.

Example Of Problem Which Apply The Use Of Euclidean Algorithm.

Problems
Consider the problem of purchasing RM 510 of travellers cheque using only RM 20 and RM 50. How many each type of cheque should be used.

Let x represent the amount of cheque for RM 50.
Let y represent the amount of cheque for RM 20.

Hence,the equation could be represent as follows;
50x + 20y = 510.

Using Euclidean Algorithm,we evaluate the gcd (50,20)
50 = 2•20 + 10
20 = 2•10 + 0

Since gcd(50,20)=10 and 10|510,the equation has a solution.

To obtain the integer 10 as a linear combination of 20 and 50,we work backward through the previous computations as follows
10 = 50 – 2•20 = 1•50 – 2•20
So 10 = 1•50 + (-2)•20

Upon multiplying this relation by 51,we obtain
510 = 51•50 + (-102)•20.

Thus x0 = 51 and y0=-102 is a solution for 50x + 20y=510.
The other solution is given by the equation x = 51+2t and y = -102 – 5t.
Since x and y are always positive (because it involve money),hence only few value of t is applicable.

51+2t>0 and -102-5t>0
hence,
t>-25.5 and t<-20.4

Hence,overlapped real value of t is -21,-22,-23,-24,-25. Thus the value of x and y which is applicable are ;

When t=-25, x=1 and y=23.
When t=-24, x=3 and y=18.
When t=-23, x=5 and y=13.
When t=-22, x=7 and y=8.
When t=-21, x=9 and y=3.

Myspace Graphics