Calculating the gcd of the two polynomials with the Euclidean Algorithm is probably the easiest way to do it. It terminates in our case after only 3 steps of the algorithm, so we get the gcd as the remainder of the second step. You would have also gotten it after only 3 steps, had you done the *full* polynomial division in each step rather than just stop after the first term of the quotient. This in particular applies to the polynomial division in your second step where you wondered why your remainder had a higher degree than your divisor. This only happened because you were not finished with the division yet.
While doing it with the Euclidean Algorithm is probably the easiest way to get at the gcd, doing it with some algebra (ring theory) and complex numbers gives some more insights into the structure of the problem. Let the polynomial g in C[X] denote a greatest common divisor (gcd) of the two given polynomials p1=X^91 + 1 and p2=X^65 + 1. Wlog, let's choose the unique gcd with a leading coefficient of 1. In C[X], i.e. when the coefficients originate from the field of complex numbers C, g factors completely into linear factors of the form (X - a) where a is a complex number, by the Fundamental Theorem of Algebra. First, let (X - a) be any linear factor of g. Then, a is a root of g, which means that a is also a common root of both p1 and p2 (because g divides both). Therefore, a^91 = -1and a^65 = -1. From that follows a^26 = a^91 / a^65 = 1 and a^13 = a^65 / (a^26)^2 = -1. So, a is a 13th root of -1, and (X - a) is a linear factor of the polynomial X^13 + 1. Conversely, let X - a be any linear factor of X^13 + 1. Then a is a 13th root of -1, i.e. a^13 = -1. This implies a^91 = (a^13)^7 = (-1)^7 = -1 and a^65 = (a^13)^5 = (-1)^5 = -1. Therefore, X - a is a common factor of both p1 and p2, which in turn implies it is a linear factor of the greatest common divisor g. Thus, we know that g and X^13 + 1 have exactly the same linear factors (X - a). Moreover, all of these linear factors have a multiplicity of 1 because the complex roots of the polynimials p1, p2, and X^13 + 1 are all of that multiplicity, being nth complex roots of -1. We also know that C[X] is a Unique Factorization Domain where the linear factors are the prime elements. Therefore, as g and X^13 + 1 share exactly the same prime divisors with the same multiplicity, they must be the same polynomial, up to a unit of the polynomial ring. But, since g and X^13 + 1 have the same leading coefficient of 1, they must be exactly identical, so g = X^13 + 1, q.e.d.
Alternative but less elegant solution based on the fact that these polynomials are easy to factor: (x^91+1) has roots at x_k = e^((2*k+1)*pi*i/91) and (x^65+1) has roots at x_n = e^((2*n+1)*pi*i/65). So the polynomials factor into the product of all (x-x_k) and (x-x_n) respectively. Then you just have to identify the common roots. e^((2*k+1)*pi*i/91) = e^((2*n+1)*pi*i/65) (2*k+1)/91 = (2*n+1)/65 5*(2*k+1) = 7*(2*n+1) 5*k = 7*n+1 7*n+1 mod 5 is the same as 2*n+1 mod 5, i.e. [1,3,0,2,4,1,3,0,2,4,...], so the possible values for n are 5*m+2 for 0≤m
Long way: euclidean algorithm because gcf(a,b)=gcf(a mod b, b) for a>b Shorter way: notice both gcf(65,91)=13 so sum of odd powers formulas give us that (x¹³+1) is a factor. Substitute t=x¹³ for the other factor in the difference of powers formulas, then euclidean algorithm on them to verify that they share no further factors, thus (x¹³+1) is the greatest common factor.
Very interesting. I wonder how the exercise was designed? That is, you start from a result and follow the opposite path to finally reach the statement of the exercise. How could it have been done? More than solving the exercise, I find it more interesting to know how to create the exercise.
f(x)=x^91 + 1, f'(x)=91 x^90 f'(x)=91 x^90 is always grater then 0, f'(x)=0 if x=0, f is an increasing function f(-1)=0 is the only solution of f(x)=0 we can write the polynom : x^91 + 1=(x+1)q(x) where q(x) has no roots (prime polynom). Same work for x^65 + 1=(x+1)p(x) where p(x) has no roots. Then the only factor between the two polynoms is (x+1).
Well, no. p and q may be divisible by some polynomial w which also has no roots, e.g. (x^2+1)(x^4+1) and (x^4+1)(x^6+1) have no real roots while having a common factor of (x^4+1) A plynomial with no real roots is not necesserly prime
@@raptor9514 you got it I did not think of it, I was really focusing on Theron if a poly nom has n roots then it will be written as f(x)=(x-a1)(x-a2)....(x-an) I was totally wrong, thank you.
well this is repeated modulus math based on reducing the HCF until you have something manageable. The new mod is the lower number/polynomial. You will always get either a 0 or a 1 as the final result. with 1 it means relatively coprime and a 0 means you found the HCF on the previous step. interesting. This is what in part GIMPS must be doing in order to determine if the target number is prime.
Yes - provided the degree of the polynomials has an odd factor and is not a power of two. All roots of xⁿ + 1 are also roots of x²ⁿ - 1; and thus are 2n'th roots of unity, a cyclic group of order 2n. However, every common factor of a polynomial xⁿ + 1 must be the cyclotomic polynomial for a subgroup, which by Lagrange's theorem must have order which is a divisor of the supergroup's order. Thus any common factor must have an order which divides the order of both; which you asked to be shown. In the case of polynomials with degree a power of 2, they are irreducible
@@pietergeerkens6324Most of what you are saying seems ok, so I don't know where you went wrong for your ultimate YES answer; I didn't check. However, the answer to OP's original question is clearly NO. Here is a very simple counterexample: Look at the two polynomials p1=X^4+1 and p2=X^2+1. Their GCD is 1, (*not* X^2+1 as you might have expected), i.e. they are coprime (check with the Euclidean Algorithm!). However, the GCD of the exponents of their leading terms is 2, i.e. they do share a non-trivial common factor.
@@Grecks75 Good catch. I neglected to mention that it only holds for polynomials with a composite degree that's not a power of 2. Those polynomials are always irreducible.
Nice, but 91 and 65 are both divisible by 13 which is their HCF. does it work with every couple of exponents with 1 added to both? I.E. HCF of x^84+1 and X^76+1 is X^4+1? If yes can it be demonstrated?
Also have a look at my main answer for a discussion of the problem using the polynomial ring C[X] over the field of complex numbers C that argues with (unique) prime factorization in this ring. That will shed some light and give answers as to "why" this happens (for the original problem and also some similar cases).
Your example here is one of the cases with even exponents where the same argument should work, if I'm not mistaken, and X^4+1 is indeed a GCD of the other two polynomials. However, it doesn't work out that way in all cases with even exponents, maybe I can find a counterexample later.
That was easy. Here is a very simple counterexample: Look at the two polynomials p1=X^4+1 and p2=X^2+1. Their GCD is 1, (*not* X^2+1 as you might have expected), i.e. they are coprime (check with the Euclidean Algorithm!). However, the GCD of the exponents of their leading terms is 2, i.e. they share a non-trivial common factor.
I might be a little obsessed with this channel. Really great work
absolutely love these videos. watch em while i eat my breakfast.
Or you could replace x^13 with t and use the x^odd no. + 1 factoring rule to get t+1 as only common factor
Calculating the gcd of the two polynomials with the Euclidean Algorithm is probably the easiest way to do it. It terminates in our case after only 3 steps of the algorithm, so we get the gcd as the remainder of the second step. You would have also gotten it after only 3 steps, had you done the *full* polynomial division in each step rather than just stop after the first term of the quotient. This in particular applies to the polynomial division in your second step where you wondered why your remainder had a higher degree than your divisor. This only happened because you were not finished with the division yet.
Thank you so much for your videos! God bless you. I love your admonition to never stop learning.
I WISH I HAD YOU AS MY PROF IN UNIVERSITY , YOURE FANTASTIC
Another great video! You make MATHS fun!
While doing it with the Euclidean Algorithm is probably the easiest way to get at the gcd, doing it with some algebra (ring theory) and complex numbers gives some more insights into the structure of the problem.
Let the polynomial g in C[X] denote a greatest common divisor (gcd) of the two given polynomials p1=X^91 + 1 and p2=X^65 + 1. Wlog, let's choose the unique gcd with a leading coefficient of 1.
In C[X], i.e. when the coefficients originate from the field of complex numbers C, g factors completely into linear factors of the form (X - a) where a is a complex number, by the Fundamental Theorem of Algebra.
First, let (X - a) be any linear factor of g. Then, a is a root of g, which means that a is also a common root of both p1 and p2 (because g divides both). Therefore, a^91 = -1and a^65 = -1. From that follows a^26 = a^91 / a^65 = 1 and a^13 = a^65 / (a^26)^2 = -1. So, a is a 13th root of -1, and (X - a) is a linear factor of the polynomial X^13 + 1.
Conversely, let X - a be any linear factor of X^13 + 1. Then a is a 13th root of -1, i.e. a^13 = -1. This implies a^91 = (a^13)^7 = (-1)^7 = -1 and a^65 = (a^13)^5 = (-1)^5 = -1. Therefore, X - a is a common factor of both p1 and p2, which in turn implies it is a linear factor of the greatest common divisor g.
Thus, we know that g and X^13 + 1 have exactly the same linear factors (X - a). Moreover, all of these linear factors have a multiplicity of 1 because the complex roots of the polynimials p1, p2, and X^13 + 1 are all of that multiplicity, being nth complex roots of -1. We also know that C[X] is a Unique Factorization Domain where the linear factors are the prime elements. Therefore, as g and X^13 + 1 share exactly the same prime divisors with the same multiplicity, they must be the same polynomial, up to a unit of the polynomial ring. But, since g and X^13 + 1 have the same leading coefficient of 1, they must be exactly identical, so g = X^13 + 1, q.e.d.
This can be generalised. GCD(x^m+1,x^n+1)=x^gcd(m,n) + 1 when both m and n are odd numbers.
I learn something new everyday😅The beauty of life
Excellent use of the euclidian algorithm. Thanks for sharing!
Love your proofs. 😊
a^5 +1 = (a+1)(a^4-a^3+a^2-a+1)
&
a^7+1 = (a+1)(a^6 -a^5 +a^4 - a^3 +a^2 -1) where a=x^13
That finds the HCF I guess!
No, now you have to prove that the HCF of two right side polynomials is 1.
Alternative but less elegant solution based on the fact that these polynomials are easy to factor:
(x^91+1) has roots at x_k = e^((2*k+1)*pi*i/91) and (x^65+1) has roots at x_n = e^((2*n+1)*pi*i/65). So the polynomials factor into the product of all (x-x_k) and (x-x_n) respectively. Then you just have to identify the common roots.
e^((2*k+1)*pi*i/91) = e^((2*n+1)*pi*i/65)
(2*k+1)/91 = (2*n+1)/65
5*(2*k+1) = 7*(2*n+1)
5*k = 7*n+1
7*n+1 mod 5 is the same as 2*n+1 mod 5, i.e. [1,3,0,2,4,1,3,0,2,4,...], so the possible values for n are 5*m+2 for 0≤m
I was going to attempt to do it that way, but I just unpaused and watched the show. Good to know it works.
Why the negative sign (-)not included in (x^26)-1
i also want to ask him
There’s a lot of “GCD-ing” (with e phase angles) involved when factoring out coefficients in Fourier Series analysis
Well explained and well done ! Greetings !
You can do all this stuff, and long division with polynomials. I wish they would teach it that way.
Beautifully done. Thanks.
Long way: euclidean algorithm because gcf(a,b)=gcf(a mod b, b) for a>b
Shorter way: notice both gcf(65,91)=13 so sum of odd powers formulas give us that (x¹³+1) is a factor. Substitute t=x¹³ for the other factor in the difference of powers formulas, then euclidean algorithm on them to verify that they share no further factors, thus (x¹³+1) is the greatest common factor.
Sir where have you been?❤ I need your videos every day its like an addiction❤loveee
I love your explanation
Very interesting. I wonder how the exercise was designed? That is, you start from a result and follow the opposite path to finally reach the statement of the exercise. How could it have been done? More than solving the exercise, I find it more interesting to know how to create the exercise.
Isn't it called GCD? (Greatest Common Divisor)
HCF and GCD are the same thing, different textbooks use different names
GCD is called HCF in most commonwealth countries.
except growing up I learned is at Greatest Common Factor, just to split the difference 😄
In Brazil we use MDC (Máximo Divisor Comum ), direct translation of GCD
Except GCD is appliable to integers only I suppose.
Great fun! Thank you!
Beautiful !
👍👍👍
f(x)=x^91 + 1, f'(x)=91 x^90
f'(x)=91 x^90 is always grater then 0, f'(x)=0 if x=0, f is an increasing function f(-1)=0 is the only solution of f(x)=0
we can write the polynom : x^91 + 1=(x+1)q(x) where q(x) has no roots (prime polynom).
Same work for x^65 + 1=(x+1)p(x) where p(x) has no roots.
Then the only factor between the two polynoms is (x+1).
Well, no. p and q may be divisible by some polynomial w which also has no roots, e.g. (x^2+1)(x^4+1) and (x^4+1)(x^6+1) have no real roots while having a common factor of (x^4+1)
A plynomial with no real roots is not necesserly prime
@@raptor9514 you got it I did not think of it, I was really focusing on Theron if a poly nom has n roots then it will be written as
f(x)=(x-a1)(x-a2)....(x-an)
I was totally wrong, thank you.
HCF? Is it a new way to say GCD?
Thanks 🙏🙏🙏🙏
well this is repeated modulus math based on reducing the HCF until you have something manageable. The new mod is the lower number/polynomial. You will always get either a 0 or a 1 as the final result. with 1 it means relatively coprime and a 0 means you found the HCF on the previous step. interesting. This is what in part GIMPS must be doing in order to determine if the target number is prime.
so is it legit to assume that for answers of this form, the result is of the form x^n+1, where n is the hcf of the two starting exponents?
Yes - provided the degree of the polynomials has an odd factor and is not a power of two. All roots of xⁿ + 1 are also roots of x²ⁿ - 1; and thus are 2n'th roots of unity, a cyclic group of order 2n.
However, every common factor of a polynomial xⁿ + 1 must be the cyclotomic polynomial for a subgroup, which by Lagrange's theorem must have order which is a divisor of the supergroup's order.
Thus any common factor must have an order which divides the order of both; which you asked to be shown.
In the case of polynomials with degree a power of 2, they are irreducible
@@pietergeerkens6324Most of what you are saying seems ok, so I don't know where you went wrong for your ultimate YES answer; I didn't check. However, the answer to OP's original question is clearly NO.
Here is a very simple counterexample: Look at the two polynomials p1=X^4+1 and p2=X^2+1. Their GCD is 1, (*not* X^2+1 as you might have expected), i.e. they are coprime (check with the Euclidean Algorithm!). However, the GCD of the exponents of their leading terms is 2, i.e. they do share a non-trivial common factor.
@@Grecks75 Good catch.
I neglected to mention that it only holds for polynomials with a composite degree that's not a power of 2. Those polynomials are always irreducible.
2:37 it matters if you use extended Euclidean algorithm
Wow, amazing
Nice, but 91 and 65 are both divisible by 13 which is their HCF. does it work with every couple of exponents with 1 added to both? I.E. HCF of x^84+1 and X^76+1 is X^4+1? If yes can it be demonstrated?
Sorry, I've seen it already answered below.
Also have a look at my main answer for a discussion of the problem using the polynomial ring C[X] over the field of complex numbers C that argues with (unique) prime factorization in this ring. That will shed some light and give answers as to "why" this happens (for the original problem and also some similar cases).
Your example here is one of the cases with even exponents where the same argument should work, if I'm not mistaken, and X^4+1 is indeed a GCD of the other two polynomials. However, it doesn't work out that way in all cases with even exponents, maybe I can find a counterexample later.
That was easy. Here is a very simple counterexample: Look at the two polynomials p1=X^4+1 and p2=X^2+1. Their GCD is 1, (*not* X^2+1 as you might have expected), i.e. they are coprime (check with the Euclidean Algorithm!). However, the GCD of the exponents of their leading terms is 2, i.e. they share a non-trivial common factor.
When you check , x+y=8 and XY=48, NOT 8. Confused me.
x^13 +1
When x^13= a it’s liked.. the GCD between a^7 + 1 and a^5 + 1 is a + 1 ???
Fun stuff, however when one replaces x for a number bigger than 1, the results doesn't quite match.
in 7:12, why can the remainder have negative sign?
It doesn't matter whether a number is positive or negative divisibility to exist.
@@PrimeNewtons thank you 🙌🏽
Amazing!
Why the negative sign (-)not included in (x^26)-1