Too hard for the IMO? Too easy?

[@videolome]

Nice problem, thank you, Michael. Here is a solution using matrices. Let A be the matrix (0 1 0) (0 0 1) (-1 0 3) Then the characteristic polynomial of A is p(x)=x^3-3x^2+1. This implies that if a,b,c are the three roots of p(x), then a^n+b^n+c^n=trace(A^n) (an integer, for all n) By Cayley-Hamilton, we have that A^3-3A^2+I =0, where I is the 3x3 identity matrix. It is possible to see that A^1988= u A^2+ v A+ w I, where u,v,w are integers. In fact, A^1988 == 14 I+16 A+9 A^2 mod 17 If we let N=1988, then a^N+b^N+c^N=trace(A^N)==trace(14 I+16 A+9 A^2 )==1 mod 17. The rest is just like Michael's solution.

[@MichaelPennMath]

This is a very nice approach!!

[@Risu0chan]

Amazing, Hector! Two questions: how do you find a matrix that fits the polynomial (usually one goes the other way, calculating its charac polynomial from a matrix), And how do you calculate A^1988.

[@videolome]

@@Risu0chan there is something called the companion matrix that does that. Check it out in Wikipedia. To do the computation, I used Mathematica. PolynomialMod[PolynomialRemainder[p[x],q[x],x],17] Where p[x_]:=x^1988; q[x_]:=1-3 x^2+x^3;

[@Risu0chan]

@@videolome Ah, interesting and useful.Thank you :)

[@toomanyhobbies2011]

Sweet.

[@jerrysstories711]

This problem reminds me why I'm a mathematically competent scientist and not a real mathematician.

[@prithujsarkar2010]

lol

[@leif1075]

Why do you say that? And doesn't it make you feel bad?

[@kidzbop38isstraightfire92]

Agreed. My engineering background did not show me how to solve this problem lol.

[@jbtechcon7434]

Wow, yes do check out his channel! Very cool! I've been binging! Thanks for the recommendation.

[@jerrysstories711]

@@jbtechcon7434 Thanks! Glad you enjoyed! :-)

[@debayuchakraborti1963]

I love how problem-solvers say "easy to see" even if it is very hard to notice

[@numbers93]

if you mean the part where he talks about the largest root being between 2 and 3, it comes straight from calculus. The function is strictly increasing to the right of sqrt(2).

[@NickiRusin]

well yeah, it's really hard to notice, but after that it's easy to see!

[@prithujsarkar2010]

this problem was kind of brutal (solution looks easy but hard to think of so many things at once) . polynomials , functions , number theory all in one packet

[@jkid1134]

Pretty easy to see x^3 outgrows 3x^2 past 3 lol

[@kristianwichmann9996]

@@jkid1134 Since we later find there's two other real roots, this is not really needed.

[@goodplacetostop2973]

24:18 Loading 98.2%... So close! Have a lovely Sunday, Michael and you all!

[@vaibhavnanchahal4173]

If you divide 24:18 with 24:20 isn't that 99.86%. Unless of course you're implying something different which I am very curious to find out.

[@goodplacetostop2973]

@@vaibhavnanchahal4173 Loading 98.4%... Please have a look at the number of Michael Penn’s subscribers.

[@vaibhavnanchahal4173]

Of course! 😅

[@Aramil4]

Can someone explain what this is about? Just curious

[@numbers93]

The justification of the congruence equality at 19:40 is unclear and I think actually requires a lot more proof. It certainly does not seem immediate from the facts currently established.

[@numbers93]

After some additional thought, I conclude that it really is not immediate. The proof the congruence equality is not terrible or particularly long, but it feels off having it skipped over considering the carefulness and amount of rigor shown in the rest of the video

[@lambdcalculus]

I feel like just saying it would be allowed in the competition. But for teaching purposes I think it might indeed be better to justify that. edit: by the way, the justification that I am using to convince myself is that 4, 5 and 11, mod 17, satisfy the symmetric sums identities satisfied by alpha, beta and gamma. since alpha^n + beta^n + gamma^n mod 17 can be represented as a function of those sums, then setting that equal to 4^n + 5^n + 11^n is justified.

[@avz1865]

Yeah, it isn't necessarily a complicated justification, but I wouldn't call it obvious.

[@CauchyIntegralFormula]

Yeah, this congruence does the bulk of the work in this problem, so it definitely needs to be justified carefully, and it just... isn't. You'd lose some points on the IMO for not justifying that step

[@speedsterh]

This is the part of the vid I have the most trouble with

[@vinc17fr]

I haven't looked at the video yet, but this is similar to Binet's formula for Fibonacci numbers. Applying the idea for x³−3x²+1, and reducing mod 17 gives a sequence of period 16, so that u[1988] ≡ u[4] ≡ 69 ≡ 1. Then since 1988 is even, α^1988 is slightly less than u[1988], so that floor(α^1988) = u[1988] − 1, which is divisible by 17.

[@b0redguy329]

