obito022's blog

How to learn Number Theory?
By obito022, history, 2 years ago, In English

I am trying to learn math for competitive programming. I want to start with Number Theory and I am confused. I don't know how to start with it and and actually use it to solve cp problems. I can easily solve implementation, string etc. problems but when I see some math numbers, symbols I get scared. so how I can I acquire the knowledge about math in general for cp? someone please help me out! And I am still in high school and I don't have that much experience with extreme math. I have never been to any math competition.

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

You need to get comfortable with these topics primarily

  • Divisibility
  • Congruence, residue classes
  • Primes, properties of primes, prime power factorization
  • gcd, properties of gcd, lcm
  • euclid's algorithm for gcd, and extended euclid for linear diophantine equations
  • chinese remainder theorem
  • Number Systems in different bases, and related properties

Here are some algorithms you would definitely need to know - Bigmod (fast exponentiation under modulo) - Inverse mod (conditions for existence) - Sieve for precalculation of primes - Factorization, prime-power factorization

For the theoretical topics, you should check out some books, I recommend 104 Number Theory Problems from USA IMO Training, you can also try to find your way through these Michael Penn — Number Theory

But after having some basic knowledge, it's just solving a lot of problems, mastery comes with practice.

Some of the more intermediate topics include

  • totient function
  • Number of Divisors
  • Sum of Divisors
  • General properties of multiplicative functions
  • Wilson's Theorem
  • Miller Rabin primality detection
  • Pollard Rho factorization
→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi!

You can learn the math for CP on USACO Guide. We are still developing our modules, so we don't have every possible math topic that will come up in a CP contest; however, USACO Guide is definitely a great introduction to the math required for CP.

Here are the modules I recommend you look at:

You can also gain math experience by solving problems with the math tag, and use the editorials for help on specific problems. There are also plenty of good CF blogs out there, so I recommend you use that.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Hi, how about adding the subset of lectures from this playlist on NT by Richard E. Borcherds to Divisibility and Modular Arithmetic Resources. I like them. Please have a look, when you find time.

    obito022, you can also follow it. Doing upto lecture no. 17 and solving problems will suffice the requirement for now imo.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

watch utkarsh guptas math in cp series in unacademy it is free and one of the best.

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Thanks everyone! I didn't expect these many response. I hope all of you will help me in my future journey! Thanks again!

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What should I study in number theory for problems between (1000-1600) ? because I don't want to learn things that I don't use at my current level

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

help me pls!!!!

→ Reply