1 x 8 + 1 = 9
12 x 8 + 2 = 98
123 x 8 + 3 = 987
1234 x 8 + 4 = 9876
12345 x 8 + 5 = 98765
123456 x 8 + 6 = 987654
1234567 x 8 + 7 = 9876543
12345678 x 8 + 8 = 98765432
123456789 x 8 + 9 = 987654321
1 x 9 + 2 = 11
12 x 9 + 3 = 111
123 x 9 + 4 = 1111
1234 x 9 + 5 = 11111
12345 x 9 + 6 = 111111
123456 x 9 + 7 = 1111111
1234567 x 9 + 8 = 11111111
12345678 x 9 + 9 = 111111111
123456789 x 9 +10= 1111111111
9 x 9 + 7 = 88
98 x 9 + 6 = 888
987 x 9 + 5 = 8888
9876 x 9 + 4 = 88888
98765 x 9 + 3 = 888888
987654 x 9 + 2 = 8888888
9876543 x 9 + 1 = 88888888
98765432 x 9 + 0 = 888888888
Brilliant, isn't it?
And finally, take a look at this symmetry:
1 x 1 = 1
11 x 11 = 121
111 x 111 = 12321
1111 x 1111 = 1234321
11111 x 11111 = 123454321
111111 x 111111 = 12345654321
1111111 x 1111111 = 1234567654321
11111111 x 11111111 = 123456787654321
111111111 x 111111111=12345678987654321
Monday, March 30, 2009
Take 5 - The Beauty Of Numbers.
Sunday, March 29, 2009
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.
Euclidean Algorithm
Theorem 3
Given integers a and b,not both of which are zero,there exist integers x and y such that gcd(a,b) = ax+by.
Theorem 4
If gcd (a,b) = d,then .
Proof – Since gcd(a,b) is equal to d,then from theorem 3,exist x and y such that d = ax + by. Divide both sides by d to obtain 1=(a/d)x+(b/d)y. Because d is the common divisor of a and b,then it is sure that a/d and b/d is integers. Thus,
Euclidean Algorithm
The Euclidean algorithm, also called Euclid's algorithm, is an algorithm for finding the greatest common divisor of two numbers a and b . The algorithm can also be defined for more general rings than just the integers. There are even principal rings which are not Euclidean but where the equivalent of the Euclidean algorithm can be defined. The algorithm for rational numbers was given in Book VII of Euclid's Elements. The algorithm for reals appeared in Book X, making it the earliest example of an integer relation algorithm (Ferguson et al. 1999).
Example 1 - Find the gcd of 754 and 56
765 - (13) * (56) = 37
56 - (1) * (37) = 19
37 - (1) * (19) = 18
19 - (1) * (18) = 1
18 - (18) * (1) = 0
So gcd of 765 and 56 is 1
Example 2 - Find the gcd of 342 and 76
342 - (4) * (76) = 38
76 - (2) * (38) = 0
So gcd of 342 and 76 is 38
Diophantine Equation
Introduction
In mathematics, a Diophantine equation is an indeterminate polynomial equation that allows the variables to be integers only. Diophantine problems have fewer equations than unknown variables and involve finding integers that work correctly for all equations. In more technical language, they define an algebraic curve, algebraic surface or more general object, and ask about the lattice points on it.
While individual equations present a kind of puzzle and have been considered throughout history, the formulation of general theories of Diophantine equations (beyond the theory of quadratic forms) was an achievement of the twentieth century.
Linear Diophantine equations take the form ax + by = c. If c is the greatest common divisor of a and b then this is Bézout's identity, and the equation has infinitely many solutions. These can be found by applying the extended Euclidean algorithm. It follows that there are also infinitely many solutions if c is a multiple of the greatest common divisor of a and b. If c is not a multiple of the greatest common divisor of a and b, then the Diophantine equation ax + by = c has no solutions.
Conditions for Diophantine equation to have solution.
i. The greatest common divisor of a and b divide c.
ii. No three of a,b,c,d have a common factor 1.
iii. Intergers (x,y) is a solution of the linear Diophantine equation ax+by=c if and only if the (x,y) is a lattice point in the plane that lies in line ax+by=c.
Method to find the solution of ax+by=c .
i. Given an equation of ax+by=c. First,find the greatest common divisor of a and b using Euclidean algorithm.
Example : Determine all solution in intergers of
24x+138y=18
The computation is as follows :
138 = 5•24 + 18
24 = 1•18 + 6
18 = 3•6 + 0
So,the gcd(24,138)=d=6.
ii. Check whether gdc(a,b) divide c or not. With regards to example above,since 618,hence the equation 24x+138y=18 has a solution.
iii. Obtain c in linear combination of a and b.
To obtain 6 in linear combination of 24 and 138,we work backward through the previous computation as follows :
138 = 5•24 + 18 18 = 138 - 5•4
24 = 1•18 + 6 6 = 24 - 1•18
18 = 3•6 + 0
6 = 24 - 1•18
= 24 – 1 (138 - 5•4)
= 24 - 1•138 + 5•4
= 6•24 - 1•138
= 6•24 + (-1)•138
Hence,6 in linear combination of 24 and 138 is 6= 6•24 + (-1)•138.
iv. Continuing from example above,upon multiplying the 6= 6•24 + (-1)•138 by 3,we obtain
18 = 18•24 + (-3)•138
Thus, and
.
Other solution are obtained by using formulae and
The other solution are given by x = 18 + 23t and y = -3 – 4t for .....and so on.
Division Algorithm
Theorem 1 (Division Algorithm)
Given integers a and b,with b>0,there exist unique integers q and r satisfying a = qb + r. The integers q and r are called,respectively,the quotient and remainder in the division of a by b.
Example,
a = 8 , b = 3, q = 2, r = 2
8 = 2 x 3 + 2 ( a = qb + r)
Definition.
An integer b is said to be divisible by an integer , in symbols a|b, if there exist some integer c such that b = ac.
3|6 indicate 3 divide 6 , which exist c=2.
Theorem 2
For integers a , b , c , the following hold :-
1. a|0 , 1|a , a|a
2. a|1 iff
3. if a|b and c|d , then ac|bd
4. if a|b and b|c , then a|c
5. a|b and b|a iff
6. if a|b and b|c , then a|(bx+cy) for some integers x and y.
Proof
3. since a|b and c|d,then exist e and f such that b = ac and d = cf. Because bd = ae•cf = ac•ef , thus ac|bd.
4. Since a|b and b|c,then exist e and f such that b = ae and c = bf. Because c = bf =aef,thus a|c.
5. Since a|b and a|c,then exist e and f such that b = ae and c = af. Hence,
bx + cy = aex + afy = a(ex+fy). Let (ex+fy) = w. Hence, bx + cy = aw. Thus,a|(bx+cy) for some x and y.
Definition
Let a anb b be given integers,with at least one of them different from zero. The greatest common divisor (gcd) of a and b,denoted by gcd(a,b) is positive integer d satisfying the following;
a) d|a and d|b (d is a common divisor)
b) if c|a and c|b,then c|d.
Introduction To Number Theory
Divisibility Theory in the Integers
Number Theory is a study of numbers,which involve integers only such as the numbers -2,-1,0,1,2,3,4 and so on. This numbers is called real numbers.
Another kind of numbers are as follows:
Numbers such as and so on are known as fraction.
Numbers such as are known as complex number.
Well-ordering principle.
Every non-empty set, S of non-negative integers contains a least element ; that is,there is some integer a in S such that for all b’s belonging to S.
An example to illustrate this principle,
S = { 1 , 2 , 3 , 5 , 7 , 9 , 12 }