How Is this familiar?🤔

[@michael169chapman]

I solved almost the same way but with a slight change at the end. The sum of n powers of roots is exactly the formula of the n'th term of the recursion sequence starting from a0=3,a1=3,a2=9 and defined by taking thrice the previous term minus the term three positions from the current. You can check manually that mod17 it has a period of 16 and that a4=1

[@laszloliptak611]

For 5:48: x^3-3x^2+1=x^2(x-3)+1, so if x>3, then both terms are positive.

[@larsdahl5528]

Yes, I saw that one too. (That was the easy part of this!)

[@christopherrice4360]

I love seeing extremely difficult math problems get solved.

[@Stelios2711]

The observation of the congruence between the sum of the roots and the roots in the finite field F_(17) was pure gold!

[@williammauriciogiraldomuri9855]

I am not being able to fully understand this (it is probably because I don't have any background in field theory). Would you mind please explaining it to me?

[@An-ht8so]

@@williammauriciogiraldomuri9855 I think that the idea is that a^n+b^n+c^n has an expression in terms of a+b+c, ab+bc+ac and abc, that doesn't depends on wether you're in R or F17, because your working with integers coefficients regardless, that naturally projetcs in F17. In turn these three expressions have the "same value" wether a b and c are the real roots or the F17 ones, because they are given by the coefficients of the polynomial. I'm not sure how I would go about writing it rigorously so this may be wrong, but I couldn't make sense of it otherwise.

[@charlesbrowne9590]

Thanks for all the great (!) videos. You have very good handwriting, which is an underrated quality for a mathematician. Decades ago, when I was in school, I used to do my math(s) homework in ink. Not because I never made a mistake, but always because I needed to see what I was doing. I also pepper my speech with “OK” and “great”. You eschew cliche thinking.

[@monikaherath7505]

These problems are really interesting but they make me feel like a worthless subhuman. I feel like a mathematical insect compared to these IMO gold winners.

[@raffaelevalente7811]

It's like watching Bolt running 100 m. in 9"58, while normal people usually take their cars to ride more than 10 meters... :)

[@andreasraab5294]

Nein, bloß nicht wortless fühlen!

[@MyOneFiftiethOfADollar]

I feel that way sometimes, but remember the IMO competitors often have an immense amount of preparation time wise and also working through the problems from previous competitions. They know what type of problems to expect.

[@carstenmeyer7786]

I used a variant of Hector Lemeli's great solution that can be done by hand without much computation: *p(x) = x^3 - 3x^2 + 1 = (x - a) (x - b) (x - c)* and *s_n := a^n + b^n + c^n* With *p(0) = 1* we know none of the three roots can be zero, so we calculate: *n in Z: 0 = a^{n-2} * p(a) + b^{n-2} * p(b) + c^{n-2} * p(c) = s_{n+1} - 3s_n + s_{n-2}* Reordering yields the recursive relation called "Newton's Identity". We get the initial conditions by comparing coefficients of *p(n)* , just as Michael Penn did at 13:16 : *s_{n+1} = 3s_n - s_{n-2}, s_{-1} = 0, s_0 = 3, s_1 = 3* We try to find a period within " *s_n mod 17* ", so we use the recursion above to calculate the first few terms. We stop as soon as we notice a repetition of three consecutive terms (we need three, because the recursion order is three): *s_n mod 17: 0, 3, 3, 9, 7, 1, 11, 9, 9, 16, 5, 6, 2, 1, 14, 6, 0, 3, 3, ...* The period length is *16* . With *1988 = 142 * 16 + 4* we have *floor(a^{1988}) = s_{1988} - 1 = s_4 - 1 = 1 - 1 = 0 mod 17*

[@tomatrix7525]

Another really great problem. Amazing content at the moment from you Michael!

[@danmarino900]

Can someone please explain to me at 20:00 how he made the jump to saying that “alpha^{2n} + ... = 4^{2n} = ... (mod 17)”? been staring at this for 10 straight minutes i have no idea why that follows

[@danmarino900]

@@angelmendez-rivera351 i think i understand. can you tell me if this explanation is correct?: Let S(a,b,c)=a^{2n}+b^{2n}+c^{2n}”, which is a symmetric polynomials and can thus be expressed as a polynomial *in the* elementary symmetric polynomials. Also, (x-alpha)(x-beta)(x-gamma) or (x-4)(x-5)(x-11) when expanded is a polynomial in x whose coefficients are *all of the elementary symmetric polynomials of degree

[@mcwulf25]

Glad you wrote that. I got that far too.

[@petersievert6830]

@@danmarino900 I stumbled upon the same, so very thankful for your question and Angel's answer. What helped me to grasp it a little bit better, when I realized that due to the polynomials being the same, thus: alpha*beta*gamma == 4*5*11 mod 17 ; alpha*beta + alpha*gamma + beta*gamma == 4*5 + 4*11 + 5*11 mod 17 alpha + beta + gamma == 4 + 5 + 11 mod 17 and thus alpha^2n + beta^2n + gamma^2n will be written in the respective equivalent terms mod 17 like 4^2n + 5^2n + 11^2n and as each for the terms is the same mod 17, so must their result.

[@ronritekinamatigai]

I solved it in a slightly different way, without factoring in F_17 Let a[n] = α^n+β^n+γ^n. Then from x^3=3x^2-x^0 it follows that a[n+3]=3a[n+2]-a[n] Values a[0,1,2] are easy to calculate from the symmetric polynomials: 3,3,9. Thus, we both proved that a[n] is integer for every n, and have easy formula to calculate next a[n] Direct calculation shows that modulo 17, the sequence of a[n] is periodic with period 16: a[n]=(3,3,9,7,1,11,9,9,16,5,6,2,1,13,6) Then a[1988]=a[4]=1

[@d.o.584]

Now, if we can show that the period must be 16 (some extension of Fermat's theorem) that would be really cool.

[@ronritekinamatigai]

@@d.o.584 I guess, that won't be so easy. It is related to the fact that matrix [[0,1,0],[0,0,1],[-1,0,3]], that encodes the recurrence relation for a[n], is diagonalizable in F_17, and proving this requires factorization of its characteristic polynomial x^3-3x^2+1

[@primenumberbuster404]

@@d.o.584 tbh, you can reduce all that 16 calculations to only 3 calculations. by FLT, the maximum period less than 17 is 16. so the minimum period has to be a positive multiple of 16 other than 16 which is 2,4,8.

[@conovan5081]

Great stuff, discovered your channel recently, in love with it! I do give some tries to the problems but don't go that far... yet!

[@anonymous-in5fp]

I might be wrong but for large value of n beta^2n+gama^2n is tending to zero hence floor of alfa^2n is equal to alfa^2n

[@limerent]

that was really cool

[@andy_in_colorado7060]

I like being able to “almost” follow along, and really appreciate every video. I love math and wish I had been more disciplined when younger.

[@asklar]

the fact that a^n+b^n (...+c^n etc) can be written as a polynomial g_n(x,y) on x=ab, y=a+b is pretty cool! it's obv trivial for n=0 and n=1 (it's g_0 = 2, g_1(x, y) = y^2-2x) You can prove this then by [strong] induction: a^(n+1) + b^(n+1) = (g(ab, a+b) - b^n) . a + (g(ab, a+b)-a^n) . b = g(ab, a+b) . (a+b) - (a . b^n + b . a^n) = g_n(ab, a+b) . (a+b) - a.b. (b^(n-1) + a^(n-1)) so g_(n+1) (ab, a+b) = g_n(ab, a+b) . (a+b) - ab . g_(n-1) (ab, a+b) which is a polynomial in only ab and a+b! :)

