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.
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.
@@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
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
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.)
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 .
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.
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.
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.
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.
Actually, if you start by calculating the value of f(n) = n^2 + n + 1 for small, consecutive number n, you get: n=1 => f(n) = 3 n=2 => f(n) = 7 x 37 n=3 => f(n) = 13 x 5 x 101 n=4 => f(n) = 21 x 3121 Looking at the first factor of each value of f(n), it is not so difficult to see that: 3 = 1 x 2 + 1 7 = 2 x 3 + 1 13 = 3 x 4 + 1 21 = 4 x 5 + 1 I.e. each of those first values of f(n) has a factor of the form n x (n+1) + 1 = n^2 + n + 1.
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.
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
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
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 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.
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.
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
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
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.
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
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
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 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.
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)
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'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
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).
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.)
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🤘
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.
6:23 fundamental theorem of *algebra*, right?
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.
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.
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.
Actually, if you start by calculating the value of f(n) = n^2 + n + 1 for small, consecutive number n, you get:
n=1 => f(n) = 3
n=2 => f(n) = 7 x 37
n=3 => f(n) = 13 x 5 x 101
n=4 => f(n) = 21 x 3121
Looking at the first factor of each value of f(n), it is not so difficult to see that:
3 = 1 x 2 + 1
7 = 2 x 3 + 1
13 = 3 x 4 + 1
21 = 4 x 5 + 1
I.e. each of those first values of f(n) has a factor of the form n x (n+1) + 1 = n^2 + n + 1.
"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
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
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.
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
Why is it necessary to consider omega as cube root of unity not 4th root or 5th root, anyway?
Thanks for new omympoad math problems. It is what more I like (sorry for my English writing)
For 1:
1^2 + 1^8 + 1 = 1+1+1 = 3, which is a prime
Brilliant!
Indeed, ω is the key to solve this one.
(Incidentally, x^8＋x^2+1 seems not to be factored in Q-coefficient)
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
6:49 What was that???
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.
Where is qna?
In fact the Galois group of g(x) is S_6 because is irreducible and its discriminant is -14731, free squares.
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)).
Super, hyper, VIDEO KEEP GOING PROF.
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.
"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......... "
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
What kinda chalk does he use??
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
Some power eight is negative. So use i.
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.
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
How would someone think of those hints ?? Things should be done systematically in mathematics. You should give some background on those hints.
Can anyone tell Michael's email as I have a problem that I'm facing 😅
12:42 and that's a good place to stop!!!!!!!!🥰🥰🥰🥰🥰🥰
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.
Good
Ah yes, using complex numbers and field theory facts to solve a math olympiad problem. Doesn't this seem a little too advanced?
finally, we prove One Direction
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
I think the thumbnail is wrong
I don't even understood the answer. How many are there now?
Only one answer which is n=1
Nice
smart
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
Who in the world would.actually think of all this??
I can answer for n=1
Ireland represent 🇮🇪
beef... beef...
whaaaaat?
I am from India seeing these maths problem.
I am very interested in solving mathematics
Or instead of writing out all the maths just write "1,2"