Fermat's Method of Infinite Descent

This note has been used to help create the Fermat's Method of Infinite Descent wiki

My second note for TorQue Group - Here we go :) ......

Q.\textbf{Q.}Solve in non-negative integers the equation:- x3+2y3=4z3x^{3}+2y^{3} = 4z^{3}

new new

Solution.\textbf{Solution.} Clearly we can observe the (0,0,0)(0,0,0) is a solution.

Next let us suppose that (x1,y1,z1)(x_1,y_1,z_1) be a non-trivial solution.Since 21/32^{1/3} and 41/34^{1/3} are both irrational it is clear that x1>0,y1>0,z1>0x_1 > 0,y_1 > 0,z_1 > 0.

From x13+2y13=4z13x_1^{3}+2y_1^{3} = 4z_1^{3},it is quite evident that x1x_1 must be even.So we can write x1=2x2x_1 = 2x_2.(where x2x_2 is a positive integer).Then we have 4x23+y13=2z134x_2^{3}+y_1^{3} = 2z_1^{3}.Hence now we have y1=2y2y_1=2y_2.Similar;y in the next step we will have z1=2z2z_1 = 2z_2.So finally we can continue this procedure over and over again to obtain a decreasing sequence of integers x1>x2>x3>....x_1 > x_2 > x_3 > .....But since x1x_1 is a finite positive integer this sequence surely cannot go on forever with going negative.Hence we have a contradiction and no other solution is possible.

Introduction:\textbf{Introduction:}Fermat's method of infinite descent is essentially the contrapositive of mathematical induction that can be used to disprove statements.In the language of the ladder metaphor, if you know you can’t reach any rung without first reaching a lower rung, and you also know you can’t reach the bottom rung, then you cannot reach any rung.

dominoes falling??no?? dominoes falling??no??

Statement:\textbf{Statement:} It can be stated as follows:

Let kk be a non-negative integer.

Whenever P(m)P(m) is true for an integer m>km > k ,then there must exist some smaller integer jj with m>j>km>j>k for which P(j)P(j) is true.

The P(n)P(n) is false for all n>kn > k

Intuition:\textbf{Intuition:}That is, if there were an n for which P(n)P(n) was true, one could construct a sequence n>n1>n2>n > n_1 > n_2 > · · · all of which would be greater thank k but for the non-negative integers, no such infinite descending sequence exists.

Variants:\textbf{Variants:}The FMID has two variants that can be extremely useful especially in the solution of Diophantine equations.They are

1.1.There is no sequence of non-negative integers n1>n2>n_1 > n_2 > · · · .

2.2.If the sequence of non-negative integers nin_i with 1i1 \le i satisfies the inequalities n1n2 n_1 ≥ n_2 ≥ · · · , then there exists ii such that ni=ni+1=.n_i = n_{i+1} = · · · .

We used the variant 1 itself to solve the problem at the beginning of this section.

Q.\textbf{Q.}Find the maximal value of m2+n2m^{2} + n^{2} if m and n are integers between 11 and 19811981 satisfying (n2mnm2)2=1(n^{2} - mn - m^{2})^{2} = 1. [22nd IMO]

Solution:\textbf{Solution:}Clearly (m,n)=(1,1)(m,n) = (1,1) is a trivial solution.Moreover,putting m=nm=n we get m=n=1m=n=1 .

Also if a pair m,nm,n satisfies the relation and 0<m<n0 < m < n then we have m<n2mm < n\le 2m[This can be shown by ptuung the values in the equation].Then completing he square we get : (n2mnm2)2=((nm)2+mn2m2)2(n^{2} - mn - m^{2})^{2} = ((n - m)^{2} + mn - 2m^{2})^2 =((nm)2+m(nm)m2)2= ((n - m)^{2} + m(n - m) - m^{2})^{2} =(m2m(nm)(nm)2)2= (m^{2} - m(n - m) - (n - m)^{2})^{2}

Clearly m,nmm,n-m satisfies the same relation.

By Variant 2, the transformation (m,n)(nm,m)(m, n) → (n-m,m) must terminate after finitely many steps, and it terminates only when m=n=1.m = n = 1..Hence all the pairs satisfying the above relation can be obtained by the inverse transformation (m,n)(n,m+n)(m, n) → (n,m + n) several times:(1,1)(2,1)(3,2)(5,3)(1, 1) → (2, 1) → (3, 2) → (5, 3) →· · ·

So the components of all such pairs are Fibonacci numbers.The largest Fibonacci number less than 19811981 is F16=1597F_{16} = 1597,so the answer to the problem is F152+F162=3524578F_{15}^{2}+F_{16}^{2} = 3524578.

Fib Fib

Historical Background:\textbf{Historical Background:}The method of infinite descent is associated with the name of Pierre de Fermat because he was probably the first to state it explicitly even though Euclid makes use of the infinite descent in his elements (see problem2).In a letter to Christian Huygens Fermat claimed infinite descent as his own :

"I have finally organized this according to my method and shown that if a given number is not of this nature there will be a smaller number which also is not, then a third less than the second, etc., to infinity, from which one infers that all numbers are of this nature."

Fermat Fermat

Here are a few practice problems please post the answers in the comment box :) . To view my note on the partitioning of integers click here

Problem 1.\textbf{Problem 1.}Using Fermat's principle of Infinite descent prove that 2\sqrt{2} is irrational.

Problem 2.\textbf{Problem 2.}Prove that composite number has a prime divisor.(Euclid Elements VII.31)

