Irish Mathematical Olympiad | 2009 Q3

We investigate a nice number theory question regarding prime numbers from the Irish Mathematical Olympiad.
Please Subscribe: kzbin.info...
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:
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

[@MathNerd1729]

A common strategy to factor polynomials is to add and subtract the same term, so when I saw this, I just added and subtracted n² to get: n⁸+n+1 = n⁸-n² + n²+n+1 The first part (n⁸-n²) can be factored into n²(n⁶-1) which can be further factored to n²(n³-1)(n³+1) which leads to n²(n-1)(n²+n+1)(n³+1) So: n⁸+n+1 = n²(n-1)(n²+n+1)(n³+1) + 1(n²+n+1) Hence, n⁸+n+1 = (n²+n+1)[n²(n-1)(n³+1) + 1] Since n²+n+1 is always greater than 1, we hence want the other factor to equal 1. Otherwise, n⁸+n+1 would be composite. And the only way for n²(n-1)(n³+1)+1 to equal 1 is if n²(n-1)(n³+1) is 0 Clearly, since n² and n³+1 can't be 0, n-1 must be 0 in order to make the product of the three expressions 0. So, n-1=0 or n=1.

[@mrchin7562]

Interesting. I just tried n=1 => f(1)=3, n=1 is a solution. Like he said, probably not a large number.

[@jonathan3372]

Wow, that is actually a clever move! Very elementary and maybe even straightforward for people doing problem solving, yet elegant too

[@keithmasumoto9698]

But how did you know n^2 would work, right? The hard part is justifying that.

[@ittaloceara]

@@keithmasumoto9698 mindset

[@aakashhaque9805]

This is some next-level thinking.

[@loonycooney22]

I sat this exam! 'Roots of unity' was a favourite technique of the lecturer who set that question. When I'm checking polynomials for roots, I always check for i and omega thanks to him.

[@oliverqueen5883]

I've never felt patriotic about a maths problem before today

[@yueno0727]

You should be proud of Hamilton :)

[@nanigopalsaha2408]

@@yueno0727 How does the plastered Fourth-born Son of a law man in Dublin Dubbed an impressive polyglot young'un Wunderkind embarrassed in a contest with a prodigious Vermonter Obtain Irish science's highest honour?

[@ashimchakraborty2908]

@ math is none of any countries private property though modern mathematics highly developed by Germans but not germans alone also French,some by British later Hungarian, Russian Americans and now every corner of the world East or West. Chinese or Indian or Japanese every corner of the world

[@filipkonieczny3801]

Second big hint is not true actually: -1 is 4th root of unity and (-1)^2 = (-1)^4 but 2 =\= 4 (mod 4). We need assumption that omega is primitive n-th root of unity to make this works

[@ericlabrique]

yes, in fact 1 is a n-th root of 1 for any n, too and 1^a = 1^b doesn't imply a = b + n.r It seems it's only true for PRIMITIVE roots of 1

[@normanstevens4924]

It's the order of the root that determines the modulus value. -1 has order 2 and we have that 2 == 4 (mod 2).

[@sbmathsyt5306]

I really like how you start with the small hints and big hints before giving a full solution. Great explanation of an interesting question. Well done.

[@parameshwarhazra2725]

Michael penn I really like the way you attack the problems I mean your approach is superb. Keep it up. With love from India

[@elmirismaylov7940]

Hi. You can add and subtract n⁷ n⁶ n⁵ n⁴ n³ n². Then you can factorize easily. Factors will be (n²+n+1) and (n⁶-n⁵+n³-n²+1)

[@lucdegraaf5138]

In the thumbnail the equation is wrong it should be n^8+ n + 1 and not n^8 + n^2 + 1

[@MizardXYT]

Yes. And n⁸ + n² + 1 has infinitly many primes. n⁸ + n + 1 has only one.

[@lucdegraaf5138]

@@MizardXYT Cool! How do you prove it? Always found it fascinating how you can prove such things

