Number Theory/Diophantine Analysis

From Wikiversity
Jump to navigation Jump to search
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 | edit source]

Simple Systems[edit | edit source]

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 | edit source]

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

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 | edit source]

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 | edit source]

Continued Fractions[edit | edit source]

Infinite Descent[edit | edit source]

Pythagorean Equations[edit | edit source]

Pythagorean Triples[edit | edit source]

Pythagorean triplets are sets of three natural numbers that satisfy pythagorus' 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 | edit source]

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 | edit source]

Magic Squares & Design Theory[edit | edit source]

System of Modular Congruences[edit | edit source]

Chinese Remainder Theorem[edit | edit source]

Harmonic Diophantine Equations[edit | edit source]

Partitions of Natural Numbers[edit | edit source]

Exponential Equations[edit | edit source]

Problems[edit | edit source]

[edit | edit source]

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 | edit source]

Textbooks[edit | edit source]

Practice Questions[edit | edit source]

Related WebApps[edit | edit source]

Active participants[edit | edit source]

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).