## Tag Archives: number theory for RMO

### 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 🙂

### A very very light introduction to Number Theory

This little article is a very very light introduction to Number Theory for those motivated to attempt RMO/INMO. On the other hand, it is a light introduction for anyone interested in beginning Number Theory.

Number Theory is the study of the set of positive whole numbers 1,2,3,4,5,6,7…

which are often called the set of natural numbers. We will especially want to study the relationships between the different sorts of numbers. Since ancient times, people have separated the natural numbers into a variety of different types. Here are some familiar and not so familiar examples:

odd numbers {1,3,5,7,9,11…}

even numbers {2,4,6,8,10,…}

square numbers {1,4,9,16,25,36,…}

cube numbers {1,8,27,64,125,…}

prime numbers {2,3,5,7,11,13,17,19,23,29,31…}

composite numbers {4,6,8,9,10,12,14,15,16…}

1 (modulo 4) {1,5,9,13,17,21,25…}

3 (modulo 4) {3,7,11,15,19,23,27…}

triangular numbers {1,3,6,10,15,21…}

perfect numbers {6,28,496,,,,}

Fibonacci numbers {1,1,2,3,5,8,13,21…}

Many of these types of numbers are undoubtedly already known to you. Others, such as the “modulo 4” numbers, may not be familiar. A number is said to congruent to 1(modulo 4) if it leaves a remainder of 1 when divided by 4, and similar for the 3(modulo 4) numbers. A number is called triangular if that number of pebbles can be arranged in a triangle, with one pebble at the top, two pebbles in the next row, and so on. The Fibonacci numbers are created by starting with 1 and 1. Then, to get the next number in the list, just add the previous two. Finally, a number is perfect if the sum of all its divisors, other than itself, adds back up to the original number. Thus, the numbers dividing 6 are 1,2 and 3, and 1+2+3=6. Similarly, the divisors of 28 are 1,2,4,7 and 14, and

1+2+4+7+14=28.

We will encounter all these types of numbers, and many others, in our excursion through the Theory of Numbers.

Some Typical Number Theoretic Questions.

The main goal of number theory is to discover interesting and unexpected relationships  between different sorts of numbers and to prove that these relationships are true. In this section, we will describe a few typical number theoretic problems, some of which we will eventually solve, some of which have known solutions too difficult for us to include, and some of which remain unsolved to this day.

Sum of SquaresI. Can the sum of two squares be a square? The answer is clearly “YES”; for example, $3^{2}+4^{2}=5^{2}$ and

$5^{2}+12^{2}=13^{2}$ These are examples of Pythagorean triples. We will describe all Pythagorean triples in a later blog.

Sums of Higher Powers. Can the sum of two cubes be a cube? Can the sum of two fourth powers be a fourth power? In general, can the sum of two nth powers be an nth power? The answer is NO. This famous problem, called Fermat’s Last Theorem, was first posed by Pierre de Fermat in the seventeenth century, but was not completely solved until 1994 by Andrew Wiles. Wiles’s proof uses sophisticated mathematical techniques that we will not be able to describe in detail. But, we can show (in some later blog) that no fourth power is a sum of two fourth powers.

Infinitude of Primes. A prime number is a number p whose only factors are 1 and p.

• Are there infinitely many prime numbers?
• Are there infinitely many primes that are 1 modulo 4 numbers?
• Are there infinitely many primes that are 3 modulo 4 numbers?

The answer to all these questions is “YES”. We will prove these facts later in some blog.

Sum of Squares II. Which numbers are sums of two squares? It often turns out that questions of this sort are easier to answer first for primes, so we ask which (odd) prime numbers are a sum of two squares. For example,

3=NO;

$5=1^{2}+2^{2}$

$7=NO$

$11=NO$

$13=2^{2}+3^{2}$

$17=1^{2}+4^{2}$

$19=NO$

$23=NO$

$29=2^{2}+5^{2}$

$31=NO$

$37=1^{2}+6^{2}$

Do you see a pattern? Possibly not, since this is only a short list, but a longer list leads to the conjecture that p is a sum of two squares if it is congruent to 1(modulo 4). In other words, p is a sum of two squares, if it leaves a remainder of 1 when divided by 4, and it is not a sum of two squares if it leaves a remainder of 3.

Number Shapes. The square numbers are the numbers 1,4,9,16, …that can be arranged in the shape of a square. The triangular numbers are the numbers 1,3,6,10,… that can be arranged in the shape of a triangle.

A natural question to ask is whether there are any triangular numbers that are also square numbers (other than 1). The answer is YES; the smallest example being

$36=6^{2}=1+2+3+4+5+6+7+8$

So, we might ask whether there are more examples and, if som are there infinitely many ? To search for examples, the following formula is helpful:

$1+2+3+4+...+(n-1)+n=n(n+1)/2$

Twin Primes. In the list of primes, it is sometimes true that consecutive odd numbers are both prime. We have written the twin prime pairs less than 100:

$(3,5),(5,7),(11,13),(17,19),(29,31),(41,43),(59,61), (71,73)$

Are there infinitely many twin primes? That is, are there infinitely many prime numbers p such that p+2 and  is also a prime? At present, no one knows the answer to this question.

Primes of the Form $N^{2}+1$

If we list the numbers of the form $N^{2}+1$ taking N=1,2,3,…we find that some of them are prime. Of course, if N is odd, then $N^{2}+1$ even, so it won’t be prime unless $N=1$. So, it’s really only interesting to take even values of N. We have highlighted the primes in the following list:

$2^{2}+1=5$

$4^{2}+1=17$

$6^{2}+1=37$

$8^{2}+1=65=5.13$

$10^{2}+1=101$

$12^{2}+1=145=5.29$

$14^{2}+1=197$

$16^{2}+1=257$

$18^{2}+1=325=5^{2}.13$

$20^{2}+1=401$

It looks like there are quite a few prime values, but if you take larger values of N you will find that they  become much rarer. So, we ask whether there are infinitely many primes of the form $N^{2}+1$. Again, no one presently knows the answer to this question.

We have now seem some of the types of questions that are studied in the Theory of Numbers. How does one attempt to answer these questions? The answer is that Number Theory is partly experimental and partly theoretical. The experimental part normally comes first; it leads to questions and suggests ways to answer them. The theoretical part follows; in this part, one tries to devise an argument that gives a conclusive answer to the questions. In summary, here are the steps to follow:

1) Accumulate data, usually numerical, but sometimes more abstract in nature.

2) Examine the data and try to find patterns and relationships.

3) Formulate conjectures (that is, guesses) that explain the patterns and relationships. These are frequently given by formulae.

4) Test your conjectures by collecting additional data and checking whether the new information fits your conjectures.

5) Devise an argument (that is, a proof) that your conjectures are correct.

All five steps are important in number theory and in mathematics. More generally, the scientific method always involves at least the first four steps. Be wary of any purported “scientist” who claims to have “proved” something using only the first three. Given any collection of data, it’s generally not too difficult to devise numerous explanations. The true test of a scientific theory is its ability to predict the outcome of experiments that have not yet taken place. In other words, a scientific theory only becomes plausible when it has been tested against new data. This is true of all real science. In mathematics, one requires the further step of a proof, that is, a logical sequence of assertions, starting from known facts and ending at the desired statement.

More later…

Nalin Pithwa