[@davinsequeira]

@@MizardXYT Technically it has 3 for n belongs to integers but only 1 is a +ve integer solution

[@Pacuvio25]

@@MizardXYTIsn't it a multiple of 3 for any n?

[@Hiltok]

​@@Pacuvio25 For the n⁸+n²+1 problem, using a computer algorithm to check factorization , I have primes for nϵ{1,3,6,18,24,36,72}. All are can be expressed as 2ᵐ.3ⁿ for m,nϵ{0,1,2,3} but not all choices of m & n produce a prime. I have stopped at this point. There's likely to be more n's, but I'm not the guy to find them.

[@johanrichter2695]

As long as we know that n^2+n+1 is a factor over the integers, I don't think we need to do the polynomial division, your reasoning works fine without knowing what the polynomial you called g is, as long it has integer coefficients. (We can use Gauss' lemma to see that g must have integer coefficients.)

[@twistedsector]

6:23 fundamental theorem of *algebra*, right?

[@winniethexiinwesttaiwan8578]

n^8+n+1=sum(n^i for i in range 8) - n^2*sum(n^i for i in range 5)=[(n^9-1)-n^2*(n^6-1)]/(n-1) the instresting part is on the left side is cubic differential between n^3 and 1, right side is square differential between n^3 and 1, thus i find the common part n^3-1 ,so that it .

[@Goku_is_my_idol]

I did the same method🤘

[@Mathemagical55]

For n > 1 it's immediately obvious that n^6 > n^5 and n^3 > n^2 so n^6 - n^5 + n^3 - n^2 +1 must be greater than one and hence we have a non-trivial factorisation.

[@ZainAlAazizi]

I realized that only the number 1 is the solution, When I tried the number 2 I found that the result is 259 and is a composite by 7 (2^2+2+1). I did not realize that the number is composite until I have seen all your proof! Great!

[@Channel-gc3em]

Brilliant! Indeed, ω is the key to solve this one. (Incidentally, x^8＋x^2+1 seems not to be factored in Q-coefficient)

[@user-yt198]

This is a factorization problem. It is not so difficult to see that n⁸+n+1 = [n²+n+1][n⁵(n-1)+n²(n-1)+1] But for n>=2, both values inside the square brackets are bigger than 1. So for n>=2, n⁸+n+1 is composite.

[@rafael7696]

Thanks for new omympoad math problems. It is what more I like (sorry for my English writing)

[@lucatanganelli5849]

"Michael Penn won't get to the level of numberphile or blackpenredpen" Hell yeah he will

[@TechToppers]

Might even surpass bprp...

[@divyanshaggarwal6243]

idk who even said that

[@pbj4184]

Who said that?

[@keedt]

level in what sense?

[@pbj4184]

@@keedt Some immature comparison

[@chawkichalladia1812]

i have a question/ help request: I'm over all form of education and already graduated but i missed my chance to actually be good in mathematics. i want to learn math but every time i try to learn something i feel I'm missing something else that i should learn. any suggestions on a curriculum i should follow to learn math properly.

[@willnewman9783]

One thing to note with problems very similar to this: If they give you a polynomial f and say find all values so that f(n) is prime, then f must be reducible. This is because it is conjecturally true that if f(n) is prime for only finitely many values of n, then f is reducible, so they would not ask you to find all values for which an irreducible polynomial is prime.

[@sil1235]

I think you could have avoided the division and computation of g(x). If (n^2+n+1)g(n)=n^8+n+1 is to be a prime, the factor n^2+n+1 (which is greater than 1) must be equal to the number itself, and so n^2+n+1=n^8+n+1, which means n^2=n^8, and so 1=n^6 (because n=0 can be easily ruled out) which has in positive integers only solution n=1.

[@HagenvonEitzen]

Do a normal prime factorization of 3^8+3+1 = 6565 = 5*13*101, and from 5 = 2*3-1 = 3^2-3, 13 = 3^2+3+1, suspect that one of 2n-1, n^2-n, n^2+n+1 might be a polynomial factor (well, the first two of these clearly fail). Guessing coefficients this way would be easier when factoring 10^8+10+1, but that's quite a number

