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 number theory problem. You will 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:
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 $latex F_n $ and $latex F_{n+1}$ are related? That is easy. $latex 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. $latex 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 $latex 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 $latex g|F_{n+1}, F_n \rightarrow g | F_{n+1} - F_n = F_{n-1} $ which implies $latex 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 $latex g|F_{1} = 1 $. Hence g = 1.
Now, observe that there $latex 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!