Problem 3.\textbf{Problem 3.}Solve in positive integers the equation x2+y2+x+y+1=xyzx^{2} + y^{2} + x + y + 1 = xyz.

Problem 4.\textbf{Problem 4.} Solve in positive integers x,y,u,vx, y, u, v the system of equations

x2+1=uyx^{2} +1 = uy, y2+1=vx.y^{2} + 1 = vx.

Problem 5.\textbf{Problem 5.}Prove that if there is a triple (x, y, z) of positive integers such that x2+y2+1=xyzx^{2} + y^{2} + 1 = xyz, then z = 3.Find all such triples.

Problem 6.\textbf{Problem 6.}Prove that k\sqrt{k} is irrational for all k not a perfect square.

Problem 7.\textbf{Problem 7.}Find all integers x,y,zx, y, z satisfying x2+y2+z22xyz=0x^{2} + y^{2} + z^{2} - 2xyz = 0. [Korean Mathematical Olympiad]

Problem 8.\textbf{Problem 8.}Find all solutions of a2+b2=3(s2+t2)a^{2} + b^{2} = 3(s^{2} + t^{2})

My next post will be on stacking problems(which I was supposed to do in this one :P) Good Day!!

Note by Eddie The Head
5 years, 9 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Such well explanation, wonderful!

Anish Puthuraya - 5 years, 9 months ago

Log in to reply

Thanks!!Don't forget to check out my note on Stacking problems

Eddie The Head - 5 years, 9 months ago

Log in to reply

Are u majoring in maths or something. Because i never faced these interesting theorems and conjectures during my high school and not even in graduation. They are not in our courses.

Varun Singla - 5 years, 5 months ago

Log in to reply

Can I replace the method of infinite descent with a contradiction proof as follows:

Suppose that we have the smallest non-trivial solution. Using one step of the method of infinite descent, we arrived at a smaller solution, contradiction. Therefore there are no non-trivial solutions.

This method seems to be much simpler than the entire infinite descent method... Is there any advantage the method of infinite descent has over this way?

Daniel Liu - 5 years, 8 months ago

Log in to reply

I actually prefer your way over the infinite descent method. Looking at the smallest (and largest cases) sometimes gives us a lot of useful information about a problem. This technique of checking the extreme cases is called the extreme principle and it is one of my most favorite proof techniques.

Mursalin Habib - 5 years, 8 months ago

Log in to reply

Sometimes finding and proving theminimum possible value can be tedious....there infinite descent is much more effective I thnk...check out Eulrers proof of fermats two square theorem

Biswadeep Sen - 5 years, 8 months ago

Log in to reply

What yo said is essentially variant 1 of infinite descent....Is it not???

Eddie The Head - 5 years, 8 months ago

Log in to reply

They are two forms of the same thing not two different steps....Each applied in different cases....

Eddie The Head - 5 years, 8 months ago

Log in to reply

Log in to reply

Really Appreciable Notes

Usama Khidir - 5 years, 2 months ago

Log in to reply

very nice, can you repost the first torque note please?

Jean Lille - 5 years, 9 months ago

Log in to reply

I have put the link just below the picture of Fermat and above the problems :)

Eddie The Head - 5 years, 9 months ago

Log in to reply

For example 2, you mentioned that "the above relation can be obtained by transformation (m,n)(m,n) into (n,m+n)(n, m+n).

May I know how did u transform and why did we have to transform? Thanks!

Happy Melodies - 5 years, 9 months ago

Log in to reply

First we obtained a trivial solution which is (m,n)=(1,1)(m,n) = (1,1).The we proved that whenever (m,n)(m,n) is a solution (nm,m)(n-m,m) is also a solution and hence this decreasing sequence cannot go on forever and must terminate only when m = n = 1. So from (1,1) we perform the reverse transformation that is from m,n)>(n,m+n)m,n) -> (n,m+n) to obtain the other pairs of solutions and getting the Fib sequence in return......... Note that the sequence will terminate iff m = n = 1 which follows from variant 2.....If you have any doubt feel free to ask....

Eddie The Head - 5 years, 9 months ago

Log in to reply

I was very fascinated to read this note I am not familiar with transformations could u explain it in more simple terms.

Rakesh Ramachandiran - 3 years, 10 months ago

Log in to reply

Could anyone give a hint for Problem 1?

Happy Melodies - 5 years, 9 months ago

Log in to reply

Suppose 2\sqrt{2} is rational.

Then 2\sqrt{2} can be written as 2=ab\sqrt{2} = \frac{a}{b}.

So we get 2a2=b22a^{2} = b^{2}.

Since bb must be even,

so.........................D.I.Y...............................

Samuraiwarm Tsunayoshi - 5 years, 8 months ago

Log in to reply

Thank you! :)

Happy Melodies - 5 years, 6 months ago

Log in to reply

As for problem one can approach it the conventional way but instead of taking for granted that gcd(p,q)=1gcd(p,q) = 1 there try to use infinite descent(The general idea)....It's the easiest problem in the section....

Eddie The Head - 5 years, 9 months ago

Log in to reply

Suppose the contrary and let 2=pq\sqrt{2}=\dfrac{p}{q} for relatively prime positive integers p,qp,q.

Daniel Liu - 5 years, 8 months ago

Log in to reply

Can anyone post hints to Problem 3 onwards??? Or maybe post 1 solution? Thanks! :)

Happy Melodies - 5 years, 6 months ago

Log in to reply

God I love your notes. So awesome.

Ivan Sekovanić - 5 years, 5 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...