[@sayanjitb]

Why is it necessary to consider omega as cube root of unity not 4th root or 5th root, anyway?

[@goodplacetostop2973]

12:41

[@adenpower249]

Thanks

[@keedt]

Good Place to Sob: anywhere where you have a difficult math problem & Michael Penn isn't around

[@TikeMyson69]

Picture on the back of your shirt looks like a prog rock album cover.

[@kingbeauregard]

Took me too damn long to get what's happening here, but I finally got it. A number "x" is prime if its only factors are "1" and "x" -- or, to put it differently, composite numbers will have pairs of factors greater than 1. So the game here is one of negation: factor "n^8 + n + 1" and demonstrate that, for all values of "n" except maybe a select handful, the factors of the polynomial are both greater than 1. Through whatever means (I used algebraic chicanery) we factor the polynomial to "(n^2 + n + 1)(n^6 - n^5 + n^3 - n^2 + 1)" and see what happens. The first term is always greater than 1 for n >= 1, and the second term is greater than 1 for n >= 2. Soooo, the only candidate for a prime result is n=1, and indeed it happens to be prime. But for every value of "n" at 2 or greater, you get two factors that are both above 1, thus composite.

[@deept3215]

Now, solving the same problem for the pol. n^8+n+3 should be enough to get a Fields Medal

[@sankaellawela9271]

Super, hyper, VIDEO KEEP GOING PROF.

[@oliverqueen5883]

For 1: 1^2 + 1^8 + 1 = 1+1+1 = 3, which is a prime

[@siddhantsinha9276]

There is a misprint in the video thumbnail, please correct it as soon as possible. I wasted nearly 10 mins solving a wrong question lol

[@babunp114525]

Dear Sir, Thank you for your explanation. Could you please help me find out any number^any fractional e.g., 3.6^4.7

[@JM-us3fr]

You can either use Newton's Binomial Theorem, or the Taylor series for exponential and logarithm functions. It's not easy to do in one's head.

[@krstev29]

I am 13 and from a course I had a question: for what prime numbers p and q, p^2+q^2+1 is a prime number. I was getting nervous about not being able to solve it but i tried so hard and then i found out that if p and q can be same then they are both 2

[@jasonleelawlight]

I know the key is to factor the polynomial but still failed to do so, maybe because my skills have degraded as I've been graduated for many years.

[@rubyjha4298]

Where is qna?

[@AadiAcademy]

What kinda chalk does he use??

[@exodus_20_15]

6:49 What was that???

[@elkincampos3804]

In fact the Galois group of g(x) is S_6 because is irreducible and its discriminant is -14731, free squares.

[@gaius_enceladus]

"Find all positive integers n such that n^8 + n + 1 is prime." "Oi don't give a fiddlers piss...... let's go have a Guinness......... "

[@adenpower249]

Could you explain in more detail why x^2+x+1 necessarily divides x^8+x+1?

[@TechToppers]

Use the factor theorem and Roots of unity. This will simplify.

[@otakurocklee]

He skipped a step. x^2+x+1 has two distinct roots w and w^2. x^2+x+1 = (x-w)(x-w^2). We can also check that w and w^2 are roots of x^8+x+1. So we know that (x-w) factors into x^8+x+1 and so does (x-w^2). So we know that x^2+x+1=(x-w)(x-w^2) factors into x^8+x+1.

[@TechToppers]

@@otakurocklee I was right. Were I?

[@otakurocklee]

@@TechToppers Yes, you were right. :) I just put in the details. BTW, when I mentioned the skipped step, I was referring to the video, not to your post.

[@TechToppers]

@@otakurocklee Okay. A similar problem was in PRMO 2019(First stage for IMO selections in India (0 to 99 integral answers)).

[@aadityajha7502]

