# Ten problems of number theory (I don't claim them "top 10 problems").

in MES Sciencelast year (edited)

Hi.

In this post I'm going to pretend to introduce You to the most popular/known problems in number theory.
I like number theory as a branch of mathematics, because it belongs to group "5 minutes to learn, eternity to master", in opposite to math analysis, algebraic topology and other crazy subjects (I don't claim them easier to master, but You probably know what I mean).
It is like with programming languages - C or C++ is harder at the start, but Python is "5 minutes to learn, whole life to master". C++ is easier than Java at the start, but Java has lower "entry point" to get 1st job in Java than C++ (of course it is not like that in 100% situations, I say about tendency I know from real people, programmers).

Number theory is just like "theory about 0,1,2,3,4.....".

• P vs NP
The problem P vs NP belongs to Computer Science, computational complexity. What does Number Theory does there? Some problems in Number Theory belong to NP class, even to NPC class. The problem of primality of a natural number was for a very long in NP class.
At the start of XXI century, 3 amazing people made polynomial time algorithm that decides whether number is prime in polynomial time!
You can read more here:
https://en.wikipedia.org/wiki/AKS_primality_test

The problem of decomposition of any natural number into prime factors is in NPC class. Therefore, if You find polynomial time algorithm for decomposition - You win eternal fame.

• Waring problem - does for every natural number m there exists constant fm (depending on m) such that every natural number can be represented as a sum of fm m-th powers of natural numbers?
In XVIII century there was "battle" between Euler and Lagrange, who proved such fm exist for small m.
For me personally that problem is not very interesting.
• This one is for logicians :). Yuri Matiyasevich solved Hilbert's Tenth Problem (I will do post about Hilbert's Problems in July). In 1930s Kurt Godel proved that every mathematical theory is inconsistent or incomplete (it can be both). Number theory given by Peano axioms is incomplete, see for example Goodstein's Theorem.
Surprisingly, number theory given by any ste of axioms is incomplete. The sentence which cannot be proved always exists among sentences saying that certain polynomial in multiple variables has an integer solution or not!
This polynomial cannot be of degree 1 or 2 (degree of monomial is sum of degrees of each variable in monomial). The problem is which is the lowest possible degree of such polynomial - is it 3 or more?

This problem seems rather childish, but some mathematician said that world is not ready for such problems yet :)
Goodstein's sequence increases MUCH quicker than Collatz'sequence and goes to 0.

• Interesting problems can be found among sentences concerning about infintie sequences of prime numbers? For example, it is very easy to show that there are infinitely many prime numbers of both forms 4k+1 and 4k+3, both forms 6k+1 and 6k+5, all 4 forms 8k+1, 8k+3, 8k+5, 8k+7 etc.
But are there infinitely many primes of form n^2+1 where n-natural?

• Fermat's Last Theorem. The question itself is pure. The interesting parts are methods used to prove this. Algebraic geometry, elliptic curves - these are very advanced domains which were used to prove Fermat's Last Theorem by Andrew Wiles in 1990's.

There are no solutions for x^n + y^n = z^n for n>=3 (for n=2 such solutions are called Pitagorean triples like (3,4,5)).

• Goldbach's Conjecture.
Does every even number >=4 can be expressed as a sum of two primes?
Weaker version: does every natural odd number >=7 can be expressed as a sum of three primes?
In 2013 weaker version was proved by Harald Helfgott for numbers large enough. Lower ones were checked by computer. So, weaker one is proved.
Why stronger implies weaker? If number 2n can be expressed as sum of two primes p+q, then 2n+3 can be expressed as p+q+3. So, Goldbach's Conjecture implies Weak Goldbach's Conjecture.

• Riemann Hypothesis. Like PI number appears in EVERY branch of mathematics - the same way Riemann's Hypothesis appears in neighbourhood of ALMOST EVERY problem in number theory. The reason is, that under assumption of truthness of Riemann Hypothesis or Generalised Riemann's Hypothesis, almost every algorithm in number theory is quicker. Also, deterministicity of some problems like Miller-RAbin test depend on RH or GRH.

• Birch-Swinnerton-Dyer Conjecture.
Last of three millenial problems related to number theory. It concerns about powers of rational points on elliptic curves over rational field.
This is probably the most "modern" problem. So many great brains were defeated by Riemann's Hypothesis, that it is nice idea to look stronger at such problem.
Elliptic curves are also popular in algebraic geometry and others domains of mathematics.

• ABC Conjecture:
For every e > 0, there are only finitely many triples
of coprime positive integers a; b; c such that a + b = c and c > d^(1+e)" where d
denotes the product of the distinct prime factors of abc
https://en.wikipedia.org/wiki/Abc_conjecture
I'm not into the history if it very much - therefore I will write nothing more instead of writing something I'm not certain.

Thanks for reading.

Good sources (not the only ones):
"Lectures on Number Theory" - Andrzej Białynicki-Birula, Mariusz Skałba - very good first book in number theory
"Elliptic curves in cryptography" - Blake,Seroussi,Smart - non-theoretical, kind book for first meeting with elliptic curves
"Introduction to Number Theory" - Neal Koblitz
Harel, Feldman - "Algorithmic. The spirit of computing".