Irish Mathematical Olympiad | 2009 Q3
Вставка
- Опубліковано 16 чер 2024
- We investigate a nice number theory question regarding prime numbers from the Irish Mathematical Olympiad.
Please Subscribe: ua-cam.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:
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
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.
Interesting. I just tried n=1 => f(1)=3, n=1 is a solution. Like he said, probably not a large number.
Wow, that is actually a clever move! Very elementary and maybe even straightforward for people doing problem solving, yet elegant too
But how did you know n^2 would work, right? The hard part is justifying that.
@@keithmasumoto9698 mindset
This is some next-level thinking.
I've never felt patriotic about a maths problem before today
You should be proud of Hamilton :)
@@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?
@ 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
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.
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
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
It's the order of the root that determines the modulus value. -1 has order 2 and we have that 2 == 4 (mod 2).
Michael penn I really like the way you attack the problems I mean your approach is superb. Keep it up. With love from India
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.
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)
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.)
In the thumbnail the equation is wrong
it should be n^8+ n + 1 and not n^8 + n^2 + 1
Yes. And n⁸ + n² + 1 has infinitly many primes. n⁸ + n + 1 has only one.
@@MizardXYT Cool! How do you prove it? Always found it fascinating how you can prove such things
@@MizardXYT Technically it has 3 for n belongs to integers but only 1 is a +ve integer solution
@@MizardXYTIsn't it a multiple of 3 for any n?
@@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.
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.
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 .
I did the same method🤘
6:23 fundamental theorem of *algebra*, right?
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.
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.
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.
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!
Now, solving the same problem for the pol. n^8+n+3 should be enough to get a Fields Medal
12:41
Thanks
Good Place to Sob: anywhere where you have a difficult math problem & Michael Penn isn't around
"Michael Penn won't get to the level of numberphile or blackpenredpen"
Hell yeah he will
Might even surpass bprp...
idk who even said that
Who said that?
level in what sense?
@@keedt Some immature comparison
Brilliant!
Indeed, ω is the key to solve this one.
(Incidentally, x^8＋x^2+1 seems not to be factored in Q-coefficient)
For 1:
1^2 + 1^8 + 1 = 1+1+1 = 3, which is a prime
Thanks for new omympoad math problems. It is what more I like (sorry for my English writing)
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
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.
Super, hyper, VIDEO KEEP GOING PROF.
Picture on the back of your shirt looks like a prog rock album cover.
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
In fact the Galois group of g(x) is S_6 because is irreducible and its discriminant is -14731, free squares.
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
Why is it necessary to consider omega as cube root of unity not 4th root or 5th root, anyway?
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.
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.
Where is qna?
finally, we prove One Direction
"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......... "
Good
Dear Sir,
Thank you for your explanation.
Could you please help me find out any number^any fractional e.g., 3.6^4.7
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.
Some power eight is negative. So use i.
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
@Adam Romanov thanks
What kinda chalk does he use??
12:42 and that's a good place to stop!!!!!!!!🥰🥰🥰🥰🥰🥰
6:49 What was that???
Could you explain in more detail why x^2+x+1 necessarily divides x^8+x+1?
Use the factor theorem and Roots of unity. This will simplify.
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.
@@otakurocklee
I was right. Were I?
@@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.
@@otakurocklee
Okay. A similar problem was in PRMO 2019(First stage for IMO selections in India (0 to 99 integral answers)).
Nice
How would someone think of those hints ?? Things should be done systematically in mathematics. You should give some background on those hints.
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.
I think the thumbnail is wrong
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?
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
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
smart
Ah yes, using complex numbers and field theory facts to solve a math olympiad problem. Doesn't this seem a little too advanced?
Ireland represent 🇮🇪
Can anyone tell Michael's email as I have a problem that I'm facing 😅
beef... beef...
I can answer for n=1
I don't even understood the answer. How many are there now?
Only one answer which is n=1
Who in the world would.actually think of all this??
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
I am from India seeing these maths problem.
I am very interested in solving mathematics
whaaaaat?
Or instead of writing out all the maths just write "1,2"