Suppose you are given a Number Theory Olympiad Problem. You have no idea how to proceed. Totally stuck! What to do?

This post will help you to atleast start with something. You have something to proceed.

But as we share in our classes, how to proceed towards any problem generally comprises of a few easy and simple steps.

Let us illustrate the Algorithm by taking examples.

Example 1:

Problem 1: Prove that any two consecutive terms in the Fibonacci sequence are relatively prime.

Discussion:

Pattern Observation:

Well, playing with the numbers, you get 1, 1, 2, 3, 5, 8, 13, .. are in fact relatively prime. But what to do next? You understand you need to write the problem in Mathematical Language.

Mathematical Language:

How two consecutive terms in a Fibonacci Series say F_n and F_{n+1} are related? That is easy. F_{n+1} = F_n + F_{n-1}, F_{n} = F_{n-1} + F_{n-2} . But then how to proceed? We have two equations in hand! We have

Mathematical Knowledge Base and Application of Tools:

Well, you need to show gcd of two numbers are 1. Right? We have already got a relationship between the two numbers. F_{n+1} = F_n + F_{n-1}, F_{n} = F_{n-1} + F_{n-2} . Let’s see, what tools we can apply? We get if g| F_{n+1}, F_n \rightarrow g | F_{n+1} - F_n = F_{n-1} . Do you see any pattern or any invariance?

Does this depend on the initial numbers? How do we use that information? Well, if g|F_{n+1}, F_n \rightarrow g | F_{n+1} - F_n = F_{n-1} which implies g| F_{n}, F_{n-1} \rightarrow g | F_{n} - F_{n-1} = F_{n-2} . Aha! Did you see it? The pattern!

Yes, you are right! It is like a chain. We get as a result that g|F_{1} = 1 . Hence g = 1.


Number Theory Mathematical Knowledge Base

Knowledge Base of Number Theory for RMO

Problem 2: The numbers 1 through 10 are written in a row. Can the signs “+” and “-” be placed between them, so that the value of the resulting expression is O?

Discussion:

Now, observe that there 2^{!0} = 1024 ways to give different numbers. Well, 1024 ways are too much to work out. There must be some easier way out! Thus we come to the art of Generalization and De – Generalization.

Play with the data and Observe the Pattern:

We ask the simple question of why 10? Why not another number? Thus this single question leads us to experiment with the options of other easier numbers where the number of options to try out with is less. So, we take small numbers {DE-GENERALIZE) like 2, 3 and see the observe the pattern. Just like as if we are experimenting with the Lab Numbers.

Observe for {1,2} we get that all the possible options for the result are {-3,-1,1,3}. Good some pattern that is common in all the numbers? Yes, they are all odd! Well, let’s take {1,2,3}.

For {1,2,3}, we get the set as {-6, -4, -2, 0, 2, 4, 6}. Well! Well! Getting a hunch of it? This gives all of them even numbers, right?

Any pattern or logic that you can use to extend the odd case for {1,2} and even case for {1,2,3} to higher numbers!

Let’s look into the parity, right! How many odds and How many evens may suffice!

Application of the Mathematical Tools and Knowledge and the Pattern:

{1, 2, 3, …10} gives rise to 5 odd numbers and 5 even numbers. The above operation will give rise to an odd number because there are odd numbers of odd numbers, right?

This solves the problem! So, there was hardly any Mathematical Knowledge Base required! We need to observe the pattern mainly and come to the conclusion! Beautiful right!


More problems and their Analysis by the algorithm coming! Stay Tuned!