HCF of (x^91 + 1) and (x^65 + 1)

Рет қаралды 13,219

Күн бұрын

Пікірлер: 94

@Pramit1156 Ай бұрын

There is an even easier method. Both 65 & 91 has LCM of 13 , so we will convert the exponents as the exponent of x¹³. So we get Polynomial 1 = x⁹¹+1 = (x¹³)⁷+1 = a⁷+1 [Taking a = x¹³] Similarly Polynomial 2 = x⁶⁵+1 = (x¹³)⁵+1 = a⁵+1 Now in both polynomials the power of a is odd , so one of the factor will always be a+1 [By vanishing methos , we can verify it] Let's put a = -1 [a can be -1 if x is -1 as the power of x is 13 which is odd] we get , P1 = Polynomial 1 = a⁷+1 = (-1)⁷+1 = -1+1 = 0 P2 = Polynomial 2 = a⁵+1 = (-1)⁵+1 + -1+1 = 0 So , as I stated before a+1 will be a factor in both polynomial Now if we calculate the other factor in the 2 polynomials we get, P1 = a⁷+1 = (a+1)(a⁶-a⁵+a⁴-a³+a²-a+1) P2 = a⁵+1 = (a+1)(a⁴-a³+a²-a+1) The polynomials (a⁶-a⁵+a⁴-a³+a²-a+1) & (a⁴-a³+a²-a+1) are co-prime to each other , does not have any common factor for any real a. So clearly the only HCF we get is a+1 which is in fact (x¹³+1).

@Grandoise1234 Ай бұрын

Great approach. I LIKE IT MORE. It is wasy to understand.

@mainhunchikkuchikku Ай бұрын

Very nice and understandable. Vanishing method was what caught my attention.

@barryzeeberg3672 Ай бұрын

I like this method more than the brute force euclidean algorithm. this method uses more insight (ie, factoring x^n + 1 when n is odd)

@Pramit1156 Ай бұрын

@@barryzeeberg3672 Thanks. This one is easier to understand so I posted it to help the people who don't know euclidean method.

@dontspam7186 25 күн бұрын

How do you know a^6.. And the a^4.... Are coprime to one another?

@fabiozanucoli1689 2 ай бұрын

I might be a little obsessed with this channel. Really great work

@AjCohn 2 ай бұрын

absolutely love these videos. watch em while i eat my breakfast.

@shmujew4791 2 ай бұрын

I WISH I HAD YOU AS MY PROF IN UNIVERSITY , YOURE FANTASTIC

@DilipKumar-ns2kl Ай бұрын

Explained beautifully .

@williamspostoronnim9845 25 күн бұрын

Впервые узнал об алгоритме Евклида! Красивый способ решения на первый взгляд неразрешимой задачи.

@jpl569 2 ай бұрын

Very nice !! Here is another proof : As 91 = 7.13 and 65 = 5.13, let us define T = X^13. Then X^65 + 1 = T^5 + 1 = (T + 1) (T^4 - T^3 + T^2 - T + 1) And X^91 + 1 = T^7 + 1 = (T + 1) (T^6 - T^5 + … - T + 1) So T + 1 (I.e. X^13 + 1) is a common factor of the two polynoms. Now, the roots of T^5 + 1 and T^7 + 1 are the 5th and the 7th roots of - 1. As 5 and 7 are primes, no root except - 1 are in common. Then, T + 1 is the HCF of T^5 + 1 and T^7 + 1. This means that X^13 + 1 is the HCF of X^65 + 1 and X^91 + 1. Thanks for your videos. 😊

@LeBlancLover 2 ай бұрын

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

@davidcolf8362 2 ай бұрын

Thank you so much for your videos! God bless you. I love your admonition to never stop learning.

@XTRA14LIVE Ай бұрын

The goal is to find the highest common factor (HCF) of two polynomial expressions, x^91 + 1 and x^65 + 1, using the Euclidean algorithm. The Euclidean algorithm can be used to find the HCF of any two numbers by repeatedly dividing the larger number by the smaller number and taking the remainder until the remainder is 0, at which point the last divisor is the HCF. The same Euclidean algorithm can be applied to polynomial expressions by treating them as if they were numbers and writing one expression in terms of the other. The key steps in applying the Euclidean algorithm to the given polynomial expressions involve factoring the expressions and using the remainders to find the HCF. The final HCF of the two given polynomial expressions is x^13 + 1, which is found by repeatedly applying the Euclidean algorithm.

@Grecks75 2 ай бұрын

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.

@kaenemorerinyane9392 2 ай бұрын

I learn something new everyday😅The beauty of life

@Grecks75 2 ай бұрын

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.

@krwada 2 ай бұрын

Another great video! You make MATHS fun!

@Vabadrish Ай бұрын

You can solve this directly by doing X^2n+1 + Y^2n+1 Is divisible by X+Y Now as we have 91 and 65 we have hcf 13 as taking t=X^13 We have t^7+1 and t^5 +1 has common multiple t+1 Thus X13+1 If you think correctly, you too can solve in less than 10 seconds

@slavinojunepri7648 2 ай бұрын

Excellent use of the euclidian algorithm. Thanks for sharing!

@michelebrun613 13 күн бұрын

