Tag Archives: Diophantine Equations

Generalization of Pythagoras equation

Standard

About 3 years ago I discussed following two Diophantine equations of degree 2:

In this post, we will see a slight generalization of the result involving Pythagorean triplets. Unlike Pythagoras equation, x^2+y^2-z^2=0, we will work with a little bit more general equation, namely: ax^2+by^2+cz^2=0, where a,b,c\in \mathbb{Z}. For proofs, one can refer to section 5.5 of Niven-Zuckerman-Montgomery’s An introduction to the theory of numbers.

Theorem: Let a,b,c\in \mathbb{Z} be non-zero integers such that the product is square free. Then ax^2+by^2+cz^2=0 have a non-trivial solution in integers if and only if a,b,c do not have same sign, and that -bc, -ac, -ab are quadratic residues modulo a,b,c respectively.

In fact, this result helps us determine the existence of a non-trivial solution of any degree 2 homogeneous equation in three variables, f(X,Y,Z)=\alpha_1 X^2 +\alpha_2Y^2+\alpha_3Z^2+\alpha_4XY+\alpha_5YZ+\alpha_6ZX due to the following lemma:

Lemma: There exists a sequence of changes of variables (linear transformations) so that f(X,Y,Z) can be written as an equation of the form g(x,y,z)=ax^2+by^2+cz^2 with \gcd(a,b,c)=1.

Now let’s consider the example. Let f(x,y,z)=3x^2+5y^2+7z^2+9xy+11yz+13zx, and we want to determine whether this f(x,y,z)=0 has a non-trivial solution. Firstly, we will do change of variables:

\displaystyle{f(x,y,z)=3\left(x+\frac{3}{2}y +\frac{13}{6}z\right)^2 - \frac{7}{4}y^2 - \frac{85}{12}z^2 - \frac{17}{2}yz = g(x',y',z')}

where x' = x+\frac{3}{2}y +\frac{13}{6}z, y'=y and z'=z. Thus

\displaystyle{12g(x',y',z')=36x'^2 - 21 y'^2 - 85z'^2 - 102y'z' = 36x'^2 - 21\left(y'+\frac{17}{7}z'\right)^2+\frac{272}{7}z'^2=h(x'',y'',z'')}

where x'' = x',y'' = y'+\frac{17}{7}z' and z''=z'. Thus

\displaystyle{7h(x''',y'',z'') = 252x''^2 - 147y''^2+272z''^2=7(6x'')^2-3(7y'')^2 + 17(4z'')^2 = F(X,Y,Z)}

where X=6x'', Y=7y'' and Z=4z''. Now we apply the theorem to 7X^2-3Y^2+17Z^2=0. Since all the coefficients are prime numbers, we can use quadratic reciprocity to conclude that the given equation has non-trivial solution (only non trivial thing to note that -7\times 17 is quadratic residue mod -3, is same as -7\times 17 is quadratic residue mod 3).

Advertisements

Birch and Swinnerton-Dyer Conjecture

Standard

This is part of the 6 unsolved Millennium Problems. Following is a beautiful exposition of the statement and consequences of this conjecture:

Anybody with high-school level knowledge can benefit from this video.

Numbers and Logic

Standard

I am a big fan of number theory. I find the answer to Hilbert’s Tenth Problem fascinating. I was introduced to this problem, a couple of years ago, via the documentary titled : “Julia Robinson and Hilbert’s Tenth Problem“, here is the trailer:

 

You can read more about it here. Also for the sake of completeness, let me state Hilbert’s Tenth Problem:

Does there exist an algorithm to determine whether a given Diophantine equation has a solution in rational integers?

In 1970, Yuri Matiyasevich completed the solution of this problem by using the concept of Turing Machine. This short video provides a nice overview about Turing Machines in general

The answer to Hilbert’s Tenth Problem problem is

No such algorithm exists.

This interplay of number theory and logic is really interesting, isn’t it? But I can’t discuss solution of Hilbert’s Tenth Problem here, since I have never read it. But there is nice overview at Wikipedia.

I will rather discuss a puzzle from Boris A. Kordemsky’s book which illustrates the idea of this interplay.

Ask a friend to pick a number from 1 through 1000. After asking him/her ten questions that can be answered yes or no, you tell him/her the number. What kind of question?

The key to the solution is that 2 to the tenth power is 1024 (that is, over 1000). With each question you knock out half the remaining numbers, and after ten questions only the thought number is left.

I welcome you to think of a number and write the corresponding yes/no questions as a comment below.

A Curious Investigation

Standard

As I always say:

Mathematicians are those weird beasts who enjoy being surrounded by problems.

My current field of interest is Diophantine Equations (DE). Those who ever studied Number theory know about the classic Pythagorean Triplets,  equivalent to finding possible integer solutions of x^2+y^2 = z^2.

Also, it is a standard exercise (involving Method of Infinite Descent) in DE to prove  thatx^2+y^2 = 3 z^2 has no integer solutions. But in this blog post I intend  to discuss following sibling of such degree two DE:

Solve x^2+y^2 = 2z^2 for integers.

Clearly, z\neq 0, I can divide whole equation by z^2 and denote, X=x/z and Y=y/z to get:

Solve X^2+Y^2 = 2 for rational numbers.

Observe that (1,1) is a solution of given equation, then any other solution (a,b) will lie with (1,1) on a line with rational slope (or infinite slope, a vertical line, trivial case). Furthermore, every line through (1,1) with rational slope will intersect with the quadratic curve in exactly two points. Because every quadratic equation has either no solutions or two real solutions, and we already know that (1,1) is one solution.

To find all solutions, we first look at the vertical line case by substituting X=1  and seeing what two solutions you get.  One will be Y=1, and the other gives a solution (which is the same solution in this case). Next, we take a line with rational slope m through (1,1), so that (using slope-intercept form):

Y=m(X-1)+1

Now solve this line  and given curve X^2+Y^2 = 2 (which is circle of radius \sqrt{2} ). We will get:

X = \frac{m^2-2m -1}{m^2+1}

Y=\frac{-m^2-2m+1}{m^2+1}

Where, m \in \mathbb{Q}, thus like x^2+y^2=z^2, x^2+y^2 = 2z^2 has infinite integer solution.

Ending note:

x^2+y^2 = 2 has only 4 integer solutions.

Diophantine Equation & Primes

Standard

I stumbled upon following statement on some webpage (don’t have link):

There exist infinitely many integers n such that n^2 +1 divides n!.

I tried proving it, though not able to prove it but here are my insights:

  • Proof by contradiction (the way we show infinite primes) doesn’t work here.
  • I need to prove that \frac{n!}{n^2+1} = k \in \mathbb{N} for infinitely many values of n, so I should try to express n^2+1 in product form (since numerator is already in product form). After writing denominator in product form,  find a condition satisfied by infinitely many values of n, which generates infinitely many natural numbers as outcomes of \frac{n!}{n^2+1}.

First idea that came to my mind, for factoring the denominator was in terms Gaussian Integers (numbers of form a+ib where a,b are integers and i = \sqrt{-1}), but I am not able to proceed in this direction further.

Second idea to generate factors of denominator was to analyze Diophantine equation (i.e. we are concerned with only integer solutions of given equation), of form: x^2 + 1 = Dy^2

Here is a theorem from Diophantine equation, which can help me generate factors:

Lemma: Let p be a prime. The diophantine equation: x^2 - py^2 = -1 is solvable if and only if p=2 or p\equiv 1 \pmod 4

Proof: If the considered equation has a solution (x,y), then p| x^2+1. Hence either  p=2 or  p \equiv 1 \pmod 4.

For p=2x=y=1 is a solution.

We show that there is a solution for each prime p=4t+1. Let us study the existence of an integral solution (x_0,y_0) to the wee known diophantine equation: x_0^2 - py_0^2 = 1.

Observe that x_0 is odd [otherwise, y_0^2 \equiv py_0^2 \equiv 3 \pmod 4, but no square leaves a remainder 3 when divided by 4]. Thus in the relation:

x_0^2 - 1 = (x_0-1)(x_0+1) = py_0^2

factors x_0+1 and x_0-1 have greatest common divisor 2, and consequently one of them is a doubled square (to be denoted by 2x^2) and the other one 2p times a square (to be denoted by 2py^2).

The case x_0+1 = 2x^2 and x_0-1 = 2py^2 is impossible because it leads to a smaller solution of diophantine equation: x^2-py^2=1. [method of infinite descent]

It follows that x_0-1=2x^2 , and x_0+1 = 2py^2, therefore x^2-py^2 = -1

——

Now we return back to main statement.

——

Let n^2+1 = pm^2, where m \in \mathbb{N} and p is a prime of  form p=2 or p \equiv1 \pmod 4.

Now let us consider another result:

Lemma: There are infinitely number of primes of the form 4n+1.

ProofSuppose n>1 is an integer. Let p be the smallest prime divisor of N.

We define N=(n!)^2 +1.

Since N is odd, p cannot be equal to 2. It is clear that p is bigger than n (otherwise p \mid 1 ).

We know that p has the form 4k+1 or 4k+3. Since p\mid N we have:

(n!)^2 \equiv -1 \pmod p \

\Rightarrow (n!)^{p-1} \equiv (-1)^{ \frac{p-1}{2} } \pmod p.

Using Fermat’s little Theorem we get (-1)^{ \frac{p-1}{2} } \equiv 1 \pmod p.  

If p was of the form 4k+3 then \frac{p-1}{2} =2k+1 is odd and therefore we obtain -1 \equiv 1 \pmod p or p \mid 2 which is a contradiction since p is odd.

Hence, p is of the form 4k+1, now we can repeat the procedure replacing n with p and produce an infinite sequence of primes of the form 4k+1.

——

From above lemma, we can say that, n^2+1 = pm^2 for infinitely many values of p

I have expressed denominator in product form, what remains to prove is that the expression \frac{n!}{pm^2}  simplifies to give a natural number as answer.

Now this appears to me as a dead end.

If you discover/know the proof of starting statement please give its outline in comments.

But, the motive of this post is to show the beautiful flowers I observed while searching for a path which leads to given statement.

Conclusion (non mathematical)

Standard

Day before yesterday, I presented my project report titled “Diophantine Equations”. It is 90 pages long (anybody who comes to know about this curses me!) containing proof of about 40 theorems and many more illustrations and definitions. I will upload it once I have submitted it at NISER. But here is conclusion of my report:

image

You must be thinking that I have gone nuts! How can this be conclusion of some mathematics report, which deals with solving some kind of weird equation??

The main objective of the project was to analyze (discusses very old math) the available methods for solving a specific class of equations. And since problem solving is the life-blood of mathematics, the above poster is all about problem solving in real life, which I believe also works in mathematics. (I don’t want to destroy beauty of above poster, by drawing analogy, if interested do it yourself!)

Digression: Journey Experiences

1.  Go to Chandigarh if you are in search of beautiful life partner.
2.  Go to Pune  (especially in monsoon), if you are a couple, ideal place for romance (in Pune if you are roaming alone implies that you are a loser).
3.  Go to Almora, for honeymoon ( it sounds weird to travel agency when you book single ticket!).
4.  Go to Delhi, on a family trip or with friends.

I really regret visiting all 4 places alone….. (may be not???)

image

© XKCD