A number theory proof
Вставка
- Опубліковано 2 кві 2018
- Find integer solutions a^2+b^2=4c+3 , a number theory proof or disproof.
💪 Join our channel membership (for as low as $0.99 per month) to unlock several perks, including special badges and emojis during the livestreams: / @blackpenredpen
🏬 Shop math t-shirt & hoodies: teespring.com/stores/blackpen...
10% off with the code "TEESPRINGWELCOME10"
Equipment:
👉 Expo Markers (black, red, blue): amzn.to/2T3ijqW
👉 The whiteboard: amzn.to/2R38KX7
👉 Ultimate Integrals On Your Wall: teespring.com/calc-2-integral...
---------------------------------------------------------------------------------------------------
My guess is that the people you teach face to face, have no idea how lucky they are.
Thank you!!!
Thank you for doing these, they are fantastic and I just love your style.
@IonRuby Was that to me?
At the point you showed a2 + b2 = 4(k2 + l2 + l) + 1 My thoughts went this way:
a2 + b2 = 4c + 3
a2 + b2 = 4(k2 + l2 + l) + 1
4(k2 + l2 + l) + 1 = 4c + 3
4(k2 + l2 + l) = 4c + 2
k2 + l2 + l = c + 1/2
Since k and l are integers, (k2 + l2 + l) is an integer, but since c is an integer, c + 1/2 CAN'T be an integer, so there is no solution.
Tony James Me too! Anyone know if this is a valid solution as well? Seems so to me.
It is a correct and valid solution.
Tony James that is also ok!
Oh, now I get it. Thanks!
Couldn't a = 0 b = 0 and c = -3/4
Can you do more number theory?
mathninja 62703 will try!
Yes please
I agree! bprp should have more number theory.
Yes!
I'd like to see more number theory as well!
For any integer x, x=0,1,2,3 modulo 4. If x=0 or 2 (mod 4), the x^2=0 (mod 4). If x= 1 or 3 (mod 4), the x^2=1 (mod 4), so the square of any integer is 0 or 1 modulo 4. Thus a^2,b^2 is either 0 or 1 module 4. So their sum is at most 2 module 4. If a^2+b^2=4c+3, then a^2+b^2=3 (mod 4), which is not possible. Thus we have no integer solutions.
styzon That's what I was thinking, too.
Same
My first intention too.
Had the same thoughts.
By the way, it's modulus, mod for short (maybe you don't care, but maybe you aren't quite sure)
@@santiagoarce5672 it's definitely modulo, modulus is used in a little different syntax
That's fantastic! I did it basically the same way, except I did more algebra and worked it down to
2(k^2+l^2+l) = 2c+1
And then, I noticed that my left side was even and my right side was odd, so I concluded that there were no solutions. Going straight for the mod-4 observation was pretty slick!
Just saying, any integer squares are either 1 or 0 mod 4, so this proof is easy if u know that.
Oh yes, high school olympiad way of expressing it. Year10, I believe, it was.
If you know anything about quadratic residues this fact is pretty immediately obvious. a^2 + b^2 = {0,1} + {0,1} (mod 4) = {0,1,2} mod 4 != 3 (mod 4)
Consider 3 squared plus 3 squared. This sum is 18 which is congruent to 2 mod 4, so your assertion is wrong. You can show that this is the case for many other pairs of odd numbers.
@@NerdKing9826 He said that any integer squares(referring to one integer squared) are congruent to either 1 or 0 (mod 4), using the rules of modular arithmetic we can thus conclude that the sum of any 2 integer squares is congruent to either 0, 1 or 2 (mod 4) which means that a^2 + b^2 cannot be equal to 4c + 3 (where a,b,c are integers) since 4c+3 is congruent to 3 (mod 4).
Also the proof for his assertion is quite simple. There are two cases that needs to be considered, case 1: even integer and case 2: odd integer.
Let k be a positive integer
Case 1:
(2k)^2 => 4(k^2) which is congruent to 0 (mod 4)
Case 2:
(2k+1)^2 => 4k^2 + 4k + 1 => 4(k^2 + k) + 1 which is congruent to 1 (mod 4)
Hope this helped! :)
@@antrose99 you're right, but he said integer squares, not an integer squared or squared integers. I think what you're proving is what he meant, but I didnt read it that way. 👍
I used modular arithmetic. When an integer n ≡ 0 or 2 (mod 4), n^2 ≡ mod 4; when n ≡ 1 or 3 (mod 4), n^2 ≡ 1 (mod 4). Then the sum of two integer squared can be congruent to mod 4, 1 (mod 4), or 2 (mod 4), but not 3 (mod 4). Therefore, a^2 + b^2 can't be equal to 4c+3 if a,b,c are all integers. Mod made it pretty simple and it took me only two minutes lol
Hey, same! I figured it in like a minute though.
From where would you suggest starting to learn number theory?
Ah! I just posted the same!
"a is 2k, not like the 2k18 for the basketball games, but 2k" 😂
Yup1!! You got my reference!!!
dang u r so good at math and u r making me love math!! i am in algebra 2 honors, and my teacher was working out that problem you had about sqrt of i and it was EXACTLY what you did so i was like HMMMMMM
hehehe
I highly recommend your math videos to my friends. Yeah!
Your videos are fantastic, keep them up!
once he wrote the 4(k^2+L^2+l) +1 i was like "awwwwww". It looks so obvious once he points it out but at the start I'm just wondering what the heck to do. Love the video.
Suppose integer solutions exist, then take the congruence mod 4
a^2 + b^2 = 3 mod 4
But then mod 4 squares can only equal 1 or 0 (you can prove this by computation). That means that a^2 + b^2 can only be 0, 1 or 2 mod 4. Not 3. A contradiction. Thus, no solutions exist.
leoitshere you can prove that by euler's theorem...for overkill
The hypothesis that integer solutions exist did not need to be asserted.
This has been a good start for my number theory journey.
Or directly, since (k^2 + l^2 + 1) is an integer, denote it as d.
Then
4d^2 + 1 = 4c^2 +3
4d^2 = 4c^2 +2
d^2 = c^2 + 1/2
Since d, c and their squares are all integers, they cannot differ by 1/2.
A touch of number theory. Thank you.
I found another way to show it's not possible before looking at your solution, but yours is way more short and elegant :)
Interestingly, there is a solution for the equation:
a²-b² = 4c+3
In the case where a=2k and b=2l+1, a²-b² becomes:
4(k²-l²-l)-1 which we can re-write as 4(k²-l²-l)+(3-4)
And rearranging this yields 4(k²-l²-l-1)+3
Therefore letting c = k²-l²-l-1 we find that a²-b²=4c+3
Could you do Galois theory and number theory?
you're my favourite maths youtuber hands down
Different approach: consider both sides of the equation mod 4, ie. (a^2 + b^2) mod 4 = (4c + 3) mod 4.
Note that for any x, it can be decomposed as 4y + z, where z in {0,1,2,3}, and therefore x^2 mod 4 = (16y^2 + 8yz + z^2) mod 4. However, the r.h.s reduces to just z^2 mod 4. Since z in {0,1,2,3}, z^2 in {0,1}.
Therefore, (a^2 + b^2) mod 4 is in {0,1,2}.
However, (4c + 3) mod 4 = 3.
From here, since 3 is not in {0,1,2}, we can conclude that there is no solution.
One key trick I find for integer equations is to use modular arithmetic to eliminate variables. In this case, I used mod 4, because I knew that it would eliminate the variable c.
Great video! I myself am currently taking an undergraduate elective for my graduate degree in mathematics, so this video is timely and a good test of what I’ve learned. (Like you, I examined the possible solutions for "a-squared + b-squared", modulo 4.)
Also - unrelated - I want to thank you, BlackPenRedPen, for featuring one of my comments at the end of your Brilliant.org symmetric integral video back in November. These past months have been particularly busy for me, and a frustration I have is that I don’t have as much time as I would like to watch your videos. Consequently, I didn’t realize my comment was featured until a couple days ago.
But I’m almost done with my graduate degree, and I will finally be able to get back to doing math for-math’s-sake. Thanks again and keep making great videos!
Also, you’re almost at 100k subs! Yay!!
Wow, this might be the first one of the problems from this channel that I’ve gotten right!
Impossible by modulo
L.H.S congruence 0,1,2 (mod4)
R.H.S congruence 3 (mod 4)
This is great!!!
You could use Euclid's division lemma :)
Seems the prove of Fermat's Theorem. I like it, nice to see !
What is the name of the song played at the end of the video??
Wait... so if it was 4c+5 instead, there would be a solution?? (Or at least 4c+(4n+1))
Oon Han yes. We can take c=5 and we can get 3^2+4^2=4(5)+5
Different odd-even pair of a & b values have a corresponding c, so there are infinitely many solutions. But are there any kind of types of 3-variable equations with one unique solution of a, b and c i.e if a where changed there would be no corresponding values of b and c that could satisfy the equation. The closest I've found is:
a^2 + b^2 + c^2 = 35
I believe that(so long as a,b,c ∈ ℤ) it has only 2³ triples of solutions -> {1, 3 and 5}, where any of them could be their negative counterparts. I got it from places with more equations to be solved simultaneously so as to obtain a unique solution, e.g.
a + b + c = 1 | a + b + c = 7
a^3 + b^3 + c^3 = 97 | a^3 + b^3 + c^3 = 151
{5, -3, -1} | {5, 3, -1}
etc.
I wonder however if 2 additional equations are necessary, as I think just 1 is sufficient. And if so, then why are only 2 equations needed to solve a set of simultaneous equations and not 3. I was thinking it's perhaps because they aren't linear. Anyway, can number theory answer this question?
There’d be a solution for every positive integer c
*every c where 4c+5 is prime and I think some where it’s not
More generally a^2 + b^2 = 4c + (4n + 1) will have solutions no matter the n because c can always change. a^2 when a is odd equals 4v + 1 and b^2 when b is odd equals 4g^2 which gives, 4v + 1 + 4g^2 = 4(c + n) + 1 subtract 1 from both sides, 4v + 4g^2 = 4(c + n) subtract 4(c + n) from both sides, 4(v + g^2 - c - n) = 0, v + g^2 = c + n which has infinite solutions.
Very useful techniques to verify possible results
I didn’t pause the video. I’m just here to enjoy the show.
cool. Do more number theory pls !
Pretty simple: an even number 2a squared is 4a2=4(a2)=0 mod 4, while an odd number 2b+1 squared is 4b2+4b+1= 4(b2+b)+1=1 mod 4, so a square mod 4 is either 0 or 1. Therefore, the sum of two of them mod 4 is either 0 (0+0), 1 (0+1), or 2 (1+1). None of these are 3, so the sum of two squares can never be equivalent 3 mod 4, and the equation has no solutions.
What would it mean for solution, if question would say 4c+1 instead of 4c+3 on lhs and so both of them would be 4 mod 1 at the end?
Simply divide both sides by 4 and you will get different remainders o both sides , therefore no integral solutions are there for a,b,c.
this is amazing. thanks
Simple solution. Because either a or b must be odd and the other must be even, you can only adjust each of them by steps of 2. The difference between two squares that are separated by two is a multiple of 4 (four times the number between them, specifically), so if 1²+2²≠4C+3, then no solutions exist.
I want more like this
I subtracted 4c + 3 to the other side.
a^2 + -(4c + 3) + b^2 = 0
Once you have that, the inly way for that to factor and have solutions is for -(4c +3) = 2ab. From there (a + b)^2 = 0. a = -b.
Subbing in to the original equation, 2b^2 = 4c + 3
b^2 = 2c + 3/2
The right hand side of the equation is not an integer so therefore there are no solutions since b^2 must itself be an integer.
The sum of two distinct squares gives a number of 4N+1 type. The RHS is a number of 4M+3 type. Therefore they can never be any pair of integers N and M for which the equation is valid.
1:43 by using which thing? Thanks.
My idea would be that every odd square is a-1* a+1 +1 that means either a+1 or a - 1 is divisible by 4(every second even number is) and a2 is therefore 1 greater than a multiple of 4.
The even square needs to be 2 greater than a multiple of 4 because we will add both squares. But every even square is divisible by 4 because we multiply two even numbers and their factors include at least one 2 from each. The even square number has at least two 2s as factors and therefore is divisible by 4.
Very nice little problem
hey bprp, what is a number with two decimal points, and does it make sense?
excellent lesson.
I personally enjoyed the video. It was very clear and especially for people like me who are just entering the realm of number theory.
As always, there will be one or two who'll miss the point all together. It is not unusual for some spectator to think he can play soccer better than the actual player. Moreover, there's that category of an observer who looks at the pointing finger rather than the object (moon) being pointed at.
KEEP UP THE GOOD WORK!!!
Certainly a great lesson in really learning to examine a problem and easy enough to explain after you've given us the answer. But it was an answer that made me realize that if I'd actually examined the problem I could have figured it out. A great lesson.
After all at its core it was about using simple logic with regard to number theory (the product of any two numbers is always even and the sum of any even number number is an odd number). Even != Odd.
Thanks for the great video. :-)
Sir you gave a great explanation. But I have a suggestion. You should present some hard problems rather than elementary ones.
But if your goal is to help maximum peolple then you are doing a great job.
More number theory videos please!
My solution take :
Take mod 4
sun of squares cannot leave ramainder 3
No solution
Use congruency on 4.
A square is always congruent to 0 or 1 on 4.
0^2=0
1^2=1
2^2=0
3^2=1
(0,1)+(0,1)=3 is impossible (mod 4)
Would it be easier to try mod4?Since all squares are either 1 or 0 mod4
Using mod 4 a and b can be 0,1,2 or 3. Squaring these give u 0,1 (2^2 = 4 = 0 and 3^2 = 9 = 1 using mod 4)
So the left hand side can only be 0,1 or 2 but the right hand side is 3
Excellent video 👍
Well you're looking for the sum of 2 squares to be 3 mod 4 but it's impossible because a square is either 0 or 1 mod 4 (0 mod 4 stays 0 when squared, 1 stays 1, 2 becomes 0 and 3 becomes 1). So the sum of 2 square can only be 0,1 or 2 mod 4.
Awesome!
Is it not trivial since every square = 0 or 1 modulo 4, so the sum of two squares is in the set {0,1,2} modulo 4 while the RHS = 3 modulo 4?
a^2 + b^2 = 4c+3 has no integer solutions since we know that a^2 + b^2 = c^2 has integer solutions. substituting c^2 into the original equation gives c^2 = 4c+3, which has no integer solutions for c.
not sure if this makes sense but it was my first thought
Please never stop making videos
Where do you teach?
a^2 + b^2 - 3 = 4c
(a^2 +b^2 -3)/4 = c
Then plug in values for c to be 1, 2, 3 etc. and you'll the a pattern in what a^2 + b^2 end up being, which you'll write as an arithmetic progression. And like in the video there will be a 2 remainder.
Could u do a segment on chinese remainder theorem with application so we can praise oriental mathematics.
Muslym1 Ghumman
I am actually planning to do so.
What I did was added 2ab to bkth sides. Seeing that either a or b has to be even we can write any one of these as 2q.
So,
(a+b)^2=4(c+1+qb)-1
[since, 3=4-1]
Then,
As,
(a+b)^2 is either of the form 4c or 4c+1. (Proved by using euclids division lemma on 2 and any integer a).
It has no solutions.
Woah thank you.
"Integer" is a noun, "integral" can be both a noun and an adjective. When used as an adjective, it is used to describe a group of numbers that only consist of integers. When used as a noun, it means the result of integration. "Integer solutions" and "integral solutions" are both grammaticality correct but the latter sounds more like natural English.
Quadratic residues modulo 4 are 0 and 1, which basically proves it.
Martin P Sometimes in Mathematics you will be requested to do such proofs, especially at the university level, and it will take more than 10 minutes.
Beautiful.
Great. Number theory. Variety is awesome.
If you write down the Caley table for Z4, you see that n^2 mod 4 is either 0 or 1. So a^2 + b^2 mod 4 can only be either 0, 1, or 2, but NOT 3.
You can also use congruences to solve this problem. We know that each square is congruent with 0 or 1 mod 4. So you"ll have the next three cases.
1) That a^2 and b^2 are congruent with 0 => The sum is congruent with 0
2) That one of them are congruent with 0 and the other with 1=> That the sum is congruent with 1.
3) Both squares are congruent with 1 mod 4. And so we"ll have that the sum is congruent with 2.
In neither case we have that sum of squares are congruent with 3 and so we can conclude that their isn't a,b,c integers such that a^2 + b^2 = 4c+3
I love number theory!
Can you bring something more advanced? Because this could be done easily with mod 4, as other comments claim. I was thinking of a proof for Fermat Little Theorem os something.
Thanks for your videos
What a best lesson. It seems will be great and so much fun to be your student. ☺☺☺
It's actually really simple! By the Pythagorean theorem a^2+b^2=c^2 so you get the equation c^2=4c+3 move to the left hand side you get c^2-4c-3=0
and the solutions are c~4.65 and c~-0.65 which are not integer solutions thus proving that the equation
a^2+b^2=4c+3
Has no integer solutions..
(this is a joke btw)
Hello ! There is an easy way to prove it, so just make sure the left side give us reminder 0,1, or 2 and right side give us reminder 3, so we got contradiction.That it. Thank you.
n^2 always takes the form 4k or 4k+1: there are no solutions.
Another way to show this is not possible is subtract 1 to both sides. Then, divide out 2 on both sides. You have 2 * (expression) = 2 * c + 1. Call expression an integer p. Now you have 2p = 2c + 1, which is a contradiction. Since, an even # doesn't equal an odd #.
C=1/4, a=b=2^(1/2)
4=4
I paused the video when you said, I solved quickly and then I watched the rest of the video. And... I have nothing else to share. I did it exactly the same way. I even also used the letters k and l. No prize for originality for me. :(
Maks Rosebuster oh wow that's kinda cool that we used the same letters.
@@blackpenredpen I feel like it's kinda common to use the letters k, l and so on when you're doing modular arithmetic. Just a feeling though.
Maks Rosebuster Thus you can sue BpRp for copyright infringement. 😆
I added 2ab to both sides:
a^2+2ab+b^2=4c+3+2ab
The left side is now a perfect square:
(a+b)^2=4c+1+2ab
Then I subtracted ab from both sides:
(a+b)^2-2ab=4c+1
We have two cases:
(a+b)^2 is even:
even+2ab is still even but 4c+1 is always odd, so (a+b)^2 cannot be even
(a+b)^2 is odd:
an even plus an odd is the only way to be an odd number
This means either a or b is odd
So 2ab is divisible by 4, and I will call it 4d
Now if (a+b)^2 is odd, then a+b is odd, and (2x+1)^2 = 4x^2+4x+1= 4(x^2+x)+1
Then we have 4d + 4(x^2+x)+1 is a multiple of 4 plus 1 but not a multiple of 4 plus 3 so (a+b)^2 cannot be odd
Therefore it cannot be an integer
I simply thought
4c + 3 = 3 (MOD 4)
a = 0,1,2,-1 (MOD 4)
a^2 = 0,1,0,1 (MOD 4)
No way to add two of these such that it equals 3 so
a^2 + b^2 ≠ 4c + 3
I just said that 4c+3 is a prime in the Gaussian integers, as proved by Euler, yet a^2+b^2 can be factored into Gaussian integers a+bi and a-bi, so they cannot be the equal with a,b,c £Z
Any one tempted to use Pythagoras when you saw a^2 + c^2 ????
We know a^2 + b^2 = c^2 so
c^2 = 4c + 3
c^2 - 4c - 3 = 0
which does not have integer solutions...
》wink《
True River but a^2+b^2 doesn't always equal c^2 tho
True River That’s cool. At least you’re thinking like a maths scientist. Great going.
blackpenredpen True. But he also is saying if it has a c^2 solution, then it wouldn’t be a 4c + 3 format. For a,b,c integers.
I took this as a modulus question: find a^2 (mod 4) = 1 and b^2 (mod 4) = 2
After brute forcing the first 12 squares, I couldn’t find the latter, and thus I conclude my proof
Weird strategy that is
Like these types of videos teaches abstract thinking
1:42 was a reference to Mathologer?
Andy Arteaga it's a well known thing tho. I googled it.
blackpenredpen I didn't mean any offense! Just wondering if you were a Mathologer viewer!
Oh no Andy, I didn't feel offended. In fact I have heard that Simpsons joke many times in the past (usually when the fermats last theorem was brought up). I actually have seen many of his videos. They are great!
Easy one. Just by consideration modulo residue classes you immediately get a contradiction.
For those interested to know what can be done with this, please take a look at Fermat's Christmas Theorem.
My thoughts:
A and B mustn’t both be odd or even.
Let’s say a is even. A^2 is divisible by 4, which can be canceled by the 4c
All odd numbers are either expressible as (4x-1) or (4x+1)
(4x+1)^2 = 16x^2 + 8x + 1
(4x-1)^2 = 16x^2 - 8x + 1
16x^2 and 8x both can be canceled by 4c
So I eventually get to “1 = 4c + 3”, which is impossible if C must be an integer
I would just show that all squares mod 4 are either 0 or 1 mod 4. But I might have to explain modular arithmetic. And fermats little theorem on the side.
曹老师姿势渊博呀，讲的一首好高数的前提下涉猎到了初等数论
尽管这道题本身简单，直接mod4就行了
The solution is actually pretty similar to the proof of √2 is irrational.
If you get into number theory proofs you'll notice that there are plenty of proofs by contradiction, and out of those, there are many done by using the concept of divisibility, since it's so useful.
My solution (before watching the video): Take the entire equation mod 4. Then a² + b² = 3 (mod 4). So the only possible inputs to this equation are 0..3, since it is a mod 4 equation. And order does not matter since the LHS does not change if you swap the assignments for a and b. So I looked at all possible pairs of numbers mod 4 with a
Thanks! We would think this way of solution did cost you years and again years of your life time. All possible pairs. And you are already done? Impossible. Unless you happened to forget a couple of them.
And in the case I'm misunderstanding you, please could you show which pairs you did explore and how.
BLACKPENREDPEN i had not understood the modulo therem before watching your video,now i know
Sir please suggest me some elementary well renowned number theory book for primary knowledge.
I remember this proof using ring theory proved using Wilson's theorem.
My solution:
The right side will always be odd, so the left side needs to have one even and one odd square. a = 2x, b = (2y - 1)
4x^2 + 4y^2 - 4y + 1 = 4c + 3
1 = 3 (mod 4)
which is a contradiction, so no such numbers exist.
It was a good idea to use modulo operator to prove that the given equation has no integral solution.
Substitute c squared for a squared plus b squared and solve for c.
I solved it using mod 4:
a mod 4 = 0 => a^2 mod 4 = 0^2 = 0
a mod 4 = 1 => a^2 mod 4 = 1^2 = 1
a mod 4 = 2 => a^2 mod 4 = 2^2 = 0
a mod 4 = 3 => a^2 mod 4 = 3^2 = 1
We can see that the only results we get with a perfect square mod 4 are 0 & 1, we need (a^2+b^2) mod 4 to be 3, but the maximum we can get to is 2.
Hence why it's impossible to find any integer solutions for a^2+b^2=4c+3.
I'm confused, wouldn't a = 0, b = 2, c = 0.25 work or am I missing something?
Oh, right
I immediately just looked at each side's remainders when dividing by four.
Any perfect square can only leave a remainder of 0 or 1.
Therefore the LHS leaves a remainder of 0, 1 or 2, but the RHS leaves a remainder of 3.
Thus, the answer is no.