Thank you for a number theory problem that doesn't involve working in mod N!
@TheEyalYemini3 жыл бұрын
Where do you learn this stuff? I am able to follow the explanation but I feel I would never be able to do this by myself…
@romajimamulo3 жыл бұрын
He's got a math degree and he's been doing it a long time.
@TechToppers3 жыл бұрын
+These are standard oly techniques.
@hexa33892 жыл бұрын
Practice a lot?
@dalibormaksimovic63992 жыл бұрын
Just do math from competitions. They are very similar to these ones.
@spiderjerusalem4009 Жыл бұрын
number theory, mate. Look such books up
@mcwulf253 жыл бұрын
Excellent stuff. The cherry on the cake was a solution p=19. So often there is no solution, or the solution is 0 or 1.
@bregottmannen27063 жыл бұрын
those aint even prime bro
@mcwulf253 жыл бұрын
@@bregottmannen2706 I know but in other problems Michael does the answers are often small numbers
@synaestheziac3 жыл бұрын
Great problem. I especially like how it can be solved using only high school math but would be very challenging for all but the strongest high school math students.
@cryfan68283 жыл бұрын
Absolutely. It’s really simply amazing
@praphael2 жыл бұрын
It could also be solved by anyone who knows how to program, although you do not prove there are no solutions beyond a certain p, in practice on a question like this there won't be any for a "sufficiently large" p, probably < 100. von Neumann might have taken that approach, but using his head and not a calculator ...
@tollspiller20435 ай бұрын
@@praphael well, no, it could not be "solved" because "solving" requires proving that those are the only solutions, simply stating "probably p < 100" would get 0 points on any exam
@praphael5 ай бұрын
@@tollspiller2043 I wasn't suggesting thats what you would put on the exam. But if you were given this problem on an exam, where you were only allowed pen and paper, its extremely unlikely that there would be solutions beyond about p > ~100, probably even much smaller. The reason is because prime numbers cannot be generalized by a simple formula, which is part of what makes them so interesting. So if the answer were something like "infinitely many" with some restrictions to a certain class of primes, I would be hard pressed to come up with some closed form formula for actually generating them. And for very large prime, again it would be difficult for even good mathematicians to find them without the aid of a computer Lastly if you want to get technical, the question only asks you find them, not for a proof uniqueness. So I would definitely take issue with the "zero points".
@samuelmarger90313 жыл бұрын
Very cool question indeed.
@goodplacetostop29733 жыл бұрын
12:50
@isaacwalters7473 жыл бұрын
A problem I would love to see you tackle, or maybe even a special case: The product from n=1 to N of (3+1/(a_n)), where each a_n is greater than 1 and of the form +1 or -1 modulo 6, is never an integer power of 2. The N=2 case is easy to show, as the product is bounded below and above by (3^2, 4^2), or (9,16), and there are no powers of two on that open interval.
@ChefSalad3 жыл бұрын
That second fact is missing a caveat. It's only true for polynomials with integer coefficients (I think only integers, anyway). For example, take x²+(2+2√3)x+1+2√3=0. One of it's roots is x=-1, an integer, but Δ=12, which is not a perfect square.
@reeeeeplease11782 жыл бұрын
It should work if a,b,c are integers as you said since applying the quadratic formular and splitting the fraction leaves you with int/int + sqrt/int If you want this to be an integer (or even just a rational), the sqrt has to equal an integer As such, the discriminate has to be a perfect square
@elkincampos38042 жыл бұрын
12 is a square in Z(square(3)). 12=(2*square(3))^2
@darksecret9657 күн бұрын
@@elkincampos3804 abstract algebra to the rescue
@goblinkoma3 жыл бұрын
Did he mean "integer solutions" in the second hint? If not, someone pls explain i'm lost..
@Grizzly013 жыл бұрын
He did. An integral solution is one that all the unknown variables take only integer values.
@goblinkoma3 жыл бұрын
@@Grizzly01 ah ok thank you!
@schweinmachtbree10133 жыл бұрын
yup, "integral" is also an adjective meaning "which is an integer". so you could say that integral integrals are definite integrals from calculus whose values are integers :D
@dominickmancine60333 жыл бұрын
@@schweinmachtbree1013 But understanding this is not integral to solving the problem in the video. :)
@sayaksengupta43703 жыл бұрын
@@schweinmachtbree1013 That is not always true. Integral does not always means an integer. But in this case it does.
@perappelgren9483 жыл бұрын
Rewatching this again. Such great a video, Prof P! 👍👍
@MyOneFiftiethOfADollar3 жыл бұрын
If you examine the original discriminate of 4n^3 - 3, it is a perfect square for n=7 which also leads to p=19. So guessing and testing works which happens to be not so time consuming in this case.
@praphael2 жыл бұрын
I'm not sure guess and check would be accepted though, because you haven't proved the uniquess of the solution.
@mrl94183 жыл бұрын
This was a good one
@ijuhat193 жыл бұрын
The last part is a lot simpler if you just use p = mn - m + 1; setting m = 3 and n = 1 or 7 gives you p = 1 or 19 respectively.
@seroujghazarian63432 жыл бұрын
1 is not prime
@ijuhat192 жыл бұрын
@@seroujghazarian6343 Well, yes, and you just exclude the p=1 solution for that reason.
@ianloree27843 жыл бұрын
Only one solution, very satisfying!
@manucitomx3 жыл бұрын
Wow! If ever it merited a backflip it was here.
@Tiqerboy3 жыл бұрын
Would you rather be good at backflips or math? Michael Penn : Yes
@АртемДараган-л1п3 жыл бұрын
Thanks for your hard work and good videos 😊
@bktreesdoesmc89573 жыл бұрын
May have found a different(but a little convoluted) way to solve the problem but with a similar idea. From p|n^2+n+1, we also have (n-1)|(p-1). Hence, p-1=k(n-1) and p>k(n-1). But we also have n^2+n+1>=p. Hence, n^2+n+1>=p>k(n-1). Thus, n^2+n+1>k(n-1), and hence (n^2-(k-1)n+k+1)>0, where k and n are natural numbers. Consider the equation n^2-(k-1)n+(k+1)=0 For this equation to have no real roots (i.e, n^2-(k-1)n+(k+1)>0 is true for all real numbers(and hence natural numbers n), we must have D
@satyapalsingh44293 жыл бұрын
My heart is filled with joy . Very good method of finding prime number p . God bless you .
@markohorstmann96373 жыл бұрын
Thanks for the fun videos! Love from Serbia❤️
@sarthak66053 жыл бұрын
Even good thing is if we replace p with any natural number, still the question is doable
@jordanweir71873 жыл бұрын
Amazing problem, nice vid
@matteoanoffo14473 жыл бұрын
You are Great. If you have to repost some old videos in a Better way i think you should make some algebra wich Is hard to find on KZbin. Thanks and Sorry for bad english
@pianochannel1002 жыл бұрын
Number theory is some of my favorite math
@__zenon3 жыл бұрын
Why are the videos getting more and more silent? I can't turn the volume up anymore.
@luisfelipe73512 жыл бұрын
a=Log[10,n/(n+1)]-Log[10,x/(x+1)] = n= prime x= position , a=0.12*Pi/x very close so having a we can have for a given prime the position n by NSolve
@dblaze233 жыл бұрын
10:43 We can put an X next to it. Proceeds to put an * Awesome video though
@joaomatheus2942 жыл бұрын
Beautiful question
@romajimamulo3 жыл бұрын
If you're going to stick with wider than 16:9, upload it without a black bar at the bottom so people with wider screens can appreciate it
@Alex-ff8si3 жыл бұрын
i wish there was 2:1
@beautifulworld61635 ай бұрын
Thats exactly how i did. Fact that p is prime is helps a lot for the solution l.
@paulgillespie5422 жыл бұрын
I used the same factoring, but decided to show that n^2+n+1=0 has no integer solutions.
@alonsoal64203 жыл бұрын
Beautiful!
@goodplacetostop29733 жыл бұрын
HOMEWORK : A tightrope walker stands in the center of a rope of length 32 meters. Every minute she walks forward one meter with probability 3/4 and backward one meter with probability 1/4. What is the probability that she reaches the end in front of her before the end behind her? SOURCE : Guts Round of HMMT 2003
@pardeepgarg26403 жыл бұрын
Bruh I don't understand what the question is this 🤣🤣🤣
@Thaplayer12093 жыл бұрын
My guts tell me it’s 3/4
@sirgog3 жыл бұрын
I like this problem. HINT: GP2S's choice of a power of 2 was deliberate. SOLUTION (not rigorous, this is an outline): Consider which occurs first: reaching 2 steps forward, or 2 steps back. After 2 steps, she is 9/16 to be 2 forward, 1/16 to be 2 back, and 6/16 to be back at the start. However if she is at position 0 (the centre), we can simply repeat this process. Note that Pr(she hovers near the centre for an indeterminate amount of time) approaches 0. This makes her 9/10 to reach +2 first, 1/10 to reach -2 first. Call a sequence of moves which continues until the walker ends up two steps forward or backward a second order move. Repeat this argument to see which occurs first: +4 or -4. See she is 81/82 to reach +4 first, 1/82 to reach -4 first (81/100 to reach +4 after 2 second order moves, 1/100 to end up -4 after 2 second order moves, 18/100 to return to the origin in which case we do 2 more second order moves). This is a third order move. Repeat third order moves to see which comes first: +8 or -8. 6561/6562 to be +8, 1/6562 to be -8 Repeat and see she's 3^16/(3^16 + 1) to reach +16 before -16. TL:DR - don't play rigged casino games
@sjoerdo69883 жыл бұрын
My solution: We represent the possible positions by values of n from 0 to 32, such that n=0 represents the location of the end behind her, and n=32 represents the end in front of her. Currently, she is at n=16. Let pk be the probability of reaching n=32 before reaching n=0, starting from n=k. Clearly p0=0, and p32=1. For any value k from 1 to 31, it holds that: pk=1/4*p(k-1)+3/4*p(k+1). This, together with the boundary conditions results in p_k=(1-(1/3)^n)/(1-(1/3)^32). The probability of reaching the end before the start from n=16 is then (1-(1/3)^16)/(1-(1/3)^32), which is approximately 0.99999998. Is this answer correct?
@romajimamulo3 жыл бұрын
Nearly 1. 9^8/(9^8+1) I computed this by starting with the fact after two moves, you're either at +2, 0, or -2 from where you started. You can then move all the "probability of reaching the top" terms from your current position to see the probability in terms of going 2 up or 2 down. Then, you repeat the process, doubling the recursion formula until you get the probability of going 16 up or 16 down (and not stopping till you reach one of those)
@somasahu12342 жыл бұрын
Amazing
@curiosityxxx43053 жыл бұрын
Plz make some log, e & trigonometry problems too.
@HGCFGHFHJ2 жыл бұрын
I MAY HAVE BETTER ONE AS IF U CAN SEE AT 2:16 after splitting gcd of n-1 and n2+n+1 term has gcd 1 or 3 by edl n2+n+1=n-1*n-2 +3 >gcd of (n-1,n2+n+1)=(n-1,3) staement of edalgorithm if u take their gcd as 1 u can simply equate p=n2+n+1 and p-1 to n-1 as p and p-1 also has gcd 1 it gives no soln now if take gcd 3 then put n=3m+1 then u have got 9 as common then remaining has gcd 1so take p=3m2+3m+1and p-1 as 9m get m=2 >n=7>p=19 i may have missed out some steps but if u r old learner u can think of it for this soln u need betyter understanding of gcd and edl and eda
@EternalLoveAnkh2 жыл бұрын
I have a better question. Which cubes make that prime? RJ
@blackmagicprod70393 жыл бұрын
This video was nuts
@KarlDeux2 жыл бұрын
Also, p cannot divide n-1 because n-1 is even. p is not 2, so p is odd, so p²-p+1=n is odd as well.
@alaechoulli61113 жыл бұрын
You're the best!!
@garydetlefs60952 жыл бұрын
I love your videos
@goodplacetostart90993 жыл бұрын
Good Place To Start At 1:27
@utsav89813 жыл бұрын
What did he do just after 7:48? I'm lost Also, Why did he choose to make that stuff less than D?
@thiagozanfolin93493 жыл бұрын
So most of the times that you get an expression and wants to see if it is a perfect square(ps),you can try fitting It between to consecutive ps because if that happens,you are done.So,he noticed that for every m,Dq^2
@henk77473 жыл бұрын
In order to show something is not a perfect square you can bound it between 2 squares. For example if you know 16 < x < 25, it's clear that x can not be a square.
@robertveith63833 жыл бұрын
@ henk -- You left out that you "bound it between two *consecutive perfect* squares."
@MrAmangandhi3 жыл бұрын
@@thiagozanfolin9349 can you explain the proof for why D
@thiagozanfolin93493 жыл бұрын
@@MrAmangandhi for sure! So we have D0 The discriminant is 0. Just make the graph of 2m^2 -4m +7 and you will notice it imediatally!
@jarikosonen40793 жыл бұрын
It looks kind of luck that p=19 prime number, but it looks proven there is no other ones... I hope I can learn something about this, even possibly not ever needed.
@mcwulf252 жыл бұрын
...unless p | GCD(a,b) in which case p | a AND p | b.
@farklegriffen26243 жыл бұрын
New question, what primes make that prime?
@crep503 жыл бұрын
It might look like an odd question, but it can actually be represented by p^2 - p^1 + p^0
@Oskar-zt9dc3 жыл бұрын
whats going on with the audio in the last vids?
@77Chester772 жыл бұрын
Nice video! 2:24 is it also possible, that (p-1) divides one of A or B?
@akanegally2 жыл бұрын
no it's not useful because p-1 is not necessarly a prime. Only the prime factors of p-1 divides one of A or B.
@peterquartararo32493 жыл бұрын
brilliant.!!!
@stevenmellemans72153 жыл бұрын
Someone needs to increase the circumference of the lotion distribution 😄
@peeyushagarwal58893 жыл бұрын
at 2:58, how is pn^3, p cannot be smaller than n.
@oliverherskovits79273 жыл бұрын
This inequality is due to the divisibility argument. If a number divides another number, the divisor must be less than or equal to the multiple (if both are positive). What u noticed is essentially the contradiction he builds next
@bonjour72092 жыл бұрын
That was his point
@Smilesallnightlong3 жыл бұрын
Is there an explanation/proof for the second hint anywhere? I feel a bit stupid for not understanding it.
@Nnm263 жыл бұрын
integral solution = interger solution
@johnthevampire8192 жыл бұрын
If p=4 a=2 and b=2 then we have that 4|2*2 but 4|2 is false. Correct me if I am wrong but it seems that one of the facts doesn't work all the time.
@synaestheziac2 жыл бұрын
4 isn’t a prime
@davidbrisbane72063 жыл бұрын
We could hope that p is a small prime and try p = 2,3,5,7,11,13,17,19 etc and stop when we find a value of p that satisfies the equation p² - p + 1 = n³ where n ∈ ℤ⁺. As p² - p + 1 = n³ is a quadratic equation in p, then we know that p can have at most *two* distinct real values. When we get to p = 19 by the trial and error approach, then p² - p + 1 = 343 = 7³. So p = 19 is a solution, and it is pime. As we have found one real value satisfying the quadratic, we know that the other value (root) satifying the quadratic is real too. Now we need to find the other value to the quadratic and check if it is prime or not. Now let (p - 19)(p - a), where a ∈ ℝ and So, (p - 19)(p - a) = p² - p - 342 where a is the other root of the quadratic. Now, (p - 19)(p - a) = p² - (19 + a)p + 19a = p² - p - 342 So, 19a = -342 and 1 = 19 + a So, in either case, a = -18 is the other real solution and it is *not* prime. Hence, the only value of p being prime resulting in p² - p + 1 = n³ is p = 19.
@ogasdiaz3 жыл бұрын
p can have at most two distinct values for each cube. Not overall.
@jeffreykornhauser90633 жыл бұрын
This is not correct. Quadratics do have at most 2 real solutions, but n can be any positive integer here. So really, all you essentially did was prove that n=19 and n= -18 are the only real solutions to the quadratic equation p^2-p+1=7^3. But what about p^2+p-1=8^3, p^2+p-1=9^3, so on and so forth.
@davidbrisbane72063 жыл бұрын
@@jeffreykornhauser9063 What I have proven is that there are no more possible solutions.
@davidbrisbane72063 жыл бұрын
@@ogasdiaz I'll need to check by supposing we found another cube value, say m³, such that p² - p + 1 = m^3 leads to a different set of solutions. Although, having said that, Michael proved in the end that there was only two possible value of p such that p² - p + 1 is a cube and only one of these was prime.
@stephenbeck72223 жыл бұрын
David Brisbane Michael found 4 values of p possible: -18, 0, 1, and 19, only one of which was prime. But there are surely more values of p to solve the original expression, since he used the primeness of p very early in the proof to restrict the relationship between p and n.
@tubamazouz3 жыл бұрын
Greatest !
@Max-sg5tz3 жыл бұрын
Hello guys, I am asking you for advice: With his videos, Michael got me really interested in mathematics (or better: solving mathematical-olympiad type of questions). But as a newbie, I don't have all these different types of "tricks" in my repertoire, so I am often unable to solve them. I have started creating a list with all the different tricks/methods that Michael and the other Math-KZbinrs use, and it has been really helpful, but it will take ages to complete it. Do you have any literature tips (also websites) where these "mathematical tricks" are illustrated in a systematic way? Any other pieces of advice to make quick advances in math are also welcomed. Thanks in advance.
@davidbrisbane72063 жыл бұрын
You can buy books on Putnam problems & solutions. They tend to be a bit expensive, but they usually teach you the techniques you need to solve competition problems.
@Douae11115 ай бұрын
what does he mean by integral solutions ?
@MrAmangandhi3 жыл бұрын
can anybody explain the proof to the homework part at 9:14
@rosiefay72833 жыл бұрын
Wgy do you describe many of those numbers as perfect?
@sjs2605633 жыл бұрын
Perfect number, a positive integer that is equal to the sum of its proper divisors
@HoSza12 жыл бұрын
C, D, E, F, G, A, B Period.
@particleonazock22463 жыл бұрын
AMOGUS!
@tommasomarchioni21333 жыл бұрын
Aren't 0 and 1 primes?!? Someone explain
@TayTaaay3 жыл бұрын
A prime number is divisible by itself and 1 so a prime number has 2 divisors. When we look at 0 then we can find that 0 is divisible by all real numbers (besides itself of course) because there is atleast one q such that 0.q = 0 therefore we know that 0 has infinite divisors. For 1 we know that it only has one divisor, namely just 1 itself. In order for 1 to be a prime number it has to have 2 divisors but it doesn’t so 1 is not prime.
@kenbrohere3 жыл бұрын
I was close. My guess was 23.
@Reliquancy3 жыл бұрын
There’s some kind of unpleasant high frequency buzzing in the video.
@Calculus58 Жыл бұрын
You should check your answer
@rodrigojose33693 жыл бұрын
find all integers "x" such that x² + 4 is a cube
@davidbrisbane72063 жыл бұрын
(x,y) = (±2,2) or (±11,5).
@frankrentt22253 жыл бұрын
Someone know why only check n as a variable, and no the other case (n as a constant)?
@eetswalads55283 жыл бұрын
It leads to the same solution.
@andraspongracz59963 жыл бұрын
Nice one. In fact, it would have been more precise to emphasize that p is a POSITIVE prime. That is a big extra condition that you make heavy use of. I think the problem can be fully solved without that extra condition as well. My first idea when seeing the expression p^2-p+1 was to use Eisenstein numbers (Eulerian numbers), as p^2-p+1=(p+w)(p+w^2) with w being a primitive third root of unity. I think it works, there are a number of cases to check (like 18 major ones), but they all lead to relatively simple systems of equations to solve. The main point is of course that p+w and p+w^2 are either coprime or their gcd is sqrt{-3}=1+2w, which is an Eisenstein prime. So either p+w is a cube of an Eisenstein integer multiplied by an Eisenstein unit, or the same goes for (p+w)(1+2w) and (p+w^2)/(1+2w) or the same goes for (p+w^2)(1+2w) and (p+w)/(1+2w).
@helo38273 жыл бұрын
4:16
@alainbarnier19953 жыл бұрын
Trop beau :-)
@rogeriojunior9459 Жыл бұрын
Very good 19
@vishalramadoss6682 жыл бұрын
Nice
@jiyoungpark62333 жыл бұрын
p = 1
@holyshit9223 ай бұрын
p = 19
@tonmoybhowmik86703 жыл бұрын
I want to send you a problem
@aahaanchawla53933 жыл бұрын
use the google form in the description
@helo38273 жыл бұрын
email him, I used the google form and never worked, but if I emailed, he did all of the videos(including this one)
@tonmoybhowmik86703 жыл бұрын
@@helo3827 Can I get his Email address....? 😀
@kenbrohere3 жыл бұрын
Yeah, you're gonna need this.
@arimermelstein91673 жыл бұрын
Stated more formally: If a quadratic polynomial has integral solutions, then its discriminant is a perfect square. The converse is not true.
@skylardeslypere99093 жыл бұрын
"If a quadratic polynomial _with integer coefficients_ has integral solutions, then its discriminant is a perfect square" would be more correct
@kingkartabyo62063 жыл бұрын
This partial converse is true: if a monic quadratic with integer coefficients has a perfect square discriminant, it has both roots integer. It simply means ax^2+bx+c=0 with b,c integers, a=1, and of course D=b^2-4ac is square.
@skylardeslypere99093 жыл бұрын
@@kingkartabyo6206 the (pseudo)proof is kinda fun to think about. We know that b and b² have the same parity. Also b²-4ac has the same parity as b² (and thus) b because 4ac is even. Since sqrt(b²-4ac) is an integer, it ALSO has the same parity as b. Now, either b and sqrtD are odd, making their sum/difference even, which can be divided by 2a = 2, resulting in x1 and x2 integers. If b is even, then -b±sqrtD is obviously even, making x1 and x2 integers. QED
@kingkartabyo62063 жыл бұрын
@@skylardeslypere9909 This is perfect! Well done
@olau54783 жыл бұрын
0:52 what is integral solutions? is it supposed to be integer?
@seanziewonzie3 жыл бұрын
They mean the same thing
@playgroundgames36673 жыл бұрын
p^ = 17 | 17 + 1 = 18 | 17^ = 289 | 289 - 18 = 271 | the square root of 271 = 90 which is a perfect cube. 🔥🔥
@robertveith63833 жыл бұрын
You have many errors in that line. I do not know why everything was typed on one line. There are missing characters, run-ons, and/or incomplete/false statements.
@nguyenthanh-tm6dz3 жыл бұрын
The unadvised felony surgically subtract because bar bodily welcome a a sleepy link. tart, jumpy passbook
@synaestheziac2 жыл бұрын
Damn that’s trippy
@davidbrisbane72063 жыл бұрын
@Stephen Beck I put a bit more work into the solution and solved it with a different approach. Solve p² - p + 1 = n³, where p and n are integers. I.e. It is not assumed here that p is prime. So, p² - p + (1 - n³) = 0 So, if we are to have any hope that p is an integer, then we require the discriminate D say to be an integer. Now D² = 1 - 4(1 - n³) So, 4n³ = D² + 3 Now let n = x/4 and D = y/4, then 4n³ = D² + 3 becomes x³/16 = y²/16 + 3 So, x³ = y² + 48. This is a Mordell equation with known solution in integers of (x, y) = (4, 4), (4, -4), (28, 148) and (28, -148). This equates to the solutions (n, D) = (1, 1), (1, -1), (7, 37) and (7, -37) for the equation 4n³ = D² + 3 Now p² - p + 1 = n³ with D² = 4n³ - 3 So, p = (1 ±D)/2 Now, if ±D = 1, then p = 1 If ±D = -1, then p = 0 If ±D = 37, then p = 19 If ±D = -37, then p = -18. These are the *only* integer values for p satisfying the equation p² - p + 1 = n³. So, the only prime value for p is p = 19. A point or two to note about this approach is that it doesn't assume p is prime. So, we lose the power of p being prime in the analysis, but we find all integer solutions for p, which happen to be the same ones Michael found, but his approach does not guarantee that he will find them. In his analysis, the non-prime integer values he found are really extraneous solutions. Of course, the above approach relies on a Mordell equation result, which I have not proven here.