[@wannabeactuary01]

AT 6:05 f'(x) = 3x^2 - 6x >0 for x>3

[@vishalmishra3046]

In such cubic problems, all roots (real or complex) are computable. For example - IF { x^3 + 3mx = 2n } THEN { x = [ n + √(n^2 + m^3) ] ^ (1/3) + [ n - √(n^2 + m^3) ] ^ (1/3) }. Therefore, 1/x = 2 cos(120°/3 = 40°) since n = -1/2 and n^2 + m^3 = -3/4. So, α and γ are quadratic roots computable from β = sec(40°)/2. Simplify and the 3 roots are (α = 2.879385241571817, β = 0.6527036446661393, γ = -0.532088886237956). Note that the theorem is true for all 3 roots of the equation (and not just the largest root α ).

[@nathanisbored]

i feel like i learned a lot from this one problem O.O

[@s4623]

20:38 Question says 1988! and then they magically changed at the next board.

[@pikkutonttu2697]

I have had a dabble on many problems on this channel with success time to time. However I quickly came into conclusion that this was way beyond my capability. I tried to use Vieta's formulas, but I lacked a proper idea to follow thru. I also tried some recurrence ideas, but that came to a halt very quickly also. A fascinating solution!

[@JB-ym4up]

Mathematician: 3/8 Engineer: 9.5 mm

[@adandap]

This particular cubic gives nice answers in the general formula for the case of three real roots. I calculated that alpha = 1 + 2 cos (pi/9). I tried some trig tricks with powers of that but it didn't help me solve the problem! (The other two roots are 1 + 2 cos(5 pi/9) and 1 + 2 cos(11 pi/9). )

[@spiderjerusalem4009]

starting with instead χ³-3χ+1=0. Using cardano's method. Obtaining -2cos(π/9) as one of the roots. Attaining others as well by division algorithm. Reciprocate all those roots

[@JamesLewis2]