Since 91 = 13*7 and 65 = 13*5, defining y = x^13, we have y^7 + 1 = (y+1)(y^6-y^5+y^4-y^3+y^2-y+1) and y^5+1 = (y+1)(y^4-y^3+y^2-y+1). Then, I have to check if (y^6-y^5+y^4-y^3+y^2-y+1)/(y^4-y^3+y^2-y+1) gives a rest and the answer is easily yes since (y^6-y^5+y^4-y^3+y^2-y+1)/(y^4-y^3+y^2-y+1)=y^2 + (-y+1)/(y^4-y^3+y^2-y+1). Here it is the demonstration.

@kpt123456 2 ай бұрын

I love your explanation

@chinmay1958 2 ай бұрын

This can be generalised. GCD(x^m+1,x^n+1)=x^gcd(m,n) + 1 when both m and n are odd numbers.

@michaelz2270 Ай бұрын

And the Euclidean algorithm method of the video works for that too.

@hrishikeshkulkarni8955 2 ай бұрын

Beautifully done. Thanks.

@jay_sensz 2 ай бұрын

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

@Jono4174 2 ай бұрын

I was going to attempt to do it that way, but I just unpaused and watched the show. Good to know it works.

@michaelz2270 Ай бұрын

This method generalizes to x^m + 1 and x^n + 1 for all odd m and n, getting that their GCD is x^(gcd(m,n)) + 1

@jay_sensz Ай бұрын

@@michaelz2270 That's what it boils down to, but the fact that 13 is the gcd of 91 and 65 wasn't entirely obvious the way I went about calculating it. I'm guessing there are less convoluted ways to solve e.g. e^((2*k+1)*pi*i/91) = e^((2*n+1)*pi*i/65) if you're better with number theory than I am. I didn't want to just handwave it by stating that the common roots are obviously those of x^13+1, but at least provide a slightly more rigorous derivation.

@michaelz2270 Ай бұрын

@@jay_sensz If the polynomials are x^m + 1 and x^n + 1 for m and n odd, the roots are - e^(2 pi k i/ m) and - e^(2 pi l i/ n) for 0

@jay_sensz Ай бұрын

@@michaelz2270 Makes sense, thanks. I had a feeling the way I parameterized the roots was not ideal.

@skipugh 2 ай бұрын

Love your proofs. 😊

@sAm__ThaKuR66 Ай бұрын

At 7:07 why have u written the remainder in terms of (-) negative as remainder is always a positive number and euclidean theorem deals with remainder (positive) . Pls explain my misconception dude ❤❤❤❤

@BRUBRUETNONO 2 ай бұрын

Well explained and well done ! Greetings !

@vikramanbaburaj525 2 ай бұрын

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!

@dean532 2 ай бұрын

There’s a lot of “GCD-ing” (with e phase angles) involved when factoring out coefficients in Fourier Series analysis

@jeffreyfoster8413 24 күн бұрын

Not sure how involved it would be but might be nice to see the long division of both numbers.

@antonionavarro1000 2 ай бұрын

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.

@hacerkayal1740 2 ай бұрын

Sir where have you been?❤ I need your videos every day its like an addiction❤loveee

@ProactiveYellow 2 ай бұрын

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.

@joeschmo622 Ай бұрын

✨Magic!✨

@unnikrishnannk4354 2 ай бұрын

Beautiful !

@soilsurvivor 2 ай бұрын

Great fun! Thank you!

@topquark22 2 ай бұрын

You can do all this stuff, and long division with polynomials. I wish they would teach it that way.

@Abraham_bram 2 ай бұрын

Why the negative sign (-)not included in (x^26)-1

@makehimobsessedwithyou6412 2 ай бұрын

i also want to ask him

@josephw.3877 Ай бұрын

a (-) sign doesn’t affect a number’s divisors. keeping the highest power positive is a convention so it’s easier to follow

@holyshit922 2 ай бұрын

2:37 it matters if you use extended Euclidean algorithm

@kennethgee2004 2 ай бұрын

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.

@nadonadia2521 2 ай бұрын

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).

@raptor9514 2 ай бұрын

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

@nadonadia2521 2 ай бұрын

@@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.

@als2cents679 Ай бұрын

You had a negative remainder in the first step, which seems to be incorrect?

@niloneto1608 2 ай бұрын

Fun stuff, however when one replaces x for a number bigger than 1, the results doesn't quite match.

@surendrakverma555 2 ай бұрын

Thanks 🙏🙏🙏🙏

@mircoceccarelli6689 2 ай бұрын

👍👍👍

@Risu0chan 2 ай бұрын

HCF? Is it a new way to say GCD?

@DominickAngelo 2 ай бұрын

When you check , x+y=8 and XY=48, NOT 8. Confused me.

@Juman-oi5hw 2 ай бұрын

Wow, amazing

@Tosi31415 2 ай бұрын

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?

@pietergeerkens6324 2 ай бұрын

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

@Grecks75 2 ай бұрын

@@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.

@pietergeerkens6324 2 ай бұрын

@@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.

@lucapolidori8817 2 ай бұрын

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?

@lucapolidori8817 2 ай бұрын

Sorry, I've seen it already answered below.

@Grecks75 2 ай бұрын

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).

@Grecks75 2 ай бұрын

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.

@Grecks75 2 ай бұрын

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.