Information Processing : Euclidâ€™s game

**Euclidâ€™s
game**

Ammu and Balu are playing a game. Each one can choose
any number and they write it down on a piece of paper. If Ammu picks up the number
greater than what Balu picked up, then Ammu will find the difference of the two
numbers. That difference will be shown to Balu. Now Balu takes the chance to find
the difference between the number what he has and the number shown to him by Ammu.
They will continue the process until the difference and the numbers they have become
equal. Finally, the person who gets the number equal to the difference wins the
game Let us see how it works

Suppose Ammu picked the number 34 and Balu picked
the number 19. Ammu first finds the difference between 34 and 19 which gives 15.
She shows the difference to Balu. Now Balu has 19 and she has 15, the difference
is 4. He shows to Ammu and so on. (the bigger number should be kept first to find
the difference). So Ammu wins.

Now suppose they start with Ammu (24, 18).

It goes: (24, 18) â†’ (18, 6) * Ammu* â†’ (12, 6)

If they start
with Ammu (18, 6), we get (18, 6) â†’ (12, 6) â†’ (6, 6) Balu wins!

Play the game with your friends and see for what
pairs of numbers the first player (Ammu ) wins, and when the second player wins.

Now we can notice something interesting! Begin with
any pair of numbers. Can you say anything about the pair of numbers. Remember that
we stop the process when both the numbers are same. It is the Highest Common Factor
(HCF) of the two numbers we started with. So what we have seen here is an iterative
process which leads us to the HCF of two given numbers. The HCF of *a* and
*b* (here *a*>*b*) is the same as for *a* and *a-b.*

** **

__Example 1__

Find the HCF of two numbers 16 and 28.

*Solution*

**Now the HCF of 16, 28 **

16 = 2 Ã— 2 Ã— 2 Ã— 2

28 = 2 Ã— 2 Ã— 7

HCF of (16, 28) = 2 Ã— 2 = 4

**Now the HCF of (16 , 28-16)**

16 = 2 Ã— 2 Ã— 2 Ã— 2

12 = 2 Ã— 2 Ã— 3

HCF of (16, 12) = 2 Ã— 2 = 4

Therefore HCF of (16, 28) = HCF of (16, 28-16).

Hence, HCF of two numbers a and b, a > b, is
same as the HCF of a and a â€“ b.

** **

**Euclidean algorithm**

Let us take a number 12.

If we divide 12 by 7 then, we get
quotient=1, remainder=5 and 12 can be written as 12 = (1 Ã— 7) + 5.

If we divide 12 by 2 then, we get
quotient=6, remainder=0 and 12 can be written as 12 = (2 Ã— 6) + 0.

From this, we observe that, if a number
â€˜*a*â€™ is divided by some number â€˜*b*â€™ then we get the quotient â€˜*q*â€™
and remainder â€˜*r*â€™, and â€˜*a*â€™ can be written in a unique way as *a
= (b *Ã—* q) + r*. That is, Dividend = (Divisor Ã— Quotient) + Remainder.
This is called the Euclidean algorithm.

Tags : Information Processing | Term 3 Chapter 5 | 6th Maths , 6th Maths : Term 3 Unit 5 : Information Processing

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

6th Maths : Term 3 Unit 5 : Information Processing : Euclidâ€™s game | Information Processing | Term 3 Chapter 5 | 6th Maths

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright Â© 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.