AdvertisementYour brand could be hereYour brand hereOn every Darslab page · students, parents and teachersinfo@darslab.comAsk for pricesPricesinfo@darslab.com
☰ Contents · Computing

Local and global variables, the GCD (EKUB) function

Lessons 49–50 · 2 lessons · M. R. Fayziyeva, D. M. Sayfurov, N. S. Xaytullayeva. Informatics and Information Technologies, Grade 9. “Nashriyot uyi Tasvir”, Tashkent, 2020
50

Practical lesson: functions and Euclid’s algorithm

Textbook: pp. 98–99
GoalIn the practical lesson, finds the greatest common divisor (EKUB) of two numbers with the Euclidean algorithm, writes it as a function, and uses it to reduce a fraction and to find the least common multiple (EKUK).
New words
EKUB: the greatest common divisor of two numbers (gcd) · EKUBEuclidean algorithm: repeat (a, b) → (b, a % b) until b is 0 · Yevklid algoritmiEKUK: the least common multiple, which equals a * b // EKUB(a, b) · EKUKreducing a fraction: dividing numerator and denominator by their EKUB · kasrni qisqartirish
Explanation

Finding the greatest common divisor (EKUB) of two numbers by splitting them into prime factors is not handy for a computer; the Euclidean algorithm is short and fast. Its idea: divide a by b and take the remainder, then take (b, remainder) in place of (a, b); repeat until b equals zero, and at the end a is the EKUB. For example (84, 36) → (36, 12) → (12, 0), so EKUB = 12. In Python this is a loop of two lines (code below) – both the swapping and the remainder are done in one line. Once the EKUB is found, reducing a fraction (dividing both parts by the EKUB) and finding EKUK = a * b // EKUB is very easy. The algorithm always stops, because the remainder gets smaller each time and finally reaches zero.

Python
1while b != 0:
2    a, b = b, a % b
💡 Where will I use this?
In real life

A class wanted to cover a rectangular notice board, 48 cm by 72 cm, with identical square pictures and no gaps. The largest possible side is the greatest common divisor of 48 and 72, which is 24 cm, so 6 pictures were needed.

Who uses it

Mathematicians, programmers and accountants simplify fractions to keep sums short and exact.

Try it today

Find the greatest common divisor of two numbers, such as 36 and 60, on paper by subtraction. Use it to simplify a fraction.

Worked examples
Python
1def ekub(a, b):
2    while b != 0:
3        a, b = b, a % b
4    return a
5print(ekub(84, 36))
Output
12
An EKUB function – code above. ekub(84, 36) = 12.
Python
1def ekub(a, b):
2    while b != 0:
3        a, b = b, a % b
4    return a
5g = ekub(18, 24)
6print(18 // g, 24 // g)
7
8def ekub(a, b):
9    while b != 0:
10        a, b = b, a % b
11    return a
12print(12 * 18 // ekub(12, 18))
Output
3 4
36
Reducing a fraction – the first program above. The fraction 18/24 becomes 3/4 (EKUB = 6). EKUK – the second program above. The EKUK of 12 and 18 is 36.
Class activity

“Remainder chain”: pairs choose two numbers, write the chain (a, b) → (b, a % b) in the notebook and find the EKUB; then they check it in a program.

Practice
1
Find the EKUB of 48 and 18 (with the Euclidean algorithm).
2
Starting from (84, 36), write the chain: show the pair (a, b) at each step.
3
Reducing a fraction: find the numerator and the denominator of the fraction 45/60 reduced.
4
Why does the Euclidean algorithm always stop?
Story of the Week · The Khwarizmi WayGiving part of the profitClose the week: all of this week’s subjects in one storyRead →