How would someone think of those hints ?? Things should be done systematically in mathematics. You should give some background on those hints.

[@user-A168]

Good

[@parameshwarhazra2725]

12:42 and that's a good place to stop!!!!!!!!🥰🥰🥰🥰🥰🥰

[@rish5827]

I don’t see the justification in the step where you say omega is a root of x^8 + x + 1 and omega is a root of x^2+x+1 implies x^8 + x + 1 = (x^2 + x + 1)(g(x)) where g(x) is a polynomial. This doesn’t seem to be generally true. If you take 2 is a root of (x-2)(x-5)(x-7) and 2 is a root of (x-2)(x-3) there is no polynomial g(x) such that (x-2)(x-5)(x-7) = (x-2)(x-3)g(x) Am I missing some extra criteria required for the implication to hold?

[@asiercalbet5088]

Indeed, he did not justify this properly, and it's not generally true, as you show. But x^2+x+1 is the minimal polynomial of omega over the rationals, so it can be justified. Alternatively, note that w^2 is also a root of his f(x), so f(x) is divisible by (x-w)(x-w^2)= x^2+x+1

[@sumangupta5684]

Can anyone tell Michael's email as I have a problem that I'm facing 😅

[@massipiero2974]

I did it differently, the result is correct, but i don't know if so is the reasoning 😂 Well, i started with p prime, n^8 + n + 1 = kp So n^8 + n = -1 mod p Which splits up to n*(n^7 + 1) = -1 mod p That gives me 2 possibilities (i'm not sure of that) : 1) n = -1, n^7 + 1 mod p, but n^7 = (-1)^7 = -1 = 0 mod p, so it's impossible 2) n = 1, n^7 + 1 = -1 mod p, so -2 = 1 mod p, and that gives me p = 3. So n^8 + n + 1 = 3 => n = 1, only solution

[@massipiero2974]

@Adam Romanov thanks

[@renusharma436]

Nice

[@venkateshbabu1504]

Some power eight is negative. So use i.

[@ariel_haymarket]

finally, we prove One Direction

[@tomatrix7525]

It’s no bother once you spot that the complex roots of 1 using unity are helpful, not very intuitive for me here though, I couldn’t solve without the bigger hint

[@hugolabella6417]

I think the thumbnail is wrong

[@michuosas]

smart

[@emmepombar3328]

I don't even understood the answer. How many are there now?

[@YoYo_Yosef]

Only one answer which is n=1

[@Goku_is_my_idol]

How to get the factorization You will like it So we see here an incomplete GP series So add and substract the same terms 1+n²+n³+......+n^8= p + n²+n³+.......n^7 n^9-1/n-1 = p + n²(n^6-1/n-1) n^9-1 = p(n-1) + n²(n^6-1) (n³-1)(n^6+n³+1) - n²(n³-1)(n³+1) =p(n-1) (n²+n+1)(n^6-n^5+n³-n²+1)=p n²+n+1 never equal to 1 n6-n5+n3-n2+1=1 So (n-1)(n5+n2)=0 only possible for n=1 hence p=3 I solved it by myself and i didnt copy it.

[@JM-us3fr]

Ah yes, using complex numbers and field theory facts to solve a math olympiad problem. Doesn't this seem a little too advanced?

[@ky1n603]

I can answer for n=1

[@benjaminbrady2385]

Ireland represent 🇮🇪

[@DMTHOTH]

beef... beef...

[@leif1075]

Who in the world would.actually think of all this??

[@aakashchakrabarty7714]

n^8+n+1=k where k is a prime number . n^8+n=k-1 ;n(n^7+1)=k-1 Now as n/k-1 K-1/n=m where m is a positive integer Also k/n-1/n=m Therefore n divides 1. Also n

[@megatroniker]

whaaaaat?

[@unknownsuperstarmanish7013]

I am from India seeing these maths problem. I am very interested in solving mathematics

[@oliverqueen5883]

Or instead of writing out all the maths just write "1,2"