## Tag Archives: Basic number theory

### Divisibility and the GCD — Pre-RMO, RMO and IITJEE foundation Math

We switch back to basic number theory for the express purpose of Pre-RMO, RMO and IITJEE Foundation Mathematics.

As we have already seen in a previous blog on Pythagorean triples, the notions of divisibility and factorizations are important tools in number theory. In this blog, we will look at these ideas more closely.

Suppose that m and n are integers with $m \neq 0$. We say that m divides n, if n is a multiple of m, that is, if there is an integer k so that $n=mk$. If m divides n, we write m|n. Similarly, if m does not divide n, then we write

$m \not | n$. For example, 3|6 and 12|132 since 6=3.2 and 132=12.11

The divisors of 6 are 1,2,3 and 6. On the other hand, $5 \not | 7$ since no integer multiple of 5 is equal to 7. A number that divides n is called a divisor of n.

If we are given two numbers, we can look for common divisors, that is, numbers that divide both of them. For example, 4 is a common divisor of 12 and 20, since 4|12 and 4|20. Notice that 4 is the largest common divisor of 12 and 20. Similarly, 3 is a common divisor of 18 and 30, but it is not the largest, since 6 is also a common divisor. The largest common divisor of two numbers is an extremely important quantity that will frequently appear during our number theoretic excursions.

The greatest common divisor of two numbers a and b (not both zero) is the largest number that divides both of them. It is denoted by $gcd(a,b)$. If

$gcd(a,b)=1$, we say that a and b are relatively prime or co-prime.

Two examples that we mentioned above are

$gcd(12,20)=4$ and $gcd(18,30)=6$.

Another example is $gcd(225,120)=15$

We can check that this answer is correct by factoring $225=3.3.5.5$ and

$120=2.2.2.3.5$ but, in general, factoring a and b is not an efficient way to compute their GCD or HCF.

The most efficient method known for finding the GCD of two numbers is called the Euclidean algorithm. It consists of doing a sequence of divisions with remainder until the remainder is zero. We will illustrate with an example before describing the general method.

As our example, we will compute the $gcd(36,132)$ The  first step is to divide 132 by 36, which gives a quotient of 3 and a remainder of 24. We write this as

$132=3 \times 36 +24$

The next step is to 36 and divide it by the remainder 24 from the previous step. This gives

$36=1 \times 24 +12$

Next divide 24 by 12, and we find a remainder of 0,

$24=2 \times 12 +0$

The Euclidean algorithm says that when you get a remainder of 0 then the remainder from the previous step is the GCD of the original two numbers. So, in  this case we find that the $gcd(132,36)=12$.

Notice how at each step we replace our old A and B with the numbers B and R and continue the process until we get a remainder of 0. At that point, the remainder R from the previous step is the GCD of our original two numbers.

There is one more practical matter to be mentioned before we undertake a theoretical analysis of the Euclidean algorithm. If we are given A and B, how can we find a quotient Q and the remainder R? Of course, you can always use long division, but that can be time consuming and subject to arithmetic errors if A and B are large. A pleasant alternative is to find a calculator or computer program that will  automatically compute Q and R for you. However, even if you are only equipped with an inexpensive calculator, there is an easy three-step method to find Q and R:

Method to compute Q and R on a Calculator so that $A=B \times Q +R$

1) Use the calculator to divide A by B. You get a number with decimals.

2) Discard all the digits to the right of the decimal point. This gives Q.

3) To find R, use the formula $R=A-B \times Q$.

For example, suppose  that $A=12345$ and $B=417$. Then,

$A/B=29.6043 \ldots$ so $Q=29$ and

$R=12345 - 417 \times 29=252$

We are now ready to analyze the Euclidean algorithm. The general method looks like:

$a=q_{1} \times b + r_{1}$

$b=q_{2} \times r_{1} + r_{2}$

$r_{1}=q_{3} \times r_{2} + r_{3}$

$r_{2}=q_{4} \times r_{3} + r_{4}$

$\vdots$

$r_{n-3}=q_{n-1} \times r_{n-2} + r_{n-1}$

$r_{n-2}=q_{n} \times r_{n-1} + r_{n}$

$r_{n-1}=q_{n+1} \times r_{n} + 0$

If we let $r_{0}=b$ and $r_{-1}=a$, then every line looks like :

$r_{t-1} = q_{r+1} \times r_{t} + r_{t+1}$.

Why is the last non zero remainder $r_{n}$ a common divisor of a and b?

We start from the bottom and work our way up. The last line $r_{n-1}=r_{n]$. Now, looking at the line above that, we already know that $r_{n}$ divides both $r_{n-1}$ and $r_{n-2}$ so we find that $r_{n}$ also divides $r_{n-3}$. Moving up line by line… finally, we move up to the top line and use fact that $r_{n}$ divides both $r_{1}$ and b to conclude that $r_{n}$ also divides a. This completes our verification that the last nonzero remainder $r_{n}$ is a common divisor of a and b.

But, why is $r_{n}$ the greatest common divisor of a and b?

Suppose that d is any common divisor of a and b. We will work our way back down the list of equations. So, from the first equation $a=q_{1} \times b + r_{1}$ and the fact that d divides both a and b, we see that d also divides $r_{1}$. Then, the second equation $b=q_{2}r_{1}+r_{2}$ shows us that d must divide $r_{2}$. Counting down line by line…therefore, $r_{n}$ must be the greatest common divisor of a and b.

This completes our verification that the Euclidean algorithm actually computes the greatest common divisor, a fact of sufficient importance to be officially recorded.

Theorem (Euclidean Algorithm) To compute the greatest common divisor of two numbers a and b, let $r_{-1}=a$, let $;atex r_{0}=b$, and compute successive quotients and reminders $r_{i-1}=q_{i+1} \times r_{i} + r_{i+1}$

for $i=0,1,2, \ldots$ and some remainder $r_{n+1}$ is 0. The last nonzero remainder $r_{n}$ is then the greatest common divisor of a and b.

Fun with computer programming: you can write a computer program to compute the gcd of large numbers ! Try its very easy and real fun 🙂