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

Simple Systems

$\ x+y=a,x-y=b,xy=c,x^{2}+y^{2}=d,x^{2}-y^{2}=e,x^{3}+y^{3}=f,x^{3}-y^{3}=g.$

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

For x:

Linear Diophantine Equations

Bezout's Identity [ax+by=d]

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

$ax+by=d.\,$

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

$\left\{\left(x+{\frac {kb}{\gcd(a,b)}},\ y-{\frac {ka}{\gcd(a,b)}}\right)\mid k\in \mathbb {Z} \right\}.$

Extended Euclidean Algorithm

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

$ax+by=\gcd(a,b).\,$

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

Pythagorean Equations

Pythagorean Triples

Pythagorean triplets are sets of three natural numbers that satisfy Pythagoras' theorem;$x^{2}+y^{2}=z^{2}$ 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 $(n+1)^{2}=n^{2}+2n+1$ 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

Fermats last theorem is a theorem about an equation that is similar to pythagorus' theorem. It is $x^{n}+y^{n}=z^{n}$. Fermats last theorem states that there are no integer solutions to this equation for x,y,z does not equal 0 and $n>2$. 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.

Problems

p/x + q/y = 1

Problem Let p and q be prime numbers. Find the number of pairs of positive numbers x,y that satisfy the the equation: $p/x+q/y=1\,\!$

[±] Answer

Dividing the equation by pq, we get
$1/qx+1/py=1/pq$
$(qx-pq)(py-pq)=p^{2}q^{2}$

Resources

Textbooks

• Wikibook on Number Theory
• Wikibook on High School Mathematics Extensions
• A Computational Introduction to Number Theory and Algebra
• Elementary Number Theory

Practice Questions

• from Math Links Everyone

Related WebApps

• Online Bezout Calculator

Active participants

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

---