A very classic number theory problem
Vložit
- čas přidán 4. 08. 2024
- Suggest a problem: forms.gle/ea7Pw7HcKePGB4my5
Please Subscribe: czcams.com/users/michaelpennma...
Merch: teespring.com/stores/michael-...
Personal Website: www.michael-penn.net
Randolph College Math: www.randolphcollege.edu/mathem...
Randolph College Math and Science on Facebook: / randolph.science
Research Gate profile: www.researchgate.net/profile/...
Google Scholar profile: scholar.google.com/citations?...
If you are going to use an ad-blocker, considering using brave and tipping me BAT!
brave.com/sdp793
Buy textbooks here and help me out: amzn.to/31Bj9ye
Buy an amazon gift card and help me out: amzn.to/2PComAf
Books I like:
Sacred Mathematics: Japanese Temple Geometry: amzn.to/2ZIadH9
Electricity and Magnetism for Mathematicians: amzn.to/2H8ePzL
Abstract Algebra:
Judson(online): abstract.ups.edu/
Judson(print): amzn.to/2Xg92wD
Dummit and Foote: amzn.to/2zYOrok
Gallian: amzn.to/2zg4YEo
Artin: amzn.to/2LQ8l7C
Differential Forms:
Bachman: amzn.to/2z9wljH
Number Theory:
Crisman(online): math.gordon.edu/ntic/
Strayer: amzn.to/3bXwLah
Andrews: amzn.to/2zWlOZ0
Analysis:
Abbot: amzn.to/3cwYtuF
How to think about Analysis: amzn.to/2AIhwVm
Calculus:
OpenStax(online): openstax.org/subjects/math
OpenStax Vol 1: amzn.to/2zlreN8
OpenStax Vol 2: amzn.to/2TtwoxH
OpenStax Vol 3: amzn.to/3bPJ3Bn
My Filming Equipment:
Camera: amzn.to/3kx2JzE
Lense: amzn.to/2PFxPXA
Audio Recorder: amzn.to/2XLzkaZ
Microphones: amzn.to/3fJED0T
Lights: amzn.to/2XHxRT0
White Chalk: amzn.to/3ipu3Oh
Color Chalk: amzn.to/2XL6eIJ
Thank you for a number theory problem that doesn't involve working in mod N!
12:50
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.
those aint even prime bro
@@bregottmannen2706 I know but in other problems Michael does the answers are often small numbers
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.
Absolutely. It’s really simply amazing
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 ...
@@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
@@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".
Very cool question indeed.
Rewatching this again. Such great a video, Prof P! 👍👍
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…
He's got a math degree and he's been doing it a long time.
+These are standard oly techniques.
Practice a lot?
Just do math from competitions. They are very similar to these ones.
number theory, mate. Look such books up
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.
Thanks for your hard work and good videos 😊
Thanks for the fun videos! Love from Serbia❤️
Did he mean "integer solutions" in the second hint? If not, someone pls explain i'm lost..
He did.
An integral solution is one that all the unknown variables take only integer values.
@@Grizzly01 ah ok thank you!
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
@@schweinmachtbree1013 But understanding this is not integral to solving the problem in the video. :)
@@schweinmachtbree1013 That is not always true. Integral does not always means an integer. But in this case it does.
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.
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
12 is a square in Z(square(3)). 12=(2*square(3))^2
Amazing problem, nice vid
This was a good one
Beautiful!
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.
I'm not sure guess and check would be accepted though, because you haven't proved the uniquess of the solution.
You're the best!!
Beautiful question
I love your videos
Only one solution, very satisfying!
Plz make some log, e & trigonometry problems too.
Amazing
brilliant.!!!
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 CZcams. Thanks and Sorry for bad english
Greatest !
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.
1 is not prime
@@seroujghazarian6343 Well, yes, and you just exclude the p=1 solution for that reason.
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
Even good thing is if we replace p with any natural number, still the question is doable
My heart is filled with joy . Very good method of finding prime number p . God bless you .
Wow!
If ever it merited a backflip it was here.
Would you rather be good at backflips or math?
Michael Penn : Yes
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
Bruh I don't understand what the question is this 🤣🤣🤣
My guts tell me it’s 3/4
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
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?
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)
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
Number theory is some of my favorite math
I used the same factoring, but decided to show that n^2+n+1=0 has no integer solutions.
This video was nuts
Nice video!
2:24 is it also possible, that (p-1) divides one of A or B?
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.
Trop beau :-)
Why are the videos getting more and more silent? I can't turn the volume up anymore.
Thats exactly how i did. Fact that p is prime is helps a lot for the solution l.
whats going on with the audio in the last vids?
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
i wish there was 2:1
Nice
Is there an explanation/proof for the second hint anywhere? I feel a bit stupid for not understanding it.
integral solution = interger solution
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
4:16
can anybody explain the proof to the homework part at 9:14
@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.
New question, what primes make that prime?
Good Place To Start At 1:27
what does he mean by integral solutions ?
I have a better question. Which cubes make that prime?
RJ
It might look like an odd question, but it can actually be represented by p^2 - p^1 + p^0
Wgy do you describe many of those numbers as perfect?
Perfect number, a positive integer that is equal to the sum of its proper divisors
Someone know why only check n as a variable, and no the other case (n as a constant)?
It leads to the same solution.
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.
10:43
We can put an X next to it.
Proceeds to put an *
Awesome video though
Someone needs to increase the circumference of the lotion distribution 😄
...unless p | GCD(a,b) in which case p | a AND p | b.
Very good 19
at 2:58, how is pn^3, p cannot be smaller than n.
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
That was his point
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.
AMOGUS!
You should check your answer
C, D, E, F, G, A, B
Period.
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-CZcamsrs 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.
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.
What did he do just after 7:48? I'm lost
Also, Why did he choose to make that stuff less than D?
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
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.
@ henk -- You left out that you "bound it between two *consecutive perfect* squares."
@@thiagozanfolin9349 can you explain the proof for why D
@@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!
There’s some kind of unpleasant high frequency buzzing in the video.
I was close. My guess was 23.
find all integers "x" such that x² + 4 is a cube
(x,y) = (±2,2) or (±11,5).
Yeah, you're gonna need this.
Aren't 0 and 1 primes?!? Someone explain
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.
0:52 what is integral solutions? is it supposed to be integer?
They mean the same thing
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).
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.
p can have at most two distinct values for each cube. Not overall.
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.
@@jeffreykornhauser9063
What I have proven is that there are no more possible solutions.
@@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.
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.
p = 1
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.
4 isn’t a prime
p = 19
I want to send you a problem
use the google form in the description
email him, I used the google form and never worked, but if I emailed, he did all of the videos(including this one)
@@helo3827 Can I get his Email address....? 😀
Stated more formally:
If a quadratic polynomial has integral solutions, then its discriminant is a perfect square.
The converse is not true.
"If a quadratic polynomial _with integer coefficients_ has integral solutions, then its discriminant is a perfect square"
would be more correct
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.
@@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
@@skylardeslypere9909 This is perfect! Well done
p^ = 17 | 17 + 1 = 18 | 17^ = 289 | 289 - 18 = 271 | the square root of 271 = 90 which is a perfect cube. 🔥🔥
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.
The unadvised felony surgically subtract because bar bodily welcome a a sleepy link. tart, jumpy passbook
Damn that’s trippy