Another hint (Descartes's rule of signs) would show why the root between 2 and 3 is the greatest root: f(x) has two sign-changes, so it has zero or two positive zeroes; f(-x) has one sign-change, so f(x) has one negative zero. Clearly, f(0)=1 and f(1)=-1, so (by the IVT) there is a positive zero less than 1; then as you found, there is another zero between 2 and 3, which is the only other possible zero and so must be the greatest.

[@warmpianist]

How can we factor x^3 - 3x^2 + 1 as (x-4)(x-5)(x-11) (mod 17) without having to try all 17 numbers?

[@alexgan3219]

As there can be only 3 factors, we can only check until 11 :)

[@CauchyIntegralFormula]

In fact, once you find 4 and 5, we know the sum of roots is 3, so you can determine that the last root is 3-4-5=-6=11 mod 17

[@sirgog]

Guess and check is the best solution. Once you find two of them the third is immediate.

[@kubatrcka5570]

I know another (more algebra) problem with the same polynomial and it's biggest root. Show that ceil(alpha^n) is divisible by 3, for every natural number n.

[@krzysztofkujawa5506]

Very nice video but it is not easier to count that a^4 + b^4 + c^4 = 69 using vieta's formulas, without using polynomial congruence. saying a, b, c I mean zeros of that polynomial

[@wojteksocha2002]

What about doing this: let s_n = a^n + b^n +c^n (im using a,b,c instead of alfa,beta,gamma for simplicity). Notice that s_n = (a+b+c)*s_(n-1) - (ab + bc + ca)*s_(n-2) + abc*s_(n-3) = 3*s_(n-1) - s_(n-3) and s_1 = -3, s_2 = 9, s_3 = -30. As we know, b^n + c^n for very big and even n becomes very small number, definitely smaller than 1. So that means that the value we are trying to find is just s_1998 - 1. We can calculate it by finding the general formula for s_n. You can use for instance Michael favourite technic - generating functions. I think that this will work here

[@spiderjerusalem4009]

you mean generating function for aₙ=3aₙ₋₁-aₙ₋₃ ?

[@danrain12345]

Great as always

[@toddtrimble2555]

