Number Theory/Diophantine Analysis

Welcome to the Lesson of Diophantine Analysis
Part of the School of Olympiads

This lesson is about Diophantine Equations or indeterminate polynomial equations that allows the variables to be integers only (or in some cases fractions). They have fewer equations than unknown variables and involve finding integers that work correctly for all equations. In more technical language, they define an algebraic curve, algebraic surface or more general object, and ask about the lattice points on it.
While individual equations present a kind of puzzle and have been considered throughout history, the formulation of general theories for solving them was an achievement of the twentieth century.

The questions asked in Diophantine analysis include:

  • Are there any solutions?
  • Are there any solutions beyond some that are easily found by inspection?
  • Are there finitely or infinitely many solutions?
  • Can all solutions be found, in theory?
  • Can one in practice compute a full list of solutions?

These traditional problems often lay unsolved for centuries, and mathematicians gradually came to understand their depth (in some cases), rather than treat them as puzzles.

Some widely used techniques are

  • Factor Decomposition Method
  • Bounding by Inequalities {especially Discriminant Inequality in Quadratic Equations}
  • Parametrization
  • Modular Arithmetic
  • Mathematical Induction
  • Fermat's Infinite Descent
  • Reduction to Pell's and Continued Fractions
  • Positional Numeral Systems
  • Elliptic Curves

Theorems edit

Simple Systems edit


The problem is, given any two of a, b, c, d, e, f, and g, find x and y.

For x:

Linear Diophantine Equations edit

Bezout's Identity [ax+by=d] edit

In number theory, Bézout's identity or Bézout's lemma is a linear diophantine equation. It states that if a and b are nonzero integers with greatest common divisor d, then there exist infinitely many integers x and y (called Bézout numbers or Bézout coefficients) such that


Additionally, d is the least positive integer for which there are integer solutions x and y for the preceding equation.
The Bézout numbers x and y as above can be determined with the Extended Euclidean algorithm. However, they are not unique. If one solution is given by (x, y), then there are infinitely many solutions. These are given by


Extended Euclidean Algorithm edit

The extended Euclidean algorithm is an extension to the Euclidean algorithm for finding the greatest common divisor (GCD) of integers a and b: it also finds the integers x and y in Bézout's identity


(Typically either x or y is negative). The extended Euclidean algorithm is particularly useful when a and b are coprime, since x is the modular multiplicative inverse of a modulo b.

Pell's Equations [x2-ny2=1] edit

Continued Fractions edit

Infinite Descent edit

Pythagorean Equations edit

Pythagorean Triples edit

Pythagorean triplets are sets of three natural numbers that satisfy Pythagoras' theorem;  which describes the relationships between the sides of a right angled triangle. It has been shown that there are an infinite number of them by the following proof.
The square numbers; 1, 4, 9, 16 etc can be seen to be separated by the odd numbers 3, 5, 7 etc. This is because   As an infinite number of these odd numbers are squares ( as an odd number squared results in an odd number) there must be an infinite number of pythagorean triplets.

Fermat's Last Theorem edit

Fermats last theorem is a theorem about an equation that is similar to pythagorus' theorem. It is  . Fermats last theorem states that there are no integer solutions to this equation for x,y,z does not equal 0 and  . It is particularly famous because Fermat stated that he had a proof. The first case of this to be proved was n=4 which was proved by infinite descent.

Pythagorean Quadruples and higher n-tuples edit

Magic Squares & Design Theory edit

System of Modular Congruences edit

Chinese Remainder Theorem edit

Harmonic Diophantine Equations edit

Partitions of Natural Numbers edit

Exponential Equations edit

Problems edit

p/x + q/y = 1 edit

Problem Let p and q be prime numbers. Find the number of pairs of positive numbers x,y that satisfy the the equation:  

Resources edit

Textbooks edit

Practice Questions edit

Related WebApps edit

Active participants edit

The histories of Wikiversity pages indicate who the active participants are. If you are an active participant in this division, you can list your name here (this can help small divisions grow and the participants communicate better; for large divisions a list of active participants is not needed).