This construction was originally used to approximate square roots. Notice that if x^2-ny^2=1, then x/y is approximately sqrt(n). These were first studied by Indian mathematicians Brahmagupta and Bhaskara II, which was some of the most sophisticated mathematics at the time.
@@benstallone6784 True, Diophantus studied a lot of different diophantine equations, but the first method for finding primitive solutions (called the cyclic method) were from India. Later European mathematicians discovered a different method with continued fractions.
In case you wanted to know how to get that sequence for xk, yk, you just take the number (xk)+sqrt(n)(yk), which is an element of the field Q(sqrt(n)) and has norm 1, and square it, and you get [(xk)^2+n(yk)^2] + sqrt(n)[2(xk)(yk)], and you see you get the components. They also satisfy the same equation, since this number is the square of a number of norm 1, so it also has norm 1. (the equation x^2 - ny^2 = 1 is just saying that x+sqrt(n)y has norm 1)
Hello there. Thanks a lot for your comment. Could you please give a bit more explanation with some work about why x^2-ny^2=1 just means x+sqrt(n)y has a norm of 1? Thank you so much.
@skyblue4558 the norm of x+n½y in the field Q(n½) is defined as N(x+n½y)=(x+n½y)(x-n½y)=x²-ny² If stuff like these seem intresting to you (the concept of a norm on rings/fields, fields of the form Q(a), where a is some real or complex number) then I suggest you take a look into the world of algebraic number theory (it has some pre requisites to understand the concepts, ring and group theory)
I've noticed a different argument: from the equation b^2=b^2*x^2 -a^2*y^2 one can deduce that (b,ay,bx) is a Pythagorean Triple. Since a and b are coprime by assumption, it follows that y=b*z and hence (1,a*z,x) is a reduced Pythagorean Triple. But this can only be the case if a*z=0 and x=1 which implies z=0 and thus y=b*z=0. Which is a contradiction to the assumption that y is a natural number (>0).
Yep, the only issue is the coprime part because it assumes that the fraction is on minimal terms, and the idea that you can express a fraction in minimal terms could be poisoned by the fundamental theorem of arithmetic. Maybe it is not, but it "feels" like ti may in some obscure way.
I think Michael does not want to use concepts like coprime. His proof does not require that a rational number can be written as a/b with a and b coprime. To be able to reduce to a/b with a and b coprime, you need to be able to pick the "smallest" a (or b). This is not a problem in Z, but could potentially be a problem in other integral domains. (I don't know of a counter example, though. Once you work over an algebraic number field, you have the norm which maps to Z and can use that to pick a "smallest" a.) (I suspect Michael mistakenly believes the possibility to write a rational number as a/b with a and b coprime implies unique factorization. It does not.)
@@wyattstevens8574 He does not want to use the fundamental theorem of arithmetic, i.e. the fact that Z has unique factorization. Now I believe it is a valid discussion whether the fact that every rational number can be written as a/b with a,b integer and coprime is indirectly using unique factorization, but I suspect this is why Michael does not want to assume a,b coprime.
@@jaimeduncan6167 The existence of reduced form does not need fundamental theorem of arithmetic at all, the uniqueness of reduced form needs fundamental theorem of arithmetic
While this isn’t a useful proof for applications, the contrapositive is a little more useful. If you were faced with the equation x² - ny² = 1, if n is a perfect square you know right away this equation has no natural number solutions.
Well you don't need all that for the proof because if n is a square the whole expression is a difference of square which trivialy never equal to one because you can factor it as such and have a factor of x+ny which is already bigger than one. So yeah you don't need that full statement
My favorite proof is based on the well-ordering principle. Suppose sqrt(2)=a/b. So let the set S={k*sqrt(2) \ where k and k*sqrt(2) are positive integers). S is not empty because a =b*sqrt(2). So by the well-ordering principle S has a smallest element. Say s=t*sqrt(2). We have s*(sqrt(2)-s=s*sqrt(2)-t*sqrt(2)=(s-t)*sqrt(2). Because s*sqrt(2)=2t and s are both integers: s*sqrt(2)-s=s*sqrt(2)-t*sqrt(2) = (s-t_*sqrt(2) must also be an interger. It is also positive, because s*sqrt(2)-s=s*(sqrt(2)-1) an sqrt(2)>1. It is also less than s because s=t*sqrt(2), s*sqrt(2)=2t, and sqrt(2)
I dont quite understand the step from (bx-ay)*(bx+ay) >= bx+ay. You say that that both terms must be positiv as b^2 is positive which makes sense to me, but just because bx-ay is positive doesn't mean it is greater or equal to one right? Or am I missing something?
I'm not sure if the Rational Root Theorem relies on the Fundamental Theorem of Arithmetic (its proof might indirectly use it? 🤷♂). But either way using the RRT you can also prove √2 is irrational pretty easily. For reference, the RRT says that if x is a rational root p/q of a polynomial axⁿ + ... + c then p is an integer factor of the constant term c and q is an integer factor of the coefficient a of the highest power in the polynomial. Note that as a special case, consider the polyminal equation x² = 2. You can rewrite this as x² - 2 = 0. So if x = p/q is a rational root of that equation then p is a factor of 2 and q is a factor of 1. That means q = ±1, which immediately means x = p/q = ±p must be an integer. But clearly there is no integer which when squared is 2, so therefore x can not be a rational number. This also generalizes very nicely. Say the equation is xⁿ = c. Then by the RRT if x =p/q then q must be ±1, meaning x = p/q = ±p must be an integer. So if x is rational it must be an integer - i.e. there are no rational fractional roots of integers, the roots are always either integers or irrational numbers.
RRT is a very slick way to do things for sure. As for whether it depends on Fundamental Theorem of Arithmetic, you can prove RRT with Euclid's lemma without relying directly on unique factorization. A corresponding statement to the rational root theorem can be proven in any gcd domain (because you get Euclid's Lemma in every gcd domain), and since there are gcd domains which aren't unique factorization domains, I would say that RRT doesn't rely on the Fundamental Theorem of Arithmetic.
The Rational Root Theorem provides a very short proof, but there is also a simple direct proof using elementary properties of the gcd: if (a, b) = 1 then (a², b²) = 1. If (a/b)² = n, then a² = b²n. If a/b is in lowest terms, then this implies that a² | n, so n = ka² for some integer k. Then a² = b²ka², and 1 = b²k, so b (and k) must be equal to 1, and n = a². This can easily be extended to higher powers simply by extending (a, b) = 1 -> (a², b²) = 1.
So far you proved that if there are integer solutions x,y to x^2- ny^2=1 the the sqrt(n) isnt rational. But it is possible that there are no integer solutions x,y and sqrt(n) is still not rational, right?
He didn't prove there always are such solutions for non-square n, indeed. However, there are. Joseph Louis Lagrange proved that, as long as n is not a perfect square, Pell's equation has infinitely many distinct integer solutions. [wikipedia]
I like the alternative to the classic infinite descent on the power of some prime factors, it just reverses the problem and ask you manually to find a finite set of possible primes that the square root needs to have (x, y are limiting a, b possible prime decomposition) and that's I guess why it doesn't require the fundamental theorem
Wait, how does the usual proof that sqrt(2) is irrational use the fundamental theorem of arithmetic? All you need is that if a prime divides a product, it must divide one of the two factors, right?
Right? Same for square root of any other integer which is not a perfect square. If p is a positive integer, suppose sqrt(p)=m/n (m, n coprime), Then m²=p.n² => (...) => n | m. But this is only possible if n=1 in which case sqrt(p) is an integer. The only thing we need (hidden in the (...)) is the fact that a | bc with a,b coprime, then a | c.
Can this be used for every non integer square root of a natural number? Or may there be a non-perfect square n, for wich the equation doesn't have a solution?
For n=13, it is easy to find x0=18 and y0=5, which give x0²-n*y0²=-1 which only has the wrong sign, but that disappears following the videos logic when computing x1=x0²+n*y0²=649 and y1=2*x0*y0=180, and that satisfies x1²-n*y1²=1 So I guess the message is that the initial x0²-n*y0² only has to have *magnitude* 1; that makes it easier to find. Truncated continued fraction approximations tend to give a quick solution already.
I personally do like the simplicity of the proofs involving the FToA boiling down to the very obvious roadblock that rational square roots of prime numbers don't exist, because if they did, then somehow a number should exist with even powers on all of its prime factors but also at least one prime factor with an odd power, which is impossible. If n's prime factors all have even powers, then sqrt(n) is a whole number by default If n has prime factors with an odd power, then factor out the even parts, leaving a single factor of those primes behind All even powers of n's prime factors will be halved by the square root, leaving square roots of individual primes to the first power to be analyzed Assume that the product of such prime factor's square roots is rational, ie sqrt(p1*p2*p3*p4.....)=q/r, where q and r are whole numbers Square both sides to obtain p1*p2*p3*p4....=q^2/r^2 and multiply by r^2 on both sides You get r^2*p1*p2*p3*p4.....=q^2, and examine both sides of the equation r is a whole number, and is a product of primes, so r^2's prime factorization includes only even powers of primes. p1, p2, p3, etc are primes with an odd power, the power of 1. So the left hand side has at least one odd power prime factor. q^2, like r^2, only has even powers of primes. So somehow the number on the left and the number on the right must be equal, despite the fact that a fundamental property of their prime factors is immutably different. This isn't possible, so the square root of any whole number that is not a perfect square must be irrational.
What if we use the Bezout's identity to find n, assuming that x and y are coprime? gcd(x,y)=1 => gcd(x^2,y^2)=1 u.x^2+v.y^2=1 Then apply extended Euclidean algorithm knowing that u=1, v=-n
I think it's because the left hand side has to equal b, a positive number. If it was negative, then the LHS would equal something negative as bx + ay would be positive. Additionally, since b, x, a, and y are all positive integers, it can't be a decimal.
For 94, the smallest example is: 2,143,295² - 94 * 221,064² = 1. Now THAT's a challenging calculation. Using continued fractions, it's only 15 cycles (in an EXCEL spreadsheet) to find and demonstrate as the smallest.
I wonder if the size of the x and y pair satisfying x² - ny² = 1 is a sign of how "close" √n is to rational numbers a/b where a and b are small. For n = 13, x and y are pretty large which probably indicates that √13 is quite near 18/5, while for n = 5, x and y are smaller perhaps indicating bigger a and b that gives a/b near √5 (38/17).
Perhaps you erroneously assume that (18,5) is a solution for n=13? 18*18 - 13 * 5 *5 = -1, not 1. But apart from that, the solutions indeed give a fast converging approximation of the square root of n. I suspect that this itself gives a proof of the irrationality of the square root of n, because rational numbers cannot be approximated very well by other rational numbers. (E.g. e = sum 1/n! leads to a quick proof that e is irrational.)
@@ronald3836 Actually, you can start with x_0 = 18 and y_0 = 5 and the formulas that are used in the proof will give you x_1 = 649 and y_1 = 180. :) Finding a solution to x^2-ny^2=±1 is enough, because this always works. You can try to find one by looking at the convergents of the continued fraction of sqrt(n).
I believe that the requirement that gcd(a,b) = 1 is important because that forces b =1 for a genuinely square number n. Thus, no natural number solution can exist for the equation given. So if n = t^2 and we allowed gcd(a,b) > 1, b could be any natural number we want. Thus, showing that the equation does not have any roots in the scenario that n is a square becomes a bit more tricky.
I didn't understand how you motivated the induction generating function. I understand that you need something that strictly increases and involves all of the components, but no more than that :(
Unfortunately, no. Sqrt(pi) is irrational, but there aren’t x and y so that x^2-pi*y^2=1. If n is restricted to be a positive integer, then yes! Look up Pell’s equation
Yes, this was proved in India by Bhaskara II in the 12th century and by Narayana Pandit in the 14th century and later by William Brouncker in Europe. x^2-ny^2=1 is called Pell's equation because Euler erroneously attributed it to Pell. See the Wikipedia entry for Pell's equation. Solutions can be found using continued fractions.
I have a question for you all. I was playing around a bit, trying to show, that the sqrt(4) is rational using this theorem. So I wrote: x²-4y²=1 (x-2y)*(x+2y)=1 So regardless whether we have a (-1)*(-1)=1 or a 1*1=1 situation, both factors have to equal each other, which yields: x-2y=x+2y which directly yields that y=0. But since 0 is not a natural number, there cannot exist such numbers x and y, therefore proving, that the root of 4 is indeed rational. Is my proof correct? I would appreciate any comments. :)
This video proved that if you were able to find integer solutions x,y than you know sqrt(n) isnt rational. However it didnt show if no integer solutions x,y existed that the sqrt(n) had to be rational it still could be irrational, i suppose.
We are assuming we don't know that sqrt(4) = 2, so you can't do your second step. You would have to write it slightly differently (x -sqrt(4) y) * (x + sqrt(4) y) =1 But the rest proceeds as you have it
Yep, you are right, I implicitly used sqrt(4)=2. The question is how is the proof of rationality of sqrt 4 different than the proof of irrationality of sqrt 2. I mean how to continue from (x+sqrt(4)y)*(x-sqrt(4)y)=1 now that I know I cannot suse sqrt(4)=2? And where is the difference compared to (x+sqrt(2)y)*(x-sqrt(2)y)=1?
Guys, I just found another flaw in my method. I assumed, that x-2y=x+2y. But that came from the statement, that we either must have (-1)*(-1) or 1*1. But that statement came from the fact, that x-2y and x+2y have to be at least whole numbers because x and y are natural. But that doesn´t work, because I cannot show that x+sqrt(4)y is also natural unless I have proven that sqrt(4) is natural as well. So this is another circular argument inside my original argument. So is the theorem discussed in this video at all usable for showing that sqrt(4) is rational? And if not, what could be a proof?
Just use the continued fraction of the square root for the "non-trivial calculation!" (Wikipedia shows when's a "good place to stop" based on the periodic block length) If the length is even, use convergent [length-1], and if it's odd, use convergent 2[length]-1. In other words use a palindromic section of the expansion, centered on a single number! Here's the sequence (according to Wikipedia) of increasingly non-trivial values of N: (I'll call it d from here out) d= 1, 2, 5, 10, 13, 29, 46, 53, 61, 109, 181, 277, 397, 409, 421, 541, 661, etc. (These are all such values d with less than 4 digits) Alternatively, here's an arguably faster way to find the smallest non-trivial (x, y) pair: start with triples (a, b, k) and (m, 1, m²-d). Now compose these by spitting out triple (am+bd, a+bm, k(m²-d)) and divide out a k² if a+bm | k. Repeat composing this with (m, 1, m²-d) (and satisfying a+bm | k while minimizing what m is) until k=1. If you get to k= -1, just compose the triple with itself and you're good!
I've built an EXCEL spreadsheet that does these calculations for me, as I need them. (I love the Pell equations.). First real monster is: 2,143,295² - 94 * 221,064² = 1 but even that only takes 15 cycles of the continued fraction expansion, and remains within EXCEL's (quite limited) precision.
@@wyattstevens8574 Including Generalized Pell equations where the right hand side is ±1, which I believe appropriate, then: 29,718² - 61 * 3,805² = -1. It's true that imposing the constraint of +1 on the right hand side gives a larger result for n=61; but that system is solved as soon as the fundamental unit of the ring is identified with a right hand side of -1.
Okay. So n=61 requires 10 cycles to get a R.H.S. of -1, and n=94 needs 15 cycles to get a R.H.S. of +1 (but doesn't pass through -1 on the way since 15 is odd).
Simplest thing I could think up is the following: 1. The product of a natural A with itself is always a natural B. 2. Therefore the squareroot of any arbitrary natural B must be a natural. 3. However, all factors of B individually must necessarily be less than B in magnitude. 4. Now sqrt(1) = 1 since 1^2 = 1 5. But what is sqrt(2)? 6. The factors of 2 are 2 and 1, but neither 1^2 nor 2^2 equals 2, viz., 1^2 = 1 and 2^2 = 4 . 7. Conclusion: not all squareroots of naturals are naturals. 8. Every prime has no factors but 1 and itself. 9. Conclusion: no prime is the square of any two smaller naturals. 10. Every composite has a prime factorization of 3 or more prime factors (1 is a prime--fight me, I dare you). 11. sqrt(x) = x^(1/2) 12. Conclusion: for all prime factorizations x = \prod_{k=1} p_k^N for natural constant N and prime p_k, if N is divisible by 2, then x has a natural root, otherwise the root is non-natural. 13. sqrt(x/y) = sqrt(x)/sqrt(y) = (x^(1/2))/(y^(1/2)) 14. the statement for prime factorizations above holds for x and y. 15. Conclusion: if an irreducible fraction of the form (x^N)/(y^(2M)), or (x^(2N))/(y^M)) is given, it cannot be a rational root. 16. not all square roots of naturals are naturals. 17. not all square roots of rationals are rationals. 18. Conclusion: the square root of any rational in which either its numerator, denominator, or both has an exponent not divisible by 2, then the square root of that number must be non-rational. Implies generally that the Kth root of any rational for any N or M (as given in (15)) not divisible by K is non-rational also.
I don't understand why the *first* assumption, namely that x^2 - ny^2 = 1 could not be the one that is false. I mean the order one makes claims is arbitrary. You could have started with the supposition that the square root of n in a/b and *then* the claim about x and y and 1. Then the x and y claim would be the false one.
It can be. Theorem which is proven in this video, says that if x²-ny²=1 with natural x,y,n, then √n is irrational. If this(x²-ny²=1) is wrong, then the theorem doesn't say anything about √n
x^2-ny^2=1 having a solution is the prerequisite condition of the theorem. It’s not an assumption that was added for the sake of deducing a contradiction
The minimal polynomial of sqrt(n) if n is not a square is p(x)=x^2-n. We know that x€Q if and only if x is algebric in Q and x is a root of a 1th degree polynomial in Q. So sqrt(n) if n is not a perfect square cannot be a rational number, because the polynomials that have this number as a radix have a degree greater or Equal than 2.
@@bartekabuz855 yes, example let's take the ring Z[a,b] with x² = -1 and y² = 2. X² - a has a root in Q(a,b) but not in Z[a,b]; (1+a)/b. Proof: ((1+a)/b)² = (1 + 2a + a²)/b² = 2a/2 = a The coefficients of X² - a are 1 and a, both are invertible (obiviously 1 . 1 = 1; and since a² = -1 we have a^4 = a . a^3 = 1). So if the rational root theorem applies, any root would be of the form "divisor of a / divisor of 1" but since both are units in Z[a,b], this root would also be in Z[a,b]. But here it doesn't work since 2.i = (1+i)² = sqrt(2)² . i
Whenever we have a proof that sqrt(n) is irrational, I always like studying the cases where it breaks - eg. the fact that sqrt(4) is clearly not irrational. In the traditional proof by contradiction, the step that breaks in this case is the divisibility step; ie. n|a^2 => n|a. This is only true if n is not a square number. Where does the logic in this proof break when sqrt(n) is not irrational?
You won't be able to find x,y for n=4. That you can find x,y for n not a square is non-trivial (but true). If you pick a fixed n, you can find x and y by enough trial and error. Btw, n | a ^ 2 does not imply n | a. Take n = 8, a = 4. Or n = 12, a = 6. You need n to be square free. And I think you are now close to using unique factorization. For n prime the traditional proof works without invoking unique factorization or something equivalent.
Here is a very short proof, using the structures of the subgroups of Z. For any integer n, define G as the elements x of Z such that x times the square root of n is an integer. G is a subgroup of Z. If we assume that the square root of n is rational, then G is not trivial. Then, there exists a positive integer b such that G=bZ. Define a=b times the square root of n. a is an integer, because b is in G. a times the square root of n equals b times n, and is therefore an integer, which means that a is in G. Recalling that G=bZ, we get that a is a multiple of b. Therefore, a/b, which is the square root of n, is an integer.
One of the assumptions was that a and b were minimal. But why can't a and b scale as much as you want so that b is always greater than whatever x value you have in the series which wouldn't then have the contradiction?
Yeah I wasn't sure if you could set up the definition of a and b in a way that would scale along with x sub n. Like a and b were always a sub n and b sub n where you multiply a sub 0 and b sub 0 by x sub n so you still have a numeric equivalency for the square root of n but you also keep x sub n less than b.
b is defined through sqrt(n) = a/b. n is a constant and thus a,b are constants as well (it doesn't even matter if a and b minimal). Now the contradiction is that we have an increasing sequence of natural numbers bounded above by the constant b, which doesn't work since there are only finitely many natural numbers less than b.
No, because a/b is a particular form. At the beginning of the proof, we are assuming that the fraction is expressed as a/b, where a and b are rational. The fact that there exists other representations are not relevant, for each representation we choose we can use the argument.
I have to look back in the video, but my impression was that this was not an assumption. I think at least the original intention of Michael is that you don't need to assume a to be minimal (and/or a and b to be coprime). It might be that he anyway mentioned something like that out of "habit" (since it pretty standard to pick a and b coprime, obviously).
It can be proven that sqrt(n) is rational n is a perfect square i.e. n = x² for some natural number x. Also, of course, n is taken to be a natural number here. Let's check it out. Sps sqrt(n) is rational, in other words it can be written as a/b for some natural numbers a and b with gcd(a, b) = 1. This implies that also gcd(a², b²) = 1. Since sqrt(n) = a/b we have n = a²/b² and furthermore since n is a natural number and gcd(a², b²) = 1 it must be that b² = 1 => b = 1 => n = a², hence n is a perfect square.
Nice application of Pell's equation. However, the regular proof of the irrationality of the square root of the prime number 2 does not use unique factorization (= fundamental theorem of arithmetic). The proof works just fine in algebraic number fields in which unique factorization does not hold.
Which one is the "traditional" proof? I guess it's the one by infinite descent? A common quick one-line proof uses unique factorization: sqrt(2) = a/b => a^2 = 2 b^2, which is impossible by unique factorization.
@@TheEternalVortex42 Yes, I would say that is the traditional proof. Take p = (a/b)^2 and show that you can find smaller a (and b). But this proof works only if you know that p|ab implies p|a or p|b. This is the definition of "prime number" in algebraic number theory, but if you start from the "normal" definition of a prime as a number divisible only by 1 and itself, then you still need to do some work. (I did not immediately realize this. On the one hand I know too much algebraic number theory and on the other hand this was all too long ago!) I think the point of the video is to find a proof that does not require showing that p|ab => p|a or p|b if n=p is a prime. Also, the proof works for composite numbers n, where unique factorization really starts to come in handy.... Finding x and y can be tricky, though 🙂 So.... yeah, I think Michael is essentially right about this proof at least staying further away from unique factorization.
@@blackkk07 you start with x1,y1 positive integers, and by construction x_(k+1) and y_(k+1) are integers if x_k and y_k are. I don't know if Michael said this, but it follows immediately from the formulas.
I know you didn’t use it, but even to say a/b in shortest terms you need to invoke fundamental theorem of arithmetic. Otherwise there will be multiple shortest options. You didn’t even need the fact it is shortest or a shortest exists
To prove, that the square root of any natural number k, which isn't the square of another natural number, it isn't the square of any rational number either: Let's assume, that √k=a/b, where a and b are natural and gcd(a, b)=1 (because it can). Then k=a^2/b^2 kb^2=a^2 a must be a multiple of k, so it can be expressed as kc, where c is natural. So we have kb^2=k^2c^2 b^2=kc^2, so b is also a multiple of k. Since k>1, gcd(a, b)>1 is necessary, which is a contradiction. This, of course, isn't limited only to square root, it also applies for root of any base bigger than 1.
You write :: kb^2 = a^2 => a is a multiple of k (k is not prime). Now kb^2 = a^2 => a^2 is a multiple of k. Does it automatically follow that a is a multiple of k (k not prime)?
how i would prove: suppose a/b is not an integer, and (a/b)^2 = N (an integer) all we have to show is that if b does not divide a, then b^2 cannot divide a^2
I'm not sure I'm reading you correctly, but if a/b is not an integer, b does not divide a by definition. We can then write that a/b = c/d which is the fraction in its lowest terms, i.e. a=kc and b=kd and gcd(c, d) = 1. But then gcd(c^2, d^2) = 1 also, which shows that d^2 does not divide c^2. Hence k^2*d^2 does not divide k^2*c^2 which means b^2 does not divide a^2.
What might be even more difficult to prove this way is that square root of certain 20-digit number is not irrational. Fortunately there's always the constructive approach.
@@khaledbarbaria9544The claim is that, for a given value of n, IF we can find x, y∈N (which, for Michael Penn, means x, y≥1) such that x²-ny²=1, THEN √n is not in Q. To apply the result for any particular value of n, one must then find such a non-trivial solution with x, y≥1.
There is a stronger result which is that if n ∈ ℕ is not a perfect square, then its square root is irrational. A corollary is that the square roots of natural numbers are either integers or are irrational.
In algebraic number theory a prime number is defined as an integral number satisying p | ab => p | a or p | b. And k | n means that there is integral m with n = k * m. This is valid in integral domains which have no unique factorization, so where the "fundamental theorem of arithmetic" does not hold. Suppose the prime p is the square of a rational number, so p = (a/b)^2. Then a^2 = b^2 * p, so p | a^2. Since p is a prime, this means p | a. Therefore we can write a = p * c. So b^2 * p = a^2 = c^2 * p^2 , which means b^2 = c^2 * p. So now we get p | b^2 and thus p | b, so b = p * d. This gives us p = a/b = c/d. If we go back to working in the natural numbers (i.e. the integral domain Z), we see that c < a, and if we make sure to pick a and b so that a is minimal, we have a contradiction. So the regular proof works without using the fundamental theorem of arithmetic. We can generalize the result to primes in algebraic number fields (where the integers are those numbers that are the roots of a polynomials x^n + a_n-1 x^(n-1) + ... + a_0 with a_i in Z) by chosing the numbers a and b such that the norm of a is minimal. The norm of an integral number is an integer, and the norm is multiplicative, so everything works as in Z. So the proof does not only work without using the fundamental theorem of arithmetic, it even works in algebraic number fields in which the fundamental theorem of arithmetic does not hold.
Now what is left to show is that prime numbers in N ("numbers only divisible by 1 and themselves") are prime numbers in the sense of algebraic number theory. In general this seems to be close to proving unique factorization, but for a specific prime p I think you can just check all possibilities mod p.
I can prove it in one sentence : if n is a perfect square, then difference between two positive perfect squares can not be equal to 1 ( X^2 - n*Y^2=1), therefore n is not a perfect square, therefore n^(1/2) is irrational.
@@AlcyonEldara Assume q is a non integer rational number and q² is an integer. Set q=a/b, GCD(a,b)=1, and set q²=c, then a/b * a/b = c. This is possible only when a=b=1, but it is a contradiction. Then q² is also not an integer.
@@iljas275 example: lets x = i and y = sqrt(2). Z[x,y] = {a+b.x+c.y+d.x.y |a, b, c and d in Z}. You can prove that Z[x] is a ring. Remember that x² = -1 and y² = 2. (1+x)/y isn't in this ring but is inhis fraction field Q(x,y). but ((1+x)/y)² = (1 + 2x + x²)/y² = (1 + 2i - 1)/2 = i = x is in Z[x,y].
You've correctly proven that n isn't a perfect square in a sense that n≠x² for all integer x, but you didn't prove that there is no such rational x, so √n may still be rational
This is a very interesting proof. But it makes me wonder about a more interesting idea... whether there is a way to prove that the square root of a non-perfect-square is rational. I'm not a formal number theory student, so I don't even know if such a thing exists... just thinking about it, I'm inclined to believe that if a natural number isn't a perfect square, then its square root must be irrational. I welcome feedback from any more serious (and undoubtedly better trained) mathematicians on this subject.
If a natural number is not a perfect square, then indeed its square root is non-rational. Suppose n is the square of a rational number a/b. We can choose a and b to be coprime (i.e. they have no common divisor) by cancelling out any common divisors that they initially might have. So n = (a/b)^2, which means a^2 = n * b^2. Now suppose b > 1. Then you can find a prime p that divides b. (Primes are 2,3,5,7,.... so without 1.) Since p divides b, it also divides n * b^2 = a^2. This means that p also divides a. But now a and b have p as a common divisor, which was contrary to our assumption that a and b are coprime. So b = 1 and n = a^2 is a perfect square.
We want to prove, that in x^2-ny^2=1, where x and y are natural, n isn't the square of any rational number. Lets assume, that it is and that the value of ny^2 isn't an integer. Then x^2-ny^2 can't be an integer, because x^2 is and we have a difference of an integer and a non-integer. So ny^2 must be an integer. But then we're asking for 2 squares of integers with a difference of 1. There's only 1 option for that and it's when x=1 and ny^2=0. No other options exist. So to summarize, in the equation x^2-ny^2=1, where x and y are natural, if n=0, x=1 and y can be anything, while if (x, y)=(1, 0), n can be anything, including the square of a rational number.
0 isn't included in the natural numbers so Y cannot equal zero under the setup shown in the video also ny^2 isn't necessarily the square of an integer, only y^2 is the square of an integer -(except for n = 1 or n = y^2 of course)- (unless n = some integer c^2, but this does not have to be the case)
@@supremedevice1311 Also, I just wanted to prove, that ny^2 has to be an integer, because such is x^2. I never said anythinf about ny^2 being the square of an integer. I don't know why you've brought it up, but those aren't the 2 only possible values of n such, that ny^2 is the square of an integer. n could be the square of any other integer. I think you should rewatch the video.
You're saying that ny² must be an integer, but this doesn't mean that ny² is a square of a natural number. You also need to also prove that n must be a square of an integer number
If n is a perfect square, then x^2 - n y^2 = 1 has no solution. Because if n is a perfect square, e.g. n = q^2, then x^2 - n y^2 = x^2 - q^2 y^2 = x^2 - (qy)^2, i.e., the difference between two positive perfect squares. But the difference between two positive perfect squares is never equal to 1.
But does the proof of that theorem use the fundamental theorem of arithmetic? (Probably not, but I am not 100% sure.) If you know algebraic number theory, then you know that solutions of the equation x^2 - n = 0 are integral by definition of "integral". If they are also in Q, they have to be in Z. And clearly there is no integer in Z which multiplied by itself gives 2. The traditional proof of the irrationality of sqrt(2) applied to primes in number fields works fine, even if the ring of integers of the number field has no unique factorization. But I am now wondering if perhaps somewhere in the basics of algebraic number theory we use the fact that Z has unique factorization...
This construction was originally used to approximate square roots. Notice that if x^2-ny^2=1, then x/y is approximately sqrt(n). These were first studied by Indian mathematicians Brahmagupta and Bhaskara II, which was some of the most sophisticated mathematics at the time.
And now commonly known as Pell's equation because Euler got confused :-)
It goes back even further to the ancient greeks.
@@benstallone6784 True, Diophantus studied a lot of different diophantine equations, but the first method for finding primitive solutions (called the cyclic method) were from India. Later European mathematicians discovered a different method with continued fractions.
youtube.com/@zwitterstat
A nice way to write the contradiction:
x_k >= k for all k (by a trivial induction), and x_k < b for all k. So b
It is ok, but for to use x_k
@@albertogarcia4177Do you mean “…show [that] $x_k^2 - n y_k^2 = 1$ for all k” ?
In case you wanted to know how to get that sequence for xk, yk, you just take the number (xk)+sqrt(n)(yk), which is an element of the field Q(sqrt(n)) and has norm 1, and square it, and you get [(xk)^2+n(yk)^2] + sqrt(n)[2(xk)(yk)], and you see you get the components. They also satisfy the same equation, since this number is the square of a number of norm 1, so it also has norm 1. (the equation x^2 - ny^2 = 1 is just saying that x+sqrt(n)y has norm 1)
Hello there. Thanks a lot for your comment. Could you please give a bit more explanation with some work about why x^2-ny^2=1 just means x+sqrt(n)y has a norm of 1? Thank you so much.
@skyblue4558 the norm of x+n½y in the field Q(n½) is defined as
N(x+n½y)=(x+n½y)(x-n½y)=x²-ny²
If stuff like these seem intresting to you (the concept of a norm on rings/fields, fields of the form Q(a), where a is some real or complex number) then I suggest you take a look into the world of algebraic number theory (it has some pre requisites to understand the concepts, ring and group theory)
I've noticed a different argument: from the equation b^2=b^2*x^2 -a^2*y^2 one can deduce that (b,ay,bx) is a Pythagorean Triple. Since a and b are coprime by assumption, it follows that y=b*z and hence (1,a*z,x) is a reduced Pythagorean Triple. But this can only be the case if a*z=0 and x=1 which implies z=0 and thus y=b*z=0. Which is a contradiction to the assumption that y is a natural number (>0).
Yep, the only issue is the coprime part because it assumes that the fraction is on minimal terms, and the idea that you can express a fraction in minimal terms could be poisoned by the fundamental theorem of arithmetic. Maybe it is not, but it "feels" like ti may in some obscure way.
I think Michael does not want to use concepts like coprime. His proof does not require that a rational number can be written as a/b with a and b coprime.
To be able to reduce to a/b with a and b coprime, you need to be able to pick the "smallest" a (or b). This is not a problem in Z, but could potentially be a problem in other integral domains. (I don't know of a counter example, though. Once you work over an algebraic number field, you have the norm which maps to Z and can use that to pick a "smallest" a.)
(I suspect Michael mistakenly believes the possibility to write a rational number as a/b with a and b coprime implies unique factorization. It does not.)
@@ronald3836Here he indirectly said, "They don't *have* to be, but why not?"
@@wyattstevens8574 He does not want to use the fundamental theorem of arithmetic, i.e. the fact that Z has unique factorization. Now I believe it is a valid discussion whether the fact that every rational number can be written as a/b with a,b integer and coprime is indirectly using unique factorization, but I suspect this is why Michael does not want to assume a,b coprime.
@@jaimeduncan6167 The existence of reduced form does not need fundamental theorem of arithmetic at all, the uniqueness of reduced form needs fundamental theorem of arithmetic
While this isn’t a useful proof for applications, the contrapositive is a little more useful. If you were faced with the equation x² - ny² = 1, if n is a perfect square you know right away this equation has no natural number solutions.
Well you don't need all that for the proof because if n is a square the whole expression is a difference of square which trivialy never equal to one because you can factor it as such and have a factor of x+ny which is already bigger than one. So yeah you don't need that full statement
@@dertyp6074 So that answers the question of "what happens if you put a square number in for n"? Thank you.
@@dertyp6074 Indeed you proved Michael's theorem in the video in a much simpler and quicker way, by proving the contrapositive.
My favorite proof is based on the well-ordering principle. Suppose sqrt(2)=a/b. So let the set S={k*sqrt(2) \ where k and k*sqrt(2) are positive integers). S is not empty because a =b*sqrt(2). So by the well-ordering principle S has a smallest element. Say s=t*sqrt(2).
We have s*(sqrt(2)-s=s*sqrt(2)-t*sqrt(2)=(s-t)*sqrt(2).
Because s*sqrt(2)=2t and s are both integers: s*sqrt(2)-s=s*sqrt(2)-t*sqrt(2) = (s-t_*sqrt(2) must also be an interger.
It is also positive, because s*sqrt(2)-s=s*(sqrt(2)-1) an sqrt(2)>1.
It is also less than s because s=t*sqrt(2), s*sqrt(2)=2t, and sqrt(2)
I dont quite understand the step from (bx-ay)*(bx+ay) >= bx+ay.
You say that that both terms must be positiv as b^2 is positive which makes sense to me, but just because bx-ay is positive doesn't mean it is greater or equal to one right? Or am I missing something?
Yes, I think the same, it is not trivial for me, why is that true... :SS
bx-ay is a positive integer, thus is at least 1
I'm not sure if the Rational Root Theorem relies on the Fundamental Theorem of Arithmetic (its proof might indirectly use it? 🤷♂). But either way using the RRT you can also prove √2 is irrational pretty easily.
For reference, the RRT says that if x is a rational root p/q of a polynomial axⁿ + ... + c then p is an integer factor of the constant term c and q is an integer factor of the coefficient a of the highest power in the polynomial.
Note that as a special case, consider the polyminal equation x² = 2. You can rewrite this as x² - 2 = 0. So if x = p/q is a rational root of that equation then p is a factor of 2 and q is a factor of 1. That means q = ±1, which immediately means x = p/q = ±p must be an integer. But clearly there is no integer which when squared is 2, so therefore x can not be a rational number.
This also generalizes very nicely. Say the equation is xⁿ = c. Then by the RRT if x =p/q then q must be ±1, meaning x = p/q = ±p must be an integer. So if x is rational it must be an integer - i.e. there are no rational fractional roots of integers, the roots are always either integers or irrational numbers.
RRT is a very slick way to do things for sure.
As for whether it depends on Fundamental Theorem of Arithmetic, you can prove RRT with Euclid's lemma without relying directly on unique factorization. A corresponding statement to the rational root theorem can be proven in any gcd domain (because you get Euclid's Lemma in every gcd domain), and since there are gcd domains which aren't unique factorization domains, I would say that RRT doesn't rely on the Fundamental Theorem of Arithmetic.
That final result is fantastic by itself.
I love how this shows that, in a sense, sqrt 2 has an infinite denominator
The Rational Root Theorem provides a very short proof, but there is also a simple direct proof using elementary properties of the gcd: if (a, b) = 1 then (a², b²) = 1. If (a/b)² = n, then a² = b²n. If a/b is in lowest terms, then this implies that a² | n, so n = ka² for some integer k. Then a² = b²ka², and 1 = b²k, so b (and k) must be equal to 1, and n = a². This can easily be extended to higher powers simply by extending (a, b) = 1 -> (a², b²) = 1.
One of the many superior proofs by a superior pedagogue of mathematics!!!
He is the very model of a modern magor pedagogue!
I wouldn’t call it superior.
It does not easily extend to all powers.
@@fullfungo: He still is a superior prodigious pedagogue!
So far you proved that if there are integer solutions x,y to x^2- ny^2=1 the the sqrt(n) isnt rational. But it is possible that there are no integer solutions x,y and sqrt(n) is still not rational, right?
I was wondering the same thing
He didn't prove there always are such solutions for non-square n, indeed. However, there are. Joseph Louis Lagrange proved that, as long as n is not a perfect square, Pell's equation has infinitely many distinct integer solutions. [wikipedia]
what a great proof! loved the presentation as well
I wonder if there's a pattern for when the calculation yields y
I wonder if we would find any underlying structure if we were to look at a large number of the values of (x,y) that satisfy the equation.
You might want to google Pell's equation.
I like the alternative to the classic infinite descent on the power of some prime factors, it just reverses the problem and ask you manually to find a finite set of possible primes that the square root needs to have (x, y are limiting a, b possible prime decomposition) and that's I guess why it doesn't require the fundamental theorem
Wait, how does the usual proof that sqrt(2) is irrational use the fundamental theorem of arithmetic? All you need is that if a prime divides a product, it must divide one of the two factors, right?
Right? Same for square root of any other integer which is not a perfect square.
If p is a positive integer, suppose sqrt(p)=m/n (m, n coprime), Then m²=p.n² => (...) => n | m. But this is only possible if n=1 in which case sqrt(p) is an integer.
The only thing we need (hidden in the (...)) is the fact that a | bc with a,b coprime, then a | c.
@@Felipe-sw8wpRight. This result is not the Fundamental Theorem of Arithmetic, but it is the key ingredient in the proof of the theorem.
Can this be used for every non integer square root of a natural number?
Or may there be a non-perfect square n, for wich the equation doesn't have a solution?
For n=13, it is easy to find x0=18 and y0=5, which give
x0²-n*y0²=-1
which only has the wrong sign, but that disappears following the videos logic when computing x1=x0²+n*y0²=649 and y1=2*x0*y0=180, and that satisfies
x1²-n*y1²=1
So I guess the message is that the initial x0²-n*y0² only has to have *magnitude* 1; that makes it easier to find. Truncated continued fraction approximations tend to give a quick solution already.
I personally do like the simplicity of the proofs involving the FToA boiling down to the very obvious roadblock that rational square roots of prime numbers don't exist, because if they did, then somehow a number should exist with even powers on all of its prime factors but also at least one prime factor with an odd power, which is impossible.
If n's prime factors all have even powers, then sqrt(n) is a whole number by default
If n has prime factors with an odd power, then factor out the even parts, leaving a single factor of those primes behind
All even powers of n's prime factors will be halved by the square root, leaving square roots of individual primes to the first power to be analyzed
Assume that the product of such prime factor's square roots is rational, ie sqrt(p1*p2*p3*p4.....)=q/r, where q and r are whole numbers
Square both sides to obtain p1*p2*p3*p4....=q^2/r^2 and multiply by r^2 on both sides
You get r^2*p1*p2*p3*p4.....=q^2, and examine both sides of the equation
r is a whole number, and is a product of primes, so r^2's prime factorization includes only even powers of primes. p1, p2, p3, etc are primes with an odd power, the power of 1. So the left hand side has at least one odd power prime factor.
q^2, like r^2, only has even powers of primes. So somehow the number on the left and the number on the right must be equal, despite the fact that a fundamental property of their prime factors is immutably different. This isn't possible, so the square root of any whole number that is not a perfect square must be irrational.
What if we use the Bezout's identity to find n, assuming that x and y are coprime?
gcd(x,y)=1 => gcd(x^2,y^2)=1
u.x^2+v.y^2=1
Then apply extended Euclidean algorithm knowing that u=1, v=-n
3:03 - How do we know that (bx - ay) >= 1? It's greater than zero, but ...?
I think it's because the left hand side has to equal b, a positive number. If it was negative, then the LHS would equal something negative as bx + ay would be positive. Additionally, since b, x, a, and y are all positive integers, it can't be a decimal.
@@supremedevice1311 Thanks. I get it now.
For 94, the smallest example is:
2,143,295² - 94 * 221,064² = 1.
Now THAT's a challenging calculation.
Using continued fractions, it's only 15 cycles (in an EXCEL spreadsheet) to find and demonstrate as the smallest.
I wonder if the size of the x and y pair satisfying x² - ny² = 1 is a sign of how "close" √n is to rational numbers a/b where a and b are small. For n = 13, x and y are pretty large which probably indicates that √13 is quite near 18/5, while for n = 5, x and y are smaller perhaps indicating bigger a and b that gives a/b near √5 (38/17).
Perhaps you erroneously assume that (18,5) is a solution for n=13? 18*18 - 13 * 5 *5 = -1, not 1.
But apart from that, the solutions indeed give a fast converging approximation of the square root of n.
I suspect that this itself gives a proof of the irrationality of the square root of n, because rational numbers cannot be approximated very well by other rational numbers.
(E.g. e = sum 1/n! leads to a quick proof that e is irrational.)
@@ronald3836 Actually, you can start with x_0 = 18 and y_0 = 5 and the formulas that are used in the proof will give you x_1 = 649 and y_1 = 180. :)
Finding a solution to x^2-ny^2=±1 is enough, because this always works. You can try to find one by looking at the convergents of the continued fraction of sqrt(n).
@@alonamaloh True, you can square 18+5*sqrt(13) with norm -1 to get 649+180*sqrt(13) with norm +1.
@@ronald3836 Why is it called a norm if it can be negative ?
@@_Ytreza_ oops, you are right. Let me check what I did there 😅
I believe that the requirement that gcd(a,b) = 1 is important because that forces b =1 for a genuinely square number n. Thus, no natural number solution can exist for the equation given. So if n = t^2 and we allowed gcd(a,b) > 1, b could be any natural number we want. Thus, showing that the equation does not have any roots in the scenario that n is a square becomes a bit more tricky.
I didn't understand how you motivated the induction generating function. I understand that you need something that strictly increases and involves all of the components, but no more than that :(
Filling in some gaps in Penn's end-of-video examples: (8^2 )- 7*(3^2) = 1 -> sqrt 7 is irrational
And: (10^2 )- 11*(3^2) = 1 -> sqrt 11 is irrational
Duh! Forgot one: (7^2 ) - 3*(4^2) = 1 -> sqrt 3 is irrational
I wonder what affects the 'size' of x and y for various numbers. Is it how well their continued fractions' convergents approximate it?
Brilliant, proofs like these are why I love math so much
Is the converse also true? ie. Is there some square root that is irrational, but doesn't satisfy the equation?
I'm also curious about this, instantly knowing all nonsquare n yield a solvable equation could be a powerful trick.
Unfortunately, no. Sqrt(pi) is irrational, but there aren’t x and y so that x^2-pi*y^2=1.
If n is restricted to be a positive integer, then yes! Look up Pell’s equation
Yes, this was proved in India by Bhaskara II in the 12th century and by Narayana Pandit in the 14th century and later by William Brouncker in Europe. x^2-ny^2=1 is called Pell's equation because Euler erroneously attributed it to Pell. See the Wikipedia entry for Pell's equation.
Solutions can be found using continued fractions.
Is this an if and only if?
Does a square root being irrational imply a pair (x,y) satisfying the equation exists?
Yes. en.wikipedia.org/wiki/Pell%27s_equation
@@ronald3836 that’s cool thanks
I have a question for you all. I was playing around a bit, trying to show, that the sqrt(4) is rational using this theorem.
So I wrote:
x²-4y²=1
(x-2y)*(x+2y)=1
So regardless whether we have a (-1)*(-1)=1 or a 1*1=1 situation, both factors have to equal each other, which yields:
x-2y=x+2y which directly yields that y=0. But since 0 is not a natural number, there cannot exist such numbers x and y, therefore proving, that the root of 4 is indeed rational.
Is my proof correct? I would appreciate any comments. :)
Looks like a circular argument - you used the fact that sqrt(4) = 2 is an integer to arrive at the conclusion that sqrt(4) is rational.
This video proved that if you were able to find integer solutions x,y than you know sqrt(n) isnt rational. However it didnt show if no integer solutions x,y existed that the sqrt(n) had to be rational it still could be irrational, i suppose.
We are assuming we don't know that sqrt(4) = 2, so you can't do your second step. You would have to write it slightly differently
(x -sqrt(4) y) * (x + sqrt(4) y) =1
But the rest proceeds as you have it
Yep, you are right, I implicitly used sqrt(4)=2.
The question is how is the proof of rationality of sqrt 4 different than the proof of irrationality of sqrt 2.
I mean how to continue from (x+sqrt(4)y)*(x-sqrt(4)y)=1 now that I know I cannot suse sqrt(4)=2?
And where is the difference compared to (x+sqrt(2)y)*(x-sqrt(2)y)=1?
Guys, I just found another flaw in my method. I assumed, that x-2y=x+2y. But that came from the statement, that we either must have (-1)*(-1) or 1*1. But that statement came from the fact, that x-2y and x+2y have to be at least whole numbers because x and y are natural. But that doesn´t work, because I cannot show that x+sqrt(4)y is also natural unless I have proven that sqrt(4) is natural as well. So this is another circular argument inside my original argument.
So is the theorem discussed in this video at all usable for showing that sqrt(4) is rational? And if not, what could be a proof?
amazing content lately!! keep going with this good stuff!! :)
12:16
Nice stuff. I guess this can be generalized to other kinds of equations satisfied by n ?
Just use the continued fraction of the square root for the "non-trivial calculation!" (Wikipedia shows when's a "good place to stop" based on the periodic block length)
If the length is even, use convergent [length-1], and if it's odd, use convergent 2[length]-1. In other words use a palindromic section of the expansion, centered on a single number!
Here's the sequence (according to Wikipedia) of increasingly non-trivial values of N: (I'll call it d from here out)
d= 1, 2, 5, 10, 13, 29, 46, 53, 61, 109, 181, 277, 397, 409, 421, 541, 661, etc. (These are all such values d with less than 4 digits)
Alternatively, here's an arguably faster way to find the smallest non-trivial (x, y) pair: start with triples (a, b, k) and (m, 1, m²-d). Now compose these by spitting out triple (am+bd, a+bm, k(m²-d)) and divide out a k² if a+bm | k. Repeat composing this with (m, 1, m²-d) (and satisfying a+bm | k while minimizing what m is) until k=1. If you get to k= -1, just compose the triple with itself and you're good!
I've built an EXCEL spreadsheet that does these calculations for me, as I need them. (I love the Pell equations.). First real monster is:
2,143,295² - 94 * 221,064² = 1
but even that only takes 15 cycles of the continued fraction expansion, and remains within EXCEL's (quite limited) precision.
@@pietergeerkens6324 You say "n=94 is the first monster," so how many chakravala cycles is n=61? I haven't counted them before.
@@wyattstevens8574
Including Generalized Pell equations where the right hand side is ±1, which I believe appropriate, then:
29,718² - 61 * 3,805² = -1.
It's true that imposing the constraint of +1 on the right hand side gives a larger result for n=61; but that system is solved as soon as the fundamental unit of the ring is identified with a right hand side of -1.
@pietergeerkens6324 Right- I said above, "if you're on that specific general equation, compose it with itself and there you are!"
Okay. So n=61 requires 10 cycles to get a R.H.S. of -1, and n=94 needs 15 cycles to get a R.H.S. of +1 (but doesn't pass through -1 on the way since 15 is odd).
Simplest thing I could think up is the following:
1. The product of a natural A with itself is always a natural B.
2. Therefore the squareroot of any arbitrary natural B must be a natural.
3. However, all factors of B individually must necessarily be less than B in magnitude.
4. Now sqrt(1) = 1 since 1^2 = 1
5. But what is sqrt(2)?
6. The factors of 2 are 2 and 1, but neither 1^2 nor 2^2 equals 2, viz., 1^2 = 1 and 2^2 = 4 .
7. Conclusion: not all squareroots of naturals are naturals.
8. Every prime has no factors but 1 and itself.
9. Conclusion: no prime is the square of any two smaller naturals.
10. Every composite has a prime factorization of 3 or more prime factors (1 is a prime--fight me, I dare you).
11. sqrt(x) = x^(1/2)
12. Conclusion: for all prime factorizations x = \prod_{k=1} p_k^N for natural constant N and prime p_k, if N is divisible by 2, then x has a natural root, otherwise the root is non-natural.
13. sqrt(x/y) = sqrt(x)/sqrt(y) = (x^(1/2))/(y^(1/2))
14. the statement for prime factorizations above holds for x and y.
15. Conclusion: if an irreducible fraction of the form (x^N)/(y^(2M)), or (x^(2N))/(y^M)) is given, it cannot be a rational root.
16. not all square roots of naturals are naturals.
17. not all square roots of rationals are rationals.
18. Conclusion: the square root of any rational in which either its numerator, denominator, or both has an exponent not divisible by 2, then the square root of that number must be non-rational.
Implies generally that the Kth root of any rational for any N or M (as given in (15)) not divisible by K is non-rational also.
7:59 That was a pretty smooth edit!
I don't understand why the *first* assumption, namely that x^2 - ny^2 = 1 could not be the one that is false. I mean the order one makes claims is arbitrary. You could have started with the supposition that the square root of n in a/b and *then* the claim about x and y and 1. Then the x and y claim would be the false one.
It can be. Theorem which is proven in this video, says that if x²-ny²=1 with natural x,y,n, then √n is irrational. If this(x²-ny²=1) is wrong, then the theorem doesn't say anything about √n
x^2-ny^2=1 having a solution is the prerequisite condition of the theorem. It’s not an assumption that was added for the sake of deducing a contradiction
The minimal polynomial of sqrt(n) if n is not a square is p(x)=x^2-n. We know that x€Q if and only if x is algebric in Q and x is a root of a 1th degree polynomial in Q. So sqrt(n) if n is not a perfect square cannot be a rational number, because the polynomials that have this number as a radix have a degree greater or Equal than 2.
I love these proofs that stray off the beaten path.
What about the converse?
If k^2
You're using the fundamental theorem of arithmetic.
@@AlcyonEldara where? I suppose while proving rational roots theorem but I don't really see there fully using unique prime factorization
@@bartekabuz855 yes, example let's take the ring Z[a,b] with x² = -1 and y² = 2. X² - a has a root in Q(a,b) but not in Z[a,b]; (1+a)/b.
Proof: ((1+a)/b)² = (1 + 2a + a²)/b² = 2a/2 = a
The coefficients of X² - a are 1 and a, both are invertible (obiviously 1 . 1 = 1; and since a² = -1 we have a^4 = a . a^3 = 1). So if the rational root theorem applies, any root would be of the form "divisor of a / divisor of 1" but since both are units in Z[a,b], this root would also be in Z[a,b]. But here it doesn't work since 2.i = (1+i)² = sqrt(2)² . i
Is there an inverse proof? Meaning that x^2 + k^2 y^2 = 1 w/ k in N has no solution over N?
Nvm that follows directly with b = 1 in the proof, so x < 1, which is impossible.
9801² - 29*1820² = 1
How did we conclude x is less than b?
b²>bx (previous line in the video, b² on the left, bx on the right)
b > 0 (it is a natural number by definition)
b>x
Hello there! Can you please solve the Diophantine equation 3x^2 - y^2 = 2? Thank you in advance!
Whenever we have a proof that sqrt(n) is irrational, I always like studying the cases where it breaks - eg. the fact that sqrt(4) is clearly not irrational.
In the traditional proof by contradiction, the step that breaks in this case is the divisibility step; ie. n|a^2 => n|a. This is only true if n is not a square number.
Where does the logic in this proof break when sqrt(n) is not irrational?
You won't be able to find x,y for n=4.
That you can find x,y for n not a square is non-trivial (but true). If you pick a fixed n, you can find x and y by enough trial and error.
Btw, n | a ^ 2 does not imply n | a. Take n = 8, a = 4. Or n = 12, a = 6.
You need n to be square free. And I think you are now close to using unique factorization.
For n prime the traditional proof works without invoking unique factorization or something equivalent.
Does that cover all irrational roots?
X^2-nY^2=1 looks a bit like the equation of the hyperbole where a^2 is 1 and b^2 is 1/n
Here is a very short proof, using the structures of the subgroups of Z. For any integer n, define G as the elements x of Z such that x times the square root of n is an integer. G is a subgroup of Z. If we assume that the square root of n is rational, then G is not trivial. Then, there exists a positive integer b such that G=bZ. Define a=b times the square root of n. a is an integer, because b is in G. a times the square root of n equals b times n, and is therefore an integer, which means that a is in G. Recalling that G=bZ, we get that a is a multiple of b. Therefore, a/b, which is the square root of n, is an integer.
One of the assumptions was that a and b were minimal. But why can't a and b scale as much as you want so that b is always greater than whatever x value you have in the series which wouldn't then have the contradiction?
Yeah I wasn't sure if you could set up the definition of a and b in a way that would scale along with x sub n. Like a and b were always a sub n and b sub n where you multiply a sub 0 and b sub 0 by x sub n so you still have a numeric equivalency for the square root of n but you also keep x sub n less than b.
b is defined through sqrt(n) = a/b. n is a constant and thus a,b are constants as well (it doesn't even matter if a and b minimal). Now the contradiction is that we have an increasing sequence of natural numbers bounded above by the constant b, which doesn't work since there are only finitely many natural numbers less than b.
No, because a/b is a particular form. At the beginning of the proof, we are assuming that the fraction is expressed as a/b, where a and b are rational. The fact that there exists other representations are not relevant, for each representation we choose we can use the argument.
I have to look back in the video, but my impression was that this was not an assumption. I think at least the original intention of Michael is that you don't need to assume a to be minimal (and/or a and b to be coprime). It might be that he anyway mentioned something like that out of "habit" (since it pretty standard to pick a and b coprime, obviously).
It can be proven that sqrt(n) is rational n is a perfect square i.e. n = x² for some natural number x. Also, of course, n is taken to be a natural number here. Let's check it out.
Sps sqrt(n) is rational, in other words it can be written as a/b for some natural numbers a and b with gcd(a, b) = 1. This implies that also gcd(a², b²) = 1. Since sqrt(n) = a/b we have n = a²/b² and furthermore since n is a natural number and gcd(a², b²) = 1 it must be that b² = 1 => b = 1 => n = a², hence n is a perfect square.
Nice application of Pell's equation.
However, the regular proof of the irrationality of the square root of the prime number 2 does not use unique factorization (= fundamental theorem of arithmetic).
The proof works just fine in algebraic number fields in which unique factorization does not hold.
Which one is the "traditional" proof? I guess it's the one by infinite descent? A common quick one-line proof uses unique factorization:
sqrt(2) = a/b => a^2 = 2 b^2, which is impossible by unique factorization.
@@TheEternalVortex42 Yes, I would say that is the traditional proof. Take p = (a/b)^2 and show that you can find smaller a (and b).
But this proof works only if you know that p|ab implies p|a or p|b.
This is the definition of "prime number" in algebraic number theory, but if you start from the "normal" definition of a prime as a number divisible only by 1 and itself, then you still need to do some work. (I did not immediately realize this. On the one hand I know too much algebraic number theory and on the other hand this was all too long ago!)
I think the point of the video is to find a proof that does not require showing that p|ab => p|a or p|b if n=p is a prime.
Also, the proof works for composite numbers n, where unique factorization really starts to come in handy....
Finding x and y can be tricky, though 🙂
So.... yeah, I think Michael is essentially right about this proof at least staying further away from unique factorization.
Many thanks for your great videos❤❤❤
Don't we need to check that x_k, y_k are positive "integer" in this proof?
He gives an argument why x_(k+1) > x_k, and you start with x>0.
@@ronald3836 I know it is positive, but my point is "integer". The fact x_k < b is based on this assumption.
@@blackkk07 you start with x1,y1 positive integers, and by construction x_(k+1) and y_(k+1) are integers if x_k and y_k are. I don't know if Michael said this, but it follows immediately from the formulas.
So yes, it had to be checked, and yes, it is true that they are positive integers (which get larger and larger).
Pells Equation!!!
I know you didn’t use it, but even to say a/b in shortest terms you need to invoke fundamental theorem of arithmetic. Otherwise there will be multiple shortest options. You didn’t even need the fact it is shortest or a shortest exists
To prove, that the square root of any natural number k, which isn't the square of another natural number, it isn't the square of any rational number either: Let's assume, that √k=a/b, where a and b are natural and gcd(a, b)=1 (because it can). Then k=a^2/b^2 kb^2=a^2 a must be a multiple of k, so it can be expressed as kc, where c is natural. So we have kb^2=k^2c^2 b^2=kc^2, so b is also a multiple of k. Since k>1, gcd(a, b)>1 is necessary, which is a contradiction. This, of course, isn't limited only to square root, it also applies for root of any base bigger than 1.
You write :: kb^2 = a^2 => a is a multiple of k (k is not prime). Now kb^2 = a^2 => a^2 is a multiple of k. Does it automatically follow that a is a multiple of k (k not prime)?
I like using the rational root theorem to prove that all roots of non-perfect powers are irrational.
I personally like the proof that it is a repeating continued fraction
how i would prove:
suppose a/b is not an integer, and (a/b)^2 = N (an integer)
all we have to show is that if b does not divide a, then b^2 cannot divide a^2
I'm not sure I'm reading you correctly, but if a/b is not an integer, b does not divide a by definition. We can then write that a/b = c/d which is the fraction in its lowest terms, i.e. a=kc and b=kd and gcd(c, d) = 1. But then gcd(c^2, d^2) = 1 also, which shows that d^2 does not divide c^2. Hence k^2*d^2 does not divide k^2*c^2 which means b^2 does not divide a^2.
What might be even more difficult to prove this way is that square root of certain 20-digit number is not irrational. Fortunately there's always the constructive approach.
Need to prove that the pell equation x^2-ny^2=1 has a non trivial solution
Otherwise the seq of Xk is constant =1
He assumed a solution with x, y natural numbers. In Penn-speak, natural numbers start at 1.
The solution x=1 y=0 dose not generate other différents solutions
So he must algo prove that the pell equation has a solution with x >1
@@khaledbarbaria9544 He is assuming a solution exists with x, y≥1, which is therefore not the trivial solution.
He must * prove* that an initial solution s.t x>1 (or y>0) exists. This is true but not easy. Otherwise the proof is incomplete.
@@khaledbarbaria9544The claim is that, for a given value of n, IF we can find x, y∈N (which, for Michael Penn, means x, y≥1) such that x²-ny²=1, THEN √n is not in Q.
To apply the result for any particular value of n, one must then find such a non-trivial solution with x, y≥1.
Amazing!
There is theorem that says if p is prime then it's square root is irrational
There is a stronger result which is that if n ∈ ℕ is not a perfect square, then its square root is irrational.
A corollary is that the square roots of natural numbers are either integers or are irrational.
In algebraic number theory a prime number is defined as an integral number satisying p | ab => p | a or p | b. And k | n means that there is integral m with n = k * m.
This is valid in integral domains which have no unique factorization, so where the "fundamental theorem of arithmetic" does not hold.
Suppose the prime p is the square of a rational number, so p = (a/b)^2. Then a^2 = b^2 * p, so p | a^2. Since p is a prime, this means p | a. Therefore we can write a = p * c.
So b^2 * p = a^2 = c^2 * p^2 , which means b^2 = c^2 * p. So now we get p | b^2 and thus p | b, so b = p * d.
This gives us p = a/b = c/d.
If we go back to working in the natural numbers (i.e. the integral domain Z), we see that c < a, and if we make sure to pick a and b so that a is minimal, we have a contradiction.
So the regular proof works without using the fundamental theorem of arithmetic.
We can generalize the result to primes in algebraic number fields (where the integers are those numbers that are the roots of a polynomials x^n + a_n-1 x^(n-1) + ... + a_0 with a_i in Z) by chosing the numbers a and b such that the norm of a is minimal. The norm of an integral number is an integer, and the norm is multiplicative, so everything works as in Z.
So the proof does not only work without using the fundamental theorem of arithmetic, it even works in algebraic number fields in which the fundamental theorem of arithmetic does not hold.
Now what is left to show is that prime numbers in N ("numbers only divisible by 1 and themselves") are prime numbers in the sense of algebraic number theory. In general this seems to be close to proving unique factorization, but for a specific prime p I think you can just check all possibilities mod p.
I can prove it in one sentence : if n is a perfect square, then difference between two positive perfect squares can not be equal to 1 ( X^2 - n*Y^2=1), therefore n is not a perfect square, therefore n^(1/2) is irrational.
You'd need to prove that is q is a non integer rational number then q² isn't an integer. And you will use the fundamental theorem of arithmetic.
@@AlcyonEldara Assume q is a non integer rational number and q² is an integer. Set q=a/b, GCD(a,b)=1, and set q²=c, then a/b * a/b = c. This is possible only when a=b=1, but it is a contradiction. Then q² is also not an integer.
@@iljas275 "This is possible only when a=b=1"' prove it without using the fundamentgal theorem of arithmetic ...
@@iljas275 example: lets x = i and y = sqrt(2).
Z[x,y] = {a+b.x+c.y+d.x.y |a, b, c and d in Z}. You can prove that Z[x] is a ring. Remember that x² = -1 and y² = 2.
(1+x)/y isn't in this ring but is inhis fraction field Q(x,y). but ((1+x)/y)² = (1 + 2x + x²)/y² = (1 + 2i - 1)/2 = i = x is in Z[x,y].
You've correctly proven that n isn't a perfect square in a sense that n≠x² for all integer x, but you didn't prove that there is no such rational x, so √n may still be rational
This is a very interesting proof. But it makes me wonder about a more interesting idea... whether there is a way to prove that the square root of a non-perfect-square is rational. I'm not a formal number theory student, so I don't even know if such a thing exists... just thinking about it, I'm inclined to believe that if a natural number isn't a perfect square, then its square root must be irrational. I welcome feedback from any more serious (and undoubtedly better trained) mathematicians on this subject.
If a natural number is not a perfect square, then indeed its square root is non-rational.
Suppose n is the square of a rational number a/b. We can choose a and b to be coprime (i.e. they have no common divisor) by cancelling out any common divisors that they initially might have.
So n = (a/b)^2, which means a^2 = n * b^2.
Now suppose b > 1. Then you can find a prime p that divides b. (Primes are 2,3,5,7,.... so without 1.)
Since p divides b, it also divides n * b^2 = a^2.
This means that p also divides a.
But now a and b have p as a common divisor, which was contrary to our assumption that a and b are coprime.
So b = 1 and n = a^2 is a perfect square.
We want to prove, that in x^2-ny^2=1, where x and y are natural, n isn't the square of any rational number. Lets assume, that it is and that the value of ny^2 isn't an integer. Then x^2-ny^2 can't be an integer, because x^2 is and we have a difference of an integer and a non-integer. So ny^2 must be an integer. But then we're asking for 2 squares of integers with a difference of 1. There's only 1 option for that and it's when x=1 and ny^2=0. No other options exist. So to summarize, in the equation x^2-ny^2=1, where x and y are natural, if n=0, x=1 and y can be anything, while if (x, y)=(1, 0), n can be anything, including the square of a rational number.
0 isn't included in the natural numbers so Y cannot equal zero under the setup shown in the video
also ny^2 isn't necessarily the square of an integer, only y^2 is the square of an integer -(except for n = 1 or n = y^2 of course)- (unless n = some integer c^2, but this does not have to be the case)
@@supremedevice1311 0 is the most natural number.
@@supremedevice1311 Also, I just wanted to prove, that ny^2 has to be an integer, because such is x^2. I never said anythinf about ny^2 being the square of an integer. I don't know why you've brought it up, but those aren't the 2 only possible values of n such, that ny^2 is the square of an integer. n could be the square of any other integer. I think you should rewatch the video.
@@shockbladezed2352 you said you're 'asking for two squares of an integer with a difference of 1'
You're saying that ny² must be an integer, but this doesn't mean that ny² is a square of a natural number. You also need to also prove that n must be a square of an integer number
pretty cool
Why is using the Fundamental Theorem of Arithmetic bad?
Can you prove it without a contradiction?
Technically this is "proof by negation" not "proof by contradiction". It's the normal way to prove negative propositions.
@@TheEternalVortex42 I’m pretty sure proof by negation is a type of proof by contradiction. He assumed sqrt(n)=a/b, and constructed a sequence x_0
interesting; whose proof is this ?
Notice that we did not proof the reciprocal.
Pell equations
Why is it a good thing to not use the fundamental theorem of arithmetic? It's already been proven, it's free real estate.
It is unclear to me how this reasoning avoids the perfect squares (all of which obviously are rational).
If n is a perfect square, then x^2 - n y^2 = 1 has no solution. Because if n is a perfect square, e.g. n = q^2, then x^2 - n y^2 = x^2 - q^2 y^2 = x^2 - (qy)^2, i.e., the difference between two positive perfect squares. But the difference between two positive perfect squares is never equal to 1.
or you just use the rational root theorem on the equation x²-n=0
But does the proof of that theorem use the fundamental theorem of arithmetic? (Probably not, but I am not 100% sure.)
If you know algebraic number theory, then you know that solutions of the equation x^2 - n = 0 are integral by definition of "integral".
If they are also in Q, they have to be in Z. And clearly there is no integer in Z which multiplied by itself gives 2.
The traditional proof of the irrationality of sqrt(2) applied to primes in number fields works fine, even if the ring of integers of the number field has no unique factorization.
But I am now wondering if perhaps somewhere in the basics of algebraic number theory we use the fact that Z has unique factorization...
I must be tired or stupid, or stupid tired. Lost me around the 6 minute mark. #FeedTheAlgorithm
Nice n beautiful
There are definitely proofs of this result that do not use the fundamental theorem of arithmetic nor are equal to your approach, Michael.
It feels like there are a lot of mistakes around the 4 minute mark
Feel free to state them, there are none
@@shadow-ht5gkOh! It looked like the expression said b^2-… instead of b^2=… The factorization wasn’t making sense to me.
11:51 that means 37 is irrational 🤔
This symbol means "such that": ∋