Hm, I proceeded slightly differently, in a way that avoids the "sheer luck" that your polynomial splits over F_{17} (which I hadn't noticed). Let r1, r2, r3 be the roots in ascending order. Then for i = 1, 2, 3, we have that the sequence (ri)^n satisfies the recurrence x_{n+3} = 3x_{n+2} - x_n, as does any linear combination of such sequences. We are interested in the sequence x_n = r1^n + r2^n + r3^n, computed mod 17. We have x_0 = 3, x_1 = 3, x_2 = 9 (the square power sum in terms of elementary symmetric polynomials being e1^2 - 2e_2). So the initial terms of the sequence are 3, 3, 9, with further terms determined by the recurrence, and we watch what happens mod 17. Actually I used 1, 1, 3 and then multiplied by 3 at the end; for that, the repeating block mod 17 is of length 16 and is 1, 1, 3, 8, 6, 15, 3, 3, 11, 13, 2, 12, 6, 16, 2, 0. Now 1988 mod 16 is 4, and the entries where n = 4 mod 16 yield 6 mod 17, which when multiplied by 3 results in 1 mod 17. Because r1^{1988} + r2^{1988} is small and positive (note |r1| < |r2| because r1 + r2 > 0), definitely in (0, 1), the floor of r3^1988 must be 0 mod 17.

[@digxx]

There is a famous problem about elementary symmetric polynomials: x+y+z=1 x^2+y^2+z^2=2 x^3+y^3+z^3=3 Find x^4+y^4+z^4 which turns out to be 25/6; so not an integer. So why is that integer argument apparently only valid if the symmetric polynomials are taken as the coefficients from a cubic (or generally polynomials)?

[@krzysztofkujawa5506]

In video case coefficients are all integer, in your case they aren't. x^3 - 3x^2 +1 = 0 y^3 - 3y^2 + 1 = 0 z^3 - 3z^2 + 1 = 0, so x^n + z ^ n + y ^ n = 3(x^n-1 + y^n-1 + z^n-1) - z^n-3 - x^n-3 - y ^n-3

[@digxx]

@@krzysztofkujawa5506 Sorry, maybe I don't get it, but I don't see how what you say has anything to do with what I'm asking. In the case of the video the 3 equations are x+y+z=3 xy+xz+yz=0 xyz=-1 So different defining equations for the three roots x,y,z. I see that in my case a linear combination with integer coefficients for the three elementary symmetric polynomials would lead to the coefficient of x^4+y^4+z^4 to be greater than 1, because (x+y+z)^4 gives one contribution, but e.g. also (x^2+y^2+z^2)^2 so apparently integers doesn't work, whereas in the other case there is only 1 elementary symmetric polynomial - namely (x+y+z)^n - which gives rise to the unique x^n+y^n+z^n, but any other combination, say (x+y+z)^{n-2}*(xy+xz+yz) will never give a term x^n+y^n+z^n, but how do I know the other coefficients will not be rational numbers. So what does your example show?

[@krzysztofkujawa5506]

@@digxx maybe I didn not understand your question, but it is about how we may know that x^n + y^n + z^n is integer?

[@digxx]

@@krzysztofkujawa5506 Basically yes. But why is my case not an integer?

[@krzysztofkujawa5506]

In your case it is not itneger because coeficients of polynomial which has roots x, y, z are not all integeres but in the video case the coeficients of polynomial which roots are x, y, z X^3 - 3X^2 + 1 are integers.

[@wolo-math]

Of the 30 of so videos I've watched on your channels, this is by far the most difficult solution to conceptualize. I'm curious of whether any alternative solutions exist through Cardano Del-Ferro's equation, converting the solution into Polar, then using De'Moivre's Theorem to expand the 1988th power, then somehow showing the floor of the rational part must be divisable by 17? This would be a total shot in the dark, but considering my Number Theory is quite weak it'd be my only idea.

[@emilianomaccaroni2424]

You are big! From Argentina!

[@HagenvonEitzen]

Before watching the video, my quick guess is: Estimate the roots roughly, in particular the others are small. Then consider a linear relation (i.e., Fibonacci-like)

[@l1mbo69]

When Michael said, "I think it's a pretty hard problem" I thought, how hard could it be? But then I watched the video

[@mohamedfarouk9654]

What does factorizing a polynomial under mod really mean? What is the relation between (4,5,11) and the real roots (alpha,beta,gamma)?

[@CauchyIntegralFormula]

I don't think there's a strong relationship between the roots themselves but rather between the symmetric polynomials of those roots. For instance, look at alpha^2+beta^2+gamma^2. It turns out that you can rewrite this as (alpha+beta+gamma)^2 - 2(alpha*beta + alpha*gamma + beta*gamma) = (-p)^2 - 2q (where -p = alpha + beta + gamma and q = alpha*beta + alpha*gamma + beta*gamma, as seen in the video). Thus, alpha^2 + beta^2 + gamma^2 = (3)^2 - 2(0) = 9. Similarly, modulo 17, 4^2 + 5^2 + 11^2 = (4+5+11)^2 - 2(4*5+4*11+5*11) = 3^2 - 2*0 = 9. In general, any symmetric polynomial of f(alpha,beta,gamma) can be written as a polynomial of -p, q, and -r = alpha*beta*gamma. (This fact is known as the fundamental theorem of symmetric polynomials on Wikipedia.) But since modulo 17, -p, q, and -r have the same values as 4+5+11, 4*5+4*11+5*11, and 4*5*11, respectively, it follows that every symmetric polynomial of alpha, beta, and gamma is congruent modulo 17 to its 4-5-11 form. In particular, alpha^1988 + beta^1988 + gamma^1988 = 4^1988 + 5^1988 + 11^1988 mod 17.

[@OuroborosVengeance]

@@CauchyIntegralFormula Thanks

[@kostaspapadopoulos1480]

If we see the two polynomials as functions, let's say f(x)=x^3-3x^2+1 and g(x)=(x-4)(x-5)(x-11), then in the domain (0,1,2,...,16) which contains all the possible residues if we divide a number with 17, we have f(x)=g(x) (mod17)

[@jacemandt]

I suspect that IMO problems are not written under the assumption that high school students know anything about rings and generating symmetric polynomials. (Just trying to answer the question in the title of the video.)

[@boraolmez6622]

IMO participants definitely know stuff about generating symmetric polynomials.... this actually is not that “hard” for the IMO imo(no pun intended)....

[@zafarb4219]

This might be subjective as I haven't been to IMO, but in Japan from what I've seen, most of the IMO students have a deep knowledge in university math for algebra, number theory etc. Some have just finished university math (first 4 years) completely. They do really do a lot of training.

[@l1mbo69]

@@boraolmez6622 nah it's definitely pretty hard even by IMO standards, probably could be a hard Problem 2/4 although not a 3/6 monster

[@boraolmez6622]

@@l1mbo69 agreed, but I was trying to claim that it’s not “too hard” for the imo (i would probably say 2/5 as well)

[@rbnn]

I thought IMO was for high schoolers. I didn’t learn about symmetric polynomials until I had Galois theory and certainly not in high school

[@KingstonCzajkowski]

No, the IMO is for some of the best students in the country (I believe the US only sends 7).

[@JM-us3fr]

I think the problems are meant to be solvable with no more than a high school education, but that’s probably why this problem wasn’t put on the exam

[@donaldbiden7927]

@@JM-us3fr look at the #6 problems, things used in them are never taught in high school. I believe that now a days no problem in the IMO can be solved with purely high school knowledge

[@zafarb4219]

​@@donaldbiden7927 it is theoretically possible to solve most of the problems using only high school math (calculus not included), but for some problems almost no human being can come up with the astounding ideas needed, if you're trying to not use at least some specialized knowledge.

[@taopaille-paille4992]

@@donaldbiden7927 #6 of 2020 uses very elementary tools that are known by any high school students (mainly pythagorean theorem). But the problem was very difficult because it required a lot ingenuity to put everything together.

[@Chalisque]

I had to re-read carefully to see that it was f(x)=0, not f'(x)=0 (the comma from the line above appears right where the apostrophe in f'(x) would be).

