Number Theory/Diophantine Analysis
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
editSimple Systems
editThe problem is, given any two of a, b, c, d, e, f, and g, find x and y.
For x:
Linear Diophantine Equations
editBezout's Identity [ax+by=d]
editIn 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
editThe 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]
editContinued Fractions
editInfinite Descent
editPythagorean Equations
editPythagorean Triples
editPythagorean 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
editFermats 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
editMagic Squares & Design Theory
editSystem of Modular Congruences
editChinese Remainder Theorem
editHarmonic Diophantine Equations
editPartitions of Natural Numbers
editExponential Equations
editProblems
editp/x + q/y = 1
editProblem Let p and q be prime numbers. Find the number of pairs of positive numbers x,y that satisfy the the equation:
Dividing the equation by pq, we get
Resources
editTextbooks
edit- Wikibook on Number Theory
- Wikibook on High School Mathematics Extensions
- A Computational Introduction to Number Theory and Algebra
- Elementary Number Theory
Practice Questions
editRelated WebApps
editActive participants
editThe 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).