­Introduction To Number Theory


We are back with the new article on introduction to number theory (The most demanded and hot topic in the world of Algorithms).

If you are a person who loves mathematics then you will fall in love with number theory, and if you don’t love mathematics, we will make number theory fall in love with you 😊.

Be relaxed and keep reading.

In this article we shall look at some extra-ordinary introduction to Number Theory basics, partly because they are interesting in themselves, certainly because they are used a lot in Competitive Programming, and partly because they will give you a flavour of what Number Theory is about.

Believe me if you are not good at number theory than you will probably be not able to perform good in coding contest as some coding contest are specifically focussed on Number Theory concepts.

1. What is Number Theory?

  • Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions.
  • In simple words number theory focusses mainly on doing magic with numbers like if you want to know whether a number is prime or not, we can just divide and check by all of its lesser number or we can just check till square-root of that number (optimized way).
  • Number theory provides us with a lot of proofs and short-cuts to save computational task which is really helpful when we want our code to be very efficient.

Topics covered in number theory articles on Programmers Army:

1. Primality Test:

a. Naive Approach (Brute Force).

b. Optimized Approach ( O(sqrt(n) ).

c. Sieve of Eratosthenes. ( O(1) ).


2. Prime Factorization:

a. Naive Approach (Brute Force).

b. Optimized Approach ( O(sqrt(n) ).

c. Prime factorization using sieve ( O(logn) ).


3. Binary Exponentiation (Technique to calculate a^n in O(logn) ).


4. Matrix Exponentiation.


5. Calculate ‘Nth’ element of recurrence relation in O(logn)


6. G.C.D algorithm:

a. Naive Approach (Brute Force).

b. Euclid Division Algorithm ( O(logn) ).


7. Modular Arithmetic – Part 1 (Basics)


8. Modular Arithmetic – Part 2:

a. Modular Exponentiation.

b. Modulo multiplicative inverse:

i. Fermat’s little theorem,

ii. Extended Euclidean Algorithm.


9. Total Divisors from prime factorization.


10. Binomial co-efficient using modulo inverse.


11. Euler’s Totient Function.

a. Naive Approach.

b. Optimized Approach.


12. Calculating Euler’s Phi function using sieve ( O(Nlog(logN)) ).


13. Euler’s Totient function & G.C.D sum.


14. And Many More…

These were very detailed glimpse of topics which we are going to cover in this series of number theory articles, So even if you are familiar with some concepts mentioned above we will make that understanding crystal-clear in your mind with our best efforts, and if you are a newbie in number theory than reading this articles in above mentioned sequence will make you pro in Number Theory.

So that’s it for this article as this is just introduction of number theory we will be coming up with our next article very soon till then keep learning, keep coding, keep reading and keep improving !!

Happy Coding 😊

By Programmers Army