[@erinc.8633]

I have trouble with "combining the 2 approaches". You say straight away that alpha^2n + beta^2n + gamma^2n is congruent to 4^2n + 5^2n + 11^2n mod 17 Could you justify that a lil bit better?

[@GiornoYoshikage]

I think the fact about expressing sym. polynomials (SP) by elementary sym. polynomials (ESP) is useful here. Expressions for "α^(2n) + β^(2n) + γ^(2n)" in R and F17 in terms of ESP's ("p,q,r" in the beginning of video) are same. Values of ESP's are integers, "p,q,r" in R and in F17 are congruent mod 17 (they're even the same because they're just the coefficients of polynomial) => "α^(2n) + β^(2n) + γ^(2n)" in R and in F17 are congruent mod 17, even though "α,β,γ" are different in R and in F17. This implies that α^(2n) + β^(2n) + γ^(2n) Ξ 4^(2n) + 5^(2n) + 11^(2n) (mod 17), where "α,β,γ" are real roots

[@Michael-es4fg]

Congrats on 100k subs!

[@niuhaihui]

can be also done by finding the sequence mod 17 has a period of 16

[@oliver_ai]

Great! I love IMO problems

[@andreasraab5294]

Too hard for me

[@moregirl4585]

Get ranges of roots to

[@sebastiengross7849]

If I had the tool at 3:28 it would have help me back in time I was a student. Yet today it would be useful 😁

[@l.lawliet164]

13:47 How he conclude the values for alpha, beta and gama composts?

[@GreenMeansGOF]

Can someone explain the equation at 20:00?

[@yashvardhan6521]

My fav on ur channel sir

[@vladthemagnificent9052]

I don't get it, why symmetrical polynomial of real roots is equal to that of roots in F17

[@jasongros6688]

I was thinking you could rewrite a^1998 as a linear combination of 1,a,a^2 using the fact that every power of 'a' can be written as a linear combination of these. Not sure if you get a desirable answer that way though.

[@jamirimaj6880]

Wait, so if the coefficients of ANY cubic are all integers, then the sum of any nth-power of the three roots is also an integer? And will this work on polynomials of degree 4 or higher?

[@OOobstkuchenOO]

yes, any symmetric function of the roots of a polynomial can be written as a function of the coefficients of the polynomial with integer coefficients. That's because the coefficients themselves are integer functions of the roots and the specific functions that give the coefficients of a polynomial are a basis of the space of all symmetric functions in that many variables

[@henry8777]

Another way to show alpha^n+beta^n+gamma^n is an integer is to define f(x)=alpha^x+beta^x+gamma^x. We then have f(x)=3f(x-1)-f(x-3) (because alpha,beta,gamma, are solutions to x^3=3x^2-1) and that f(-1)=0, f(0)=3, f(1)=3 (f(-1)=(alpha*beta+beta*gamma+gamma*alpha)/(alpha*beta*gamma)=0). We can then show f(x) is an integer, when x is an integer, using induction. And to show that this integer is congruent to 4^x+5^x+11^x mod 17, we can define g(x)=4^x+5^x+11^x mod 17, and because 4,5 and 11 are solution to x^3=3x^2-1 mod 17, we must have g(x)=3g(x-1)-g(x-3). g(0)=3, g(1)=4+5+11=3 and g(-1)=4^-1+5^-1+11^-1=13+7+14=0, because 13,7,14 are the multiplicative inverses of 4,5,11 respectively (ie 4*13=1 mod 17, so 13=4^-1) So f(x) must be congruent to g(x) mod 17, because they are defined by the same initial values and recurrence relationship mod 17.

[@bangstar719]

Can you tell me how to prove that f(x) is an integer, using induction? Or give me a hint?

[@spiderjerusalem4009]

​@@bangstar719f(0), f(1), and f(2) are easy to find and are all integers, then proceed by induction

[@jchaskar]

Nicely done 👍🏻 Just ignore 20:35

[@АндрейВоинков-е9п]

Can somebody explain step started on 19:37 in more detail?

[@erikr007]

All symmetric polynomials are generated by the elementary symmetric polynomials e1, e2 and e3 (look up in wikipedia). We know e1(α, β,γ) = e1(4,5,11) mod 11, e2(α, β,γ) = e2(4,5,11) mod 11, and e3(α, β,γ) = e3(4,5,11) mod 11 because these are just the coefficients of the polynomial x^3 - 3x^2 + 1. Therefore F[e1,e2,e3](α, β,γ) = F[e1,e2,e3](4,5,11) mod 11 for any multinomial expression F.

[@debjitkunduscience11a93]

Can anyone help me out with why symettric polynomial can be written in terms of apha + beta + gamma , alpha beta + beta gamma + aloha gamma , alpha beta gamma ? Thanks in advance

