MA330Sathaye Better Division AlgorithmGiven below is a convenient version of the well known Euclidean algorithm, which is easy to useand gives several useful conclusions fast.This version is from a Mathematical section of a work on Astronomy by an astronomer¯Aryabhat.afrom India in the fifth century. The suggested working presented here differs from the traditionalcommentaries, but seems consistent with the original (very cryptic) description.Let us say we have to calculate the gcd of the numbers a = 414 and b = 189. We also wish to solvethe equation ax − by = s in integers.The work consists of three steps represented by the three matrices given below. I will explain thework further down.A =414 ∗189 236 59 40 ∗B =11 4145 189 21 36 50 9 41 0C =46 11 414 ∗21 5 189 24 1 36 51 0 9 40 1 0 ∗Here are the details:1. The matrix A represents the basic algorithm. You start with the two numbers on top. Call thema, b in order. Divide the upper number by the one on the bottom and write the remainderbelow. The quotient is recorded to the right. You continue until you get a 0. Let n be thenumber of entries in the first column - including the zero entry.2. The matrix B is obtained by starting with a 1 at the bottom of the first column (added into Aat left). You write a 0 just above.To get a number just above the last one written down you multiply it by the correspondingnumber in the third column and add the number just below it. Mathematically, this meansBi,1= Bi+1,1Bi+1,3+ Bi+2,1.This matrix shall help in writing the gcd as a combination of the chosen numbers.3. The matrix C is obtained by a process similar to the one in B, except you start with 0 at thebottom of the new first column and 1 just above. The rule for the calculation is just as above:Ci,1= Ci+1,1Ci+1,4+ Ci+2,1.4. Our matrix has n rows. (In the example, n = 5).Then the gcd is An−1,1= Bn−1,2= Cn−1,3. Call it d. It is 9 for our example.5. To get the expression of the gcd as a combination of the starting numbers, the formula is(C1,1t + C1,2)b − (C2,1t + C2,2)a = ±d.Where a, b are the original numbers, namely C1,3, C2,3respectively and t is an arbitrary integer.This is easier to remember if you know determinants:1(C1,1t + C1,2) a(C2,1t + C2,2) b= ±d.Rule for the sign: The sign is chosen to be plus if n is odd and minus otherwise!Mathematically, you could write (−1)n+1d. You could also figure it out by simply testing.In our example, this becomes(46t + 11)189 − (21t + 5)414 = 9.We have the plus sign, since our n = 5 which is odd.6. The first two numbers in the first column of C are also useful. They give a/d = 414/9 = 46 andb/d = 189/9 = 21 respectively. Thus the lcm(a, b) = [a, b] is given by (ab)/d = 46 · 21 · 9.7. To get any desired number s expressed as a combination of a, b we can proceed as follows:Method 1 Note that it is necessary that s is a multiple of d. If this is not true, then s cannotbe written as a combination of a, b.Write s = md for an integer m.Then use the above expression for d and multiply it by m to get a general solution.Choose a convenient t as desired.Thus, we get:(46t + 11m)189 − (21t + 5m)414 = 9m.Note: We did not write tm but used just a t again, since it is meant to be an arbitrary integer!Thus for s = 54 we get m = 6 and(46t + 66)189 − (21t + 30m)414 = 54.For convenience, we could take t = −1 to yield (20)189 − (9)414 = 54.Method 2 Build a new version of B by creating a new first column in the following way. Startwith any desired level and create a starting pair at that level and lift the numbers by the ruleused for B.For instance, for s = 54, we start by writing 2, −1 next to 36, 9 respectively, so that 54 =(2)9 − (−1)36. Thus we have a starting version of a new B which we call B∗.B∗=414189 22 36 5−1 9 40Then lifting process goes as follows:2B∗=414189 22 36 5−1 9 40→ B∗∗=4149 189 22 36 5−1 9 40→ B∗∗∗=20 4149 189 22 36 5−1 9 40Note that this does not reach the bottom and it is not necessary (though we could fill it, if wewanted it!)Then (20)189 − (9)414 = 54 as desired. This will always work, except we may need to multiplyby −1, if the newly created column has odd number of entries.You should practice with other examples given below.8. In the traditional Indian style, I will refrain from giving the proof.However, in the modern age, you must try to make up the proof. Think about what it could be.Having studied the process of solving ax-by=c you should solve the following problems. First fiveare routine problems, while the last two illustrate the original applications.1. Find a number (and all such positive numbers) which is:• divisible by 45 after subtracting 7 from it.• and also divisible by 29 after adding 2 to itDo determine the smallest positive such number.Hint: You need to solve the equation 29b − 45a = 9. Do analyze how this will helpyou answer the question.2. Find a number divisible by 3 after subtracting 5 and divisible by 31 after subtracting 7. ( A smallvariation from Bh¯askara I of 600 A.D.)Do determine the smallest positive such number.3. Find a number which has remainder 5 when divided by 8, remainder 4 when divide by 9 andremainder 1 when divided by 7.Do determine the smallest positive such number.( A small variation from Bh¯askara I of 600 A.D.)4. Find a number which leaves a remainder 1 when divided by 2, 3, 4, 5 or 6 but is divisible by 7.Do determine the smallest positive such number.(¯Aryabhat.¯iya bh¯as.ya 600 A.D. , Ibn-al-Haitam 1000 A.D., Fibonacci 1202 A.D.)5. Suppose that if we count a set of objects by threes, then 2 are left; if we count by fives, then 3are left and if we count by sevens, then 2 are left. How many objects are there? (It is impliedthat you should find the smallest such positive number. (Sunzi fifth century - the origin of theterm “Chinese Remainder Theorem!”)36. The residue of the revolutions of Saturn is 24. Find the day number. (laghubh¯askar¯iya 600 A.D.)Explanation: Let x be the day number or the number of days elapsed since the beginning of theyuga (actually the current Kali yuga). Yuga is a long period