[@pmcate2]

alpha^n + beta^n + gamma^n = integer is not clear to me.

[@tomasstride9590]

It was a new result to me as well, so I had to go back and listen to what he said. As far as I understand it is because the roots satsify a set of symmetric equations all of which have integer value. Now any other symmetric equation can be built up using those existing equations and so must also be integers. I think that is what he said and it makes sense to me though it was not somethimg I knew before.

[@erickross5868]

If you don't want to use fields, you can also show that fact with a recurrence relation. You can prove that that expression is a_n where a_k = 3 a_{k-1} - a_{k-3} and a_0 = 3, a_1 = 3, a_2 = 9. The recurrence came from the polynomial how we typically try to solve recurrence relations like that. The initial conditions came from evaluating a_k directly (using the facts we learned from Vieta). Hence a_k is always an integer.

[@asklar]

latexbase.com/d/d2047e4d-e4a9-4778-adc5-2d5e29069295

[@bangstar719]

@@angelmendez-rivera351 but how do you know that it would be an integer? For example it can also be: (a+b+c)/(abc) which is also symmetric but not integer

[@verystablegenius4720]

ClearAll["Global`*"]; sol = NSolve[x^3 - 3 x^2 + 1 == 0, x, WorkingPrecision -> 5000] x = sol[[3]][[1]][[2]]; s = Floor[x^1988] Mod[s, 17] This gives 0 in Mathematica, so problem checks out, good job.

[@peterhiggins5131]

f(x) = x^2(x - 3) + 1, so if x > 3 all terms are positive; no need to be obscure about that.

[@toomanyhobbies2011]

We learn something new everyday. No reason to feel embarrassed by not knowing this. We use some of this in physics, but don't really care about this type of solution, so we hardly think about it.

[@knowledgekong4970]

Why pqr are integers imply alpha beta and gamma are also integers?

[@fredfrancium]

When he said I think this is a hard problem. Then I got heart attack

[@JM-us3fr]

9:01 ootch? Well there’s a new word. I might have said scootch

[@hshsshsjsjns8074]

How You Can Get [ α^2 ] = α^2n + β^2n + y^2n - 1 ?

[@pooydragon5398]

I was understanding most of the video but the part that really confused me for a moment was the fact that 68 is divisible by 17!

[@postbodzapism]

Does cubic formula help

[@mcwulf25]

Phew! Lost me when he got to the powers of n.

[@prabhatsharma5751]

Love From Nepal 😊❤

[@frozenmoon998]

There will be a day when someone dislikes this and he will say this problem is too hard. I however loved every single moment of this video.

[@cristofer2794]

Los vídeos, the vídeos, los haces improvisados? It would be cool.

[@asklar]

18:59 "how would we figure out this fact?" Magic. We would need magic.

[@eduardokuri1983]

Are shortlist problems the ones who didn’t make it into the exams?

[@maydavidr]

That was a very entertaining video. However, you should have explained how you factored the cubic (mod 17); it's appearance was a bit "deus ex machina".

[@charlesbarrow803]

He explained, where it came from he brute forced it as there was only 17 values to check

[@sea34101]

That one was hard!!

[@markregev1651]

Is your finger alright

[@JXS63J]

The moment at 18:30 is just pulled out of the air. Then you quote some other stuff that's not germaine. Then you say "Great". Not really MATHEMATICS.

[@johnloony68]

All through that I was wanting to know what alpha is

[@ericvonl]

The first thing I figured out was that alpha = 1 + 2*cos(pi/9). I verified it with a calculator, and was quite proud of myself! But I didn't know where to go from there and finally gave up today :-(

[@sriramgorur4810]

@@ericvonl How did you find alpha?

[@ericvonl]

@@sriramgorur4810 Knowing a little bit about complex numbers helped. I substituted y=x-1 to get a new equation, y^3 -3y -1 =0, which is a depressed cubic. Then Cardano's formula can be used, giving y as the sum of the cube roots of two complex numbers. I recognized those numbers as points on the unit circle in the complex plane; specifically, the points at angles pi/3 and -pi/3. So, finding the cube roots simply meant dividing the angle by 3. When adding the roots, the real parts are equal and the nonreal parts cancel out, so y=2cos(pi/9). (And then I had to remember that y=x-1.) (Also, because a cubic equation has 3 roots, I had to find the other two roots and verify that they were smaller, because the problem defines alpha as the largest)

[@psioniC_MS]

I'm a simple man, I like "simple facts"

[@amirb715]

absolutely beautiful :-)

[@holyshit922]

This equation can easily by solved without numerical methods (x-1)^3=x^3-3x^2+3x-1 (x-1)^3-3(x-1)=x^3-3x^2+3x-1-3x+3 (x-1)^3-3(x-1)=x^3-3x^2+2 (x-1)^3-3(x-1)-1=-x^3-3x^2+1 x-1=ucos(theta) (3u/u^3)=3/4 3/u^2=3/4 u=2 x-1=2cos(theta) 8cos^3(theta)-6cos(theta)-1=0 8cos^3(theta)-6cos(theta)=1 4cos^3(theta)-3cos(theta)=1/2 cos(3theta)=1/2 3theta=π/3 3theta=7π/3 3theta=13π/3 x_{1}=1+2cos(π/9) x_{2}=1+2cos(7π/9) x_{3}=1+2cos(13π/9)

[@djvalentedochp]

ok great, I must study

[@byronwatkins2565]

Your assertion at 12:25 is NOT obvious to me at all.

[@byronwatkins2565]

@@angelmendez-rivera351 This part is obvious from the commutative property of the three factors (x-a)(x-b)(x-c). How does this imply that a^n+b^n+c^n "can be written in terms of p, q, and r?"

[@byronwatkins2565]

@@angelmendez-rivera351 Your first response was indeed from earlier in the video and the commutativity of (x-a)(x-b)(x-c) makes it obvious that exchanging e.g. ab yields the same product. But you have NOT enlightened me as to why this means that a^n+b^n+c^n "can be written in terms of p, q, and r." Precisely WHAT "well-known theorem" are you talking about and where can I see it demonstrated for myself?

[@byronwatkins2565]

@@angelmendez-rivera351 This thoroughly explains 12:00-12:20, which I have already stated several times that I already understood. It also has absolutely nothing to do with his statement at 12:25 that "a^n+b^n+c^n can be written in terms of p, q, and r." But you are right about one thing: when people claim something as fact that seems to me is NOT fact, it does tend to confuse me.

[@byronwatkins2565]

@@angelmendez-rivera351 p, q, and r are the coefficients in the third order polynomial whose roots are a, b, and c: (x-a)(x-b)(x-c)=x^3+px^2+qx+r making p=a+b+c, q=ab+bc+ac, and r=-abc. NONE of this answers my question.

[@thesecretkey9845]

>Just factor mod 17 by checking every integer mod 17 bro WTF no wonder it wasn't included

[@Qoow8e1deDgikQ9m3ZG]

crazy !

[@nullplan01]

And here I thought solving the cubic would help me: x³-3x²+1 = 0 Let t = x - 1 (t+1)³ - 3(t+1)² + 1 = 0 t³+3t²+3t+1 - 3t²-6t-3 + 1 = 0 t³-3t-1 = 0 Let u+v = t I. u³ + v³ = 1 II. 3uv = 3 -> uv = 1 -> v = 1/u u⁶ - u³ + 1 = 0 u³ = 1/2 + √(1/4 - 1) = 1/2 (1 + i√3) = 1/2 (2 exp(i π/3)) = exp(i π/3) Recall that ³√1 = {1; exp(2iπ/3); exp(-2iπ/3)} With that in mind: u₁ = exp(iπ/9) u₂ = exp(7iπ/9) u₃ = exp(-5iπ/9) v₁ = exp(-iπ/9) v₂ = exp(-7iπ/9) v₃ = exp(5iπ/9) Unfortunately, we must add them up. So Cartesian form would be great right about now. u₁ = cos π/9 + i sin π/9 u₂ = cos 7π/9 + i sin 7π/9 u₃ = cos 5π/9 - i sin 5π/9 v₁ = cos π/9 - i sin π/9 v₂ = cos 7π/9 - i sin 7π/9 v₃ = cos 5π/9 + i sin 5π/9 t₁ = u₁ + v₁ = 2 cos π/9 t₂ = 2 cos 7π/9 t₃ = 2 cos 5π/9 Noticing that the cosine is a falling function in [0;π], the smallest argument yields the largest result. So t₁ must be the greatest of these. α = 2 cos π/9 + 1 Except that doesn't tell me anything about [α¹⁹⁸⁸].

[@spiderjerusalem4009]

at least you conveyed it so others could learn

[@joshuamason2227]

ok but when am i ever gonna use this in real life

[@bharatpakkha7787]

Bisection method.

[@aupen4402]

5 is not mod 17 root

[@user-A168]

Good

[@CTJ2619]

F(1)= -3

[@dOncRiMe616]

In like ~10 minutes of the video there was 4 times a 19 second advertisement. Thats completely bullshit.

[@sofly666]

essa é boa

[@fmakofmako]

I'm guessing that knowing cardano's formula makes this problem too easy.

[@igml1145]

Not at all... estimating a nasty irrational number raised to the power of 1998 sounds painful

[@fmakofmako]

@@igml1145 The largest root is of the form 1+z+w where w is the conjugate of z. The multinomial expansion of this has a bunch of powers of z that I'm not sure what to do with. It does seem a bit ugly, but I haven't worked it out myself. If anyone wants to try z is the cube root of 1/2(1+rad3 i).

[@kmlhll2656]

It's a very hard problem, really I can't solve it.

[@anilsharma-ev2my]

Show it by graph 😀😃😃😃👽👽😃😃😀😃

[@LuqmanEinstein]

I like you bro