7:31 The interesting thing in the counterexample to having more roots of f(x) mod n when n is not a prime than the degree of f is that the fact that p was a prime wasn't used at all in the inductive step. The induction step actually holds regardless of whether or not p is prime. Rather it's in the base case when f(x) = ax + b that you need p to be prime, because ax = b (mod n) can have more than one solution when n isn't prime (e.g. 2x = 2 (mod 4) has both x=1 and x=3 as solutions.) So this is one of those unusual situations where being careful in the base case step of the induction proof is really, really important!
Doesnt the base case still holds for gcd(a, n) = 1? Bc when you have a linear congruence like this, ax = b (mod n) and gcd(a, n) = 1, there is a unique solution mod n. But the counterexample that he shown was exactly the case when gdc(a, n) = 1, but quadratic. Thats what i didnt understand.
@@lucasgodim7615 Looking at it more closely, it's because the proof is using the fact that p is prime when it says that f(x) = (x-a)g(x) = 0 mod p, it's saying p | (x-a)g(x) . Note that if p is prime, then Euclid's Lemma for Prime Divisors says if p|ab that either p | a or p | b. In this case that leads to saying p | (x-a) or p | g(x). Which means (x-a) = 0 mod p or g(x) = 0 mod p. The induction hypothesis then says g(x) = 0 has at most k roots, and (x-a) = 0 adds at most 1 additional root, so f(x) then has at most k+1 roots. But notice above that if we substitute p for n which isn't prime then it is not necessarily true that if n | (x-a)g(x) then n | (x-a) or n | g(x). It's possible for (x-a) to be a factor of n and g(x) to be a different factor of n for instance and neither is 0 mod n. In the counterexample in the video, we have f(x) = x² -1 = 0 mod 12 . Now consider that f(x) = (x-1)(x+1) when x = 5. (5-1) = 4 and (5+1) = 6. Neither is 0 mod 12 but multiplied together they include all the factors of 12, so their product is 0 mod 12. Hence f(x) = (x-1)g(x) where g(x) = (x+1) has more than just two solutions mod 12 because it's possible to select x such that neither (x-1) nor g(x) are 0 mod 12 but their product is. So you do need n to be a prime in that induction step, it's just obscured in the statement that since f(x) = (x-a)g(x) = 0 mod p that (x-a) = 0 mod p or g(x) = 0 mod p
@@Bodyknock Ok, now it makes sense. When he said that we really use the fact that p was prime, I tried to find where this fact was really useful for the proof, but I couldnt find it. Tks, now its clear.
I was a maths and quantitative finance major at university. I did mostly applied maths (optimisation, PDEs) and statistics subjects. I did the advanced second year Calculus and Algebra classes (as opposed to the standard level), but I stayed away from the Pure Maths subjects in Third Year. It's really fun browsing your channel. I never took these classes, but I am learning parts of them by browsing, and I can follow it pretty well. So nice seeing all the usual 'basic ingredients' like induction and taylor series. Brings back memories. I finished university six years ago.
29:10 alternatively if we don't want to redo Hensel's lemma for x == 3 (mod 5), we can actually factor f(x) knowing that f(92) == 0 (mod 125) Synthetic division on mod 125 also works, leading to x^2+15x+31== (x-92)(x-18) (mod 125)
The proposition after Hensel's Lemma also lets us see how (for p odd) (Z/pⁿZ)* is a cyclic group(†) of order p^{n-1} (p-1) which splits up as a product of two cyclic groups of orders p^{n-1} and p-1, the latter being (Z/pZ)*.. the projection onto which is really the restriction of the obvious «ring-map» :Z/pⁿZ -> Z/pZ to the groups of units, and the former the kernel of this map: ie. elements congruent to 1 (mod p) . Now in order for an element to have order dividing p-1, both coordinates must have that property-which is a-given for the (Z/pZ)* part, but implies that the first coordinate must be trivial as exponentiation to p-1 (which is just multiplying by p-1 in additive notation) acts as an isomorphism in a cyclic (or any abelian) group of order p^{n-1}, p-1 being coprime to it, thus giving us exactly p-1 such elements. Good work! 👍 [(†) the proof of this pretty much borrows the arguments of Hensel's Lemma and is often presented without it in a group theoretic context (a minor technicality prevents cyclicity in the p=2 case which becomes isomorphic to Z/2^{n-2}Z ⊕ Z/2Z, the (Z/2Z)* component being trivial of course). The subject takes off from there to p-adic numbers and the _strange_ spherical completions of Q. Hensel's lemma also goes its own way genaralizing over rings and ideals, even varieties and schemes, giving rise to I-adic completions and what are called “formal schemes” that algebraically brings in the core of the methods in analytic geometry.]
Spoiler alert. For those who want to check their working and answers to to the warm-ups, i.e. the other solution to x^2 + 15x + 31 ≡ 0 (mod 125); and the two solutions to (x^2 + 4x + 2 ≡ 0 mod 343). A. The other solution to f(x) = x^2 + 15x + 31 ≡ 0 (mod 125): Note that f'(x) = 2x + 15. A part 1. We already found that the solutions to x^2 + 15x + 31 ≡ 0 (mod 5) were x=2 and x=3, and we are asked to find the solutions arising from the x=3 branch. A part 2. Solve f(x) = x^2 + 15x + 31 ≡ 0 (mod 25). Using a=3 and m=1. We need to solve f'(a).t ≡ - f(a)/p^m (mod p) for t to generate the solution (mod p^(m+1)) which will be (a + t.p^m). Solve f'(3).t ≡ - f(3)/5^1 (mod 5). So 21.t ≡ - 85/5 (mod 5). That gives t ≡ -17 ≡ -2 ≡ 3 (mod 5). So the other solution to x^2 + 15x + 31 ≡ 0 (mod 25) is (3 + 3*5^1) = 18. Check: f(18) = 625 ≡ 0 (mod 25). A part 3. Solve f(x) = x^2 + 15x + 31 ≡ 0 (mod 125). Using a=18 and m=2. We need to solve f'(a).t ≡ - f(a)/p^m (mod p) for t to generate the solution (mod p^(m+1)) which will be (a + t.p^m). Solve f'(18).t ≡ - f(18)/5^2 (mod 5). So 51.t ≡ - 625/25 (mod 5). That gives t ≡ -25 ≡ 0 (mod 5). So the other solution to x^2 + 15x + 31 ≡ 0 (mod 25) is (18 + 0*5^2) = 18. Check: f(18) = 625 ≡ 0 (mod 125). B. The two solutions to f(x) = x^2 + 4x + 2 ≡ 0 (mod 343). Note that the degree of f(x) is 2, so we have at most 2 solutions; and that f'(x) = 2x + 4. B part 1. Solve f(x) = x^2 + 4x + 2 ≡ 0 (mod 7). Trying x = 0, 1, ... 6, we find solutions at x=1 and x=2 (and of course we could stop there without trying 3, 4, 5, 6). B part 2a. Solve f(x) = x^2 + 4x + 2 ≡ 0 (mod 49). Using a=1 and m=1. We need to solve f'(a).t ≡ - f(a)/p^m (mod p) for t to generate the solution (mod p^(m+1)) which will be (a + t.p^m). Solve f'(1).t ≡ - f(1)/7^1 (mod 7). So 6t ≡ -7/7 ≡ -1 ≡ 6 (mod 7). That gives t = 1, and therefore the first solution to f(x) ≡ 0 (mod 49) is (1 + 1.7^1) = 8. Check: f(8) = 98 ≡ 0 (mod 49). B part 2b. Solve f(x) = x^2 + 4x + 2 ≡ 0 (mod 49). Using a=2 and m=1. We need to solve f'(a).t ≡ - f(a)/p^m (mod p) for t to generate the solution (mod p^(m+1)) which will be (a + t.p^m). Solve f'(2).t ≡ - f(2)/7^1 (mod 7). So 8t ≡ t ≡ -14/7 ≡ -2 ≡ 5 (mod 7). That gives t = 5, and therefore the second solution to f(x) ≡ 0 (mod 49) is (2 + 5.7^1) = 37. Check: f(37) = 1519 ≡ 0 (mod 49). B part 3a. Solve f(x) = x^2 + 4x + 2 ≡ 0 (mod 343). Using a=8 and m=2. We need to solve f'(a).t ≡ - f(a)/p^m (mod p) for t to generate the solution (mod p^(m+1)) which will be (a + t.p^m). Solve f'(8).t ≡ - f(8)/7^2 (mod 7). So 20t ≡ -98/49 ≡ -2 (mod 7). But 20t ≡ -t. So -t ≡ -2 (mod 7). That gives t = 2, and therefore the first solution to f(x) ≡ 0 (mod 343) is (8 + 2.7^2) = 106. Check: f(106) = 11662 ≡ 0 (mod 343). B part 3b. Solve f(x) = x^2 + 4x + 2 ≡ 0 (mod 343). Using a=37 and m=2. We need to solve f'(a).t ≡ - f(a)/p^m (mod p) for t to generate the solution (mod p^(m+1)) which will be (a + t.p^m). Solve f'(37).t ≡ - f(37)/7^2 (mod 7). So 78t ≡ -1519/49 ≡ -2 (mod 7). So t ≡ -31 (mod 7). That gives t = 4, and therefore the second solution to f(x) ≡ 0 (mod 343) is (37 + 4.7^2) = 233. Check: f(233) = 55223 ≡ 0 (mod 343).
In this case, it is indeed important that p is prime, since we cannot conclude otherwise that, since (x-a) and g(x) are integers, then if their product is divisible by p, then at least one must be.
Isn’t Langrange’s Theorem basically a lemma from the Fundamental Theorem of Algebra? Since every n-degree polynomial has n roots, in (mod p) the polynomial has at most n roots because not all of the roots may be integer.
Unfortunately this argument doesn't work because you can have more solutions in mod _k_ than not in mod _k_ . For example consider f(x) = x^2 - 1; over *Z* (or, if you like, over *C* ) it has two solutions: x = 1 and x = -1, but in mod 8 it has four solutions: x ≡ 1, x ≡ -1 ≡ 7, x ≡ 3, and x ≡ -3 ≡ 5. Lagrange's theorem is a corollary of a more general result though, namely that any polynomial of degree _n_ over a "field" has at most _n_ solutions - Lagrange's theorem is just the case where the field is *Z* /p *Z* , and the hypothesis that the leading coefficient is not divisible by _p_ ensures that the degree of _f_ over *Z* /p *Z* is the same as its degree over *Z*
I'ts unbelievable the number of Adds I am having while following your videos. almost every 2 mins I get one Add. Almost I watch more than 5 of your vidéos a day. The problem is that to happens while I am focusing enough on the blackboard.
I thought at first that the last part of the proof of the theorem that x^(p-1)≡-1 (mod p^m) has exactly p-1 roots (once you have found p-1 roots) followed straight from Lagrange's theorem, proved at the start of the video. However, this is actually not the case, since Lagrange's theorem applies mod p, not mod p^m.
In your proof of the lagrange's theorem, nothing stood out that p as in (mod p) needs to be a prime number in order for the theorem to hold true. While you gave an example how a non prime mod broke the theorem, it still lacks proper explanation.
Over any ring (you know a set where operations are defined so you can talk about addition/subtraction/multiplication seamlessly), it is defined as n a_n x^{n-1} + ... + a_1, where f=a_nxⁿ+···+a_0. (ie. defined to be 0 for n nx^{n-1}.)
@@nnaammuuss Age is not relevant here, and although I'm almost certainly older than you, I'm not going to patronise you. I'm merely going to observe that when somebody asks a question in good faith - and we should assume good faith, unless shown otherwise - the best reply is an answer, not another question. The answer to @Cletus Humphrey is simply "Yes, that's correct", and if you feel further elaboration is required, perhaps a pointer to a discussion of reduced residue systems, that I'm sure you're quite able to find. That way, nobody will feel belittled, and you will have the satisfaction of having helped someone who needed an answer.
@@RexxSchneider goodness and faith are subhuman excuses for cheap dishonesty-just what fills the churches with pedophiles with inept god talk. Same goes for your phrase ‘I'm not going to patronise you’, and going ahead with a foolish idea that it was very cleverly put. Unfortunately you are nowhere near the qualification to _‘patronise’_ any educated person, and foolish enough not to understand that, none of the above talk was about age, that you'd be given no license based on that even if you ‘cleverly’ allude to it, that you have no idea what my age is and quickly jumping to arbitrary conclusions about it is not going to paralyze anybody's intellect in a math forum, that the question was asked _because,_ the original question was so misplaced given the discussion in the video that clarifying the confusion would only require repeating what has already been said, that _‘inferring’_ therefore anybody needs tutorials on primary school modular arithmetic would only prove you incapable inference-the main trait separating human beings from monkeys, and that it is not that educated fellows don't _‘‘understand’_ your foolish culture, but when they defy it it's because they'll _not_ care about the silly dishonesties handed over by your grandfather. So keep your peasant talk in your pocket-I would have been kinder to your type if you were merely foolish, but the tears of too many children harden my pity-it is out of the question encouraging you and your type.
34:20 So is f(92) the only solution to when f is congruent to 0 mod 125? I thought there were supposed to be two because f is quadratic? Is it like the other solution is imaginary or something?
@Alain Rogez: Yes it is. Some polynomials that are congruent to zero (mod a non-prime) might have a number of distinct solutions that is no more than the degree of f(x), but the number of distinct solutions could be greater than the degree of f(x). We have no simple way of predicting which. Distinct solutions are those not congruent to each other mod p. The result that the number of distinct solutions is no more than the degree of f(x) is only guaranteed when p is prime and at least one of the coefficients of f(x) is not divisible by p.
Since the degree of f(x) is 2, there are at most 2 solutions. To solve the congruence f(x) = x^2 + 15x + 31 ≡ 0 (mod 125), we start by finding the solutions to f(x) ≡ 0 (mod 5), which are x=2 and x=3. We then use a=2 to generate a solution to f(x) ≡ 0 (mod 25). You find t=3, and that gives (2 + 3*5), which is x=17. We then use a=3 to generate a solution to f(x) ≡ 0 (mod 25). You find t=3, and that gives (3 + 3*5), which is x=18. We then use a=17 to generate a solution to f(x) ≡ 0 (mod 125). You find t=3, and that gives (17 + 3*25), which is x=92. We then use a=18 to generate a solution to f(x) ≡ 0 (mod 125). You find t=0, and that gives (18 + 0*5), which is x=18. So the two solutions to x^2 + 15x + 31 ≡ 0 (mod 125) are x=18 and x=92. It should be obvious with only two solutions which is the smaller. I have to admit I have no way of predicting which solution of x^2 + 15x + 31 ≡ 0 (mod 5) will result in the smaller solution to x^2 + 15x + 31 ≡ 0 (mod 125).
@@anshumanagrawal346 yeah but if you define the formal derivative of a polynomial, then the equality michael used in the video can be derived easily from just calculations, you do not need the theorems from analysis to do that
@@rickdoesmath3945 That's still cheating. For his Number Theory course-of which this video is #15 in the series-Michael started with Peano Axioms. Everything has been developed step-by-step starting with that. (He does use Set Theory notation, but that's for convenience only; so far he hasn't used any significant results from set theory.) In this course, till now, he hasn't defined real numbers. So the algebra of real numbers, including polynomials of real numbers, as well as calculus, haven't been defined yet. In fact, in another video (not part of this Number Theory course), Michael showed that limits and derivatives cannot be rigorously defined with rationals alone. So when he says "I'm sure you've done a course on calculus. so let's use Taylor's Series"-that's highly improper. He's asking you to take a big leap of faith. We're supposed to believe that using the lessons of the previous videos-1 through 14-you can take a detour, develop real numbers, limits, and calculus, and come back to lesson #15 without any loss of rigor. I personally don't have a problem with it-I'm an engineer after all, and useful *results* are more important to me than the *process* used to prove them. But for a mathematician-that's very unusual, to say the least.
@@nHans We do not need limits to do what he has done in this video. We can just *define* the derivative of a polynomial p(x) = a_n x^n +... +a_0 to be the polynomial q(x) = na_n x^(n-1) +... + a_1 and then the Taylor formula can be proven by simple calculations. This is done a lot of times in abstract algebra, especially in ring theory, where its impossibile to define limits. We don't care about real numbers here. We just care about this equality. Moreover, this video series is made to support a course he is teaching on number theory to students who already know their real analysis.
Nice! This is how Hensel came up with the p-adic numbers. The "why" of the p-adics is solving polynomial equations from congruence solutions :D
7:31 The interesting thing in the counterexample to having more roots of f(x) mod n when n is not a prime than the degree of f is that the fact that p was a prime wasn't used at all in the inductive step. The induction step actually holds regardless of whether or not p is prime. Rather it's in the base case when f(x) = ax + b that you need p to be prime, because ax = b (mod n) can have more than one solution when n isn't prime (e.g. 2x = 2 (mod 4) has both x=1 and x=3 as solutions.)
So this is one of those unusual situations where being careful in the base case step of the induction proof is really, really important!
Doesnt the base case still holds for gcd(a, n) = 1? Bc when you have a linear congruence like this, ax = b (mod n) and gcd(a, n) = 1, there is a unique solution mod n. But the counterexample that he shown was exactly the case when gdc(a, n) = 1, but quadratic. Thats what i didnt understand.
@@lucasgodim7615 Looking at it more closely, it's because the proof is using the fact that p is prime when it says that f(x) = (x-a)g(x) = 0 mod p, it's saying p | (x-a)g(x) . Note that if p is prime, then Euclid's Lemma for Prime Divisors says if p|ab that either p | a or p | b. In this case that leads to saying p | (x-a) or p | g(x). Which means (x-a) = 0 mod p or g(x) = 0 mod p. The induction hypothesis then says g(x) = 0 has at most k roots, and (x-a) = 0 adds at most 1 additional root, so f(x) then has at most k+1 roots.
But notice above that if we substitute p for n which isn't prime then it is not necessarily true that if n | (x-a)g(x) then n | (x-a) or n | g(x). It's possible for (x-a) to be a factor of n and g(x) to be a different factor of n for instance and neither is 0 mod n.
In the counterexample in the video, we have f(x) = x² -1 = 0 mod 12 . Now consider that f(x) = (x-1)(x+1) when x = 5. (5-1) = 4 and (5+1) = 6. Neither is 0 mod 12 but multiplied together they include all the factors of 12, so their product is 0 mod 12. Hence f(x) = (x-1)g(x) where g(x) = (x+1) has more than just two solutions mod 12 because it's possible to select x such that neither (x-1) nor g(x) are 0 mod 12 but their product is.
So you do need n to be a prime in that induction step, it's just obscured in the statement that since f(x) = (x-a)g(x) = 0 mod p that (x-a) = 0 mod p or g(x) = 0 mod p
@@Bodyknock Ok, now it makes sense. When he said that we really use the fact that p was prime, I tried to find where this fact was really useful for the proof, but I couldnt find it. Tks, now its clear.
I was a maths and quantitative finance major at university. I did mostly applied maths (optimisation, PDEs) and statistics subjects. I did the advanced second year Calculus and Algebra classes (as opposed to the standard level), but I stayed away from the Pure Maths subjects in Third Year.
It's really fun browsing your channel. I never took these classes, but I am learning parts of them by browsing, and I can follow it pretty well. So nice seeing all the usual 'basic ingredients' like induction and taylor series.
Brings back memories. I finished university six years ago.
Same here, I didn’t do any number theory but am just doing it myself now. It is actually really interesting
34:28 Homework
34:50 Good Place To Stop
29:10 alternatively if we don't want to redo Hensel's lemma for x == 3 (mod 5), we can actually factor f(x) knowing that f(92) == 0 (mod 125)
Synthetic division on mod 125 also works, leading to x^2+15x+31== (x-92)(x-18) (mod 125)
Actually, the other root can be found in a slightly easier way. We know the two roots add up to -15≡110(mod 125).
@@MichaelRothwell1what does this (mod __) mean?
@@imauz1127 See here en.m.wikipedia.org/wiki/Modular_arithmetic
@@MichaelRothwell1 thank you
The proposition after Hensel's Lemma also lets us see how (for p odd) (Z/pⁿZ)* is a cyclic group(†) of order p^{n-1} (p-1) which splits up as a product of two cyclic groups of orders p^{n-1} and p-1, the latter being (Z/pZ)*.. the projection onto which is really the restriction of the obvious «ring-map» :Z/pⁿZ -> Z/pZ to the groups of units, and the former the kernel of this map: ie. elements congruent to 1 (mod p) . Now in order for an element to have order dividing p-1, both coordinates must have that property-which is a-given for the (Z/pZ)* part, but implies that the first coordinate must be trivial as exponentiation to p-1 (which is just multiplying by p-1 in additive notation) acts as an isomorphism in a cyclic (or any abelian) group of order p^{n-1}, p-1 being coprime to it, thus giving us exactly p-1 such elements. Good work! 👍
[(†) the proof of this pretty much borrows the arguments of Hensel's Lemma and is often presented without it in a group theoretic context (a minor technicality prevents cyclicity in the p=2 case which becomes isomorphic to Z/2^{n-2}Z ⊕ Z/2Z, the (Z/2Z)* component being trivial of course). The subject takes off from there to p-adic numbers and the _strange_ spherical completions of Q. Hensel's lemma also goes its own way genaralizing over rings and ideals, even varieties and schemes, giving rise to I-adic completions and what are called “formal schemes” that algebraically brings in the core of the methods in analytic geometry.]
that's actually a good introduction to p-adic numbers. hensel's lemma is very useful to find solutions to polynomials in that field.
this is such a good explanation of hensel's lemma that helps me understand p-adic numbers way better
Spoiler alert.
For those who want to check their working and answers to to the warm-ups, i.e. the other solution to x^2 + 15x + 31 ≡ 0 (mod 125); and the two solutions to (x^2 + 4x + 2 ≡ 0 mod 343).
A. The other solution to f(x) = x^2 + 15x + 31 ≡ 0 (mod 125): Note that f'(x) = 2x + 15.
A part 1. We already found that the solutions to x^2 + 15x + 31 ≡ 0 (mod 5) were x=2 and x=3, and we are asked to find the solutions arising from the x=3 branch.
A part 2. Solve f(x) = x^2 + 15x + 31 ≡ 0 (mod 25). Using a=3 and m=1. We need to solve f'(a).t ≡ - f(a)/p^m (mod p) for t to generate the solution (mod p^(m+1)) which will be (a + t.p^m).
Solve f'(3).t ≡ - f(3)/5^1 (mod 5). So 21.t ≡ - 85/5 (mod 5). That gives t ≡ -17 ≡ -2 ≡ 3 (mod 5). So the other solution to x^2 + 15x + 31 ≡ 0 (mod 25) is (3 + 3*5^1) = 18.
Check: f(18) = 625 ≡ 0 (mod 25).
A part 3. Solve f(x) = x^2 + 15x + 31 ≡ 0 (mod 125). Using a=18 and m=2. We need to solve f'(a).t ≡ - f(a)/p^m (mod p) for t to generate the solution (mod p^(m+1)) which will be (a + t.p^m).
Solve f'(18).t ≡ - f(18)/5^2 (mod 5). So 51.t ≡ - 625/25 (mod 5). That gives t ≡ -25 ≡ 0 (mod 5). So the other solution to x^2 + 15x + 31 ≡ 0 (mod 25) is (18 + 0*5^2) = 18.
Check: f(18) = 625 ≡ 0 (mod 125).
B. The two solutions to f(x) = x^2 + 4x + 2 ≡ 0 (mod 343). Note that the degree of f(x) is 2, so we have at most 2 solutions; and that f'(x) = 2x + 4.
B part 1. Solve f(x) = x^2 + 4x + 2 ≡ 0 (mod 7). Trying x = 0, 1, ... 6, we find solutions at x=1 and x=2 (and of course we could stop there without trying 3, 4, 5, 6).
B part 2a. Solve f(x) = x^2 + 4x + 2 ≡ 0 (mod 49). Using a=1 and m=1. We need to solve f'(a).t ≡ - f(a)/p^m (mod p) for t to generate the solution (mod p^(m+1)) which will be (a + t.p^m).
Solve f'(1).t ≡ - f(1)/7^1 (mod 7). So 6t ≡ -7/7 ≡ -1 ≡ 6 (mod 7). That gives t = 1, and therefore the first solution to f(x) ≡ 0 (mod 49) is (1 + 1.7^1) = 8.
Check: f(8) = 98 ≡ 0 (mod 49).
B part 2b. Solve f(x) = x^2 + 4x + 2 ≡ 0 (mod 49). Using a=2 and m=1. We need to solve f'(a).t ≡ - f(a)/p^m (mod p) for t to generate the solution (mod p^(m+1)) which will be (a + t.p^m).
Solve f'(2).t ≡ - f(2)/7^1 (mod 7). So 8t ≡ t ≡ -14/7 ≡ -2 ≡ 5 (mod 7). That gives t = 5, and therefore the second solution to f(x) ≡ 0 (mod 49) is (2 + 5.7^1) = 37.
Check: f(37) = 1519 ≡ 0 (mod 49).
B part 3a. Solve f(x) = x^2 + 4x + 2 ≡ 0 (mod 343). Using a=8 and m=2. We need to solve f'(a).t ≡ - f(a)/p^m (mod p) for t to generate the solution (mod p^(m+1)) which will be (a + t.p^m).
Solve f'(8).t ≡ - f(8)/7^2 (mod 7). So 20t ≡ -98/49 ≡ -2 (mod 7). But 20t ≡ -t. So -t ≡ -2 (mod 7). That gives t = 2, and therefore the first solution to f(x) ≡ 0 (mod 343) is (8 + 2.7^2) = 106.
Check: f(106) = 11662 ≡ 0 (mod 343).
B part 3b. Solve f(x) = x^2 + 4x + 2 ≡ 0 (mod 343). Using a=37 and m=2. We need to solve f'(a).t ≡ - f(a)/p^m (mod p) for t to generate the solution (mod p^(m+1)) which will be (a + t.p^m).
Solve f'(37).t ≡ - f(37)/7^2 (mod 7). So 78t ≡ -1519/49 ≡ -2 (mod 7). So t ≡ -31 (mod 7). That gives t = 4, and therefore the second solution to f(x) ≡ 0 (mod 343) is (37 + 4.7^2) = 233.
Check: f(233) = 55223 ≡ 0 (mod 343).
Really nice. I don't know you want to stop but a proof of Zsygmondy theorem would be awesome. Thanks Michael !
In this case, it is indeed important that p is prime, since we cannot conclude otherwise that, since (x-a) and g(x) are integers, then if their product is divisible by p, then at least one must be.
What a wonderful video, clearly explained, fantastic!!!
0:32 "a Polynomial with integer roots". Doesn't Z[x] denote the set of polynomials with integer coefficients?
I thought I was the only one who pointed that out.
Yeah, 😊 ...just a slip-of-tongue I guess.
A series on algebra will be helpful
At 24:00 we're supposed to argue f'(xi) is not 0 mod p, as opposed to p^k.
Isn’t Langrange’s Theorem basically a lemma from the Fundamental Theorem of Algebra? Since every n-degree polynomial has n roots, in (mod p) the polynomial has at most n roots because not all of the roots may be integer.
Unfortunately this argument doesn't work because you can have more solutions in mod _k_ than not in mod _k_ . For example consider f(x) = x^2 - 1; over *Z* (or, if you like, over *C* ) it has two solutions: x = 1 and x = -1, but in mod 8 it has four solutions: x ≡ 1, x ≡ -1 ≡ 7, x ≡ 3, and x ≡ -3 ≡ 5.
Lagrange's theorem is a corollary of a more general result though, namely that any polynomial of degree _n_ over a "field" has at most _n_ solutions - Lagrange's theorem is just the case where the field is *Z* /p *Z* , and the hypothesis that the leading coefficient is not divisible by _p_ ensures that the degree of _f_ over *Z* /p *Z* is the same as its degree over *Z*
@@schweinmachtbree1013 forgot about this comment, but that makes sense. Thanks!
Please do not use f(x) to refer to the function. f(x) is a concrete number. The function itself is called f.
I'ts unbelievable the number of Adds I am having while following your videos. almost every 2 mins I get one Add. Almost I watch more than 5 of your vidéos a day. The problem is that to happens while I am focusing enough on the blackboard.
It is quite believable since that is how CZcamsrs get paid. Spend the money to get ad free service rather than whine.
I thought at first that the last part of the proof of the theorem that x^(p-1)≡-1 (mod p^m) has exactly p-1 roots (once you have found p-1 roots) followed straight from Lagrange's theorem, proved at the start of the video. However, this is actually not the case, since Lagrange's theorem applies mod p, not mod p^m.
In your proof of the lagrange's theorem, nothing stood out that p as in (mod p) needs to be a prime number in order for the theorem to hold true. While you gave an example how a non prime mod broke the theorem, it still lacks proper explanation.
How is the derivative of f(x) defined, when it operates on congruence classes?
Over any ring (you know a set where operations are defined so you can talk about addition/subtraction/multiplication seamlessly), it is defined as n a_n x^{n-1} + ... + a_1, where f=a_nxⁿ+···+a_0.
(ie. defined to be 0 for n nx^{n-1}.)
When we say x^(p-1) ≡ 1 (mod p^m) has exactly p-1 solutions, are those solutions unique up to congruence mod p^m?
I'm sorry, but what else could it possibly mean? 😊
@@nnaammuuss watch your attitude kid
@@cletushumphrey9163 tut, tut, that's presumptive my child.
@@nnaammuuss Age is not relevant here, and although I'm almost certainly older than you, I'm not going to patronise you. I'm merely going to observe that when somebody asks a question in good faith - and we should assume good faith, unless shown otherwise - the best reply is an answer, not another question.
The answer to @Cletus Humphrey is simply "Yes, that's correct", and if you feel further elaboration is required, perhaps a pointer to a discussion of reduced residue systems, that I'm sure you're quite able to find. That way, nobody will feel belittled, and you will have the satisfaction of having helped someone who needed an answer.
@@RexxSchneider goodness and faith are subhuman excuses for cheap dishonesty-just what fills the churches with pedophiles with inept god talk. Same goes for your phrase ‘I'm not going to patronise you’, and going ahead with a foolish idea that it was very cleverly put. Unfortunately you are nowhere near the qualification to _‘patronise’_ any educated person, and foolish enough not to understand that, none of the above talk was about age, that you'd be given no license based on that even if you ‘cleverly’ allude to it, that you have no idea what my age is and quickly jumping to arbitrary conclusions about it is not going to paralyze anybody's intellect in a math forum, that the question was asked _because,_ the original question was so misplaced given the discussion in the video that clarifying the confusion would only require repeating what has already been said, that _‘inferring’_ therefore anybody needs tutorials on primary school modular arithmetic would only prove you incapable inference-the main trait separating human beings from monkeys, and that it is not that educated fellows don't _‘‘understand’_ your foolish culture, but when they defy it it's because they'll _not_ care about the silly dishonesties handed over by your grandfather. So keep your peasant talk in your pocket-I would have been kinder to your type if you were merely foolish, but the tears of too many children harden my pity-it is out of the question encouraging you and your type.
8:00 shouldn't it say that a is an integer?!
Otherwise in the proof, a^(r-k) might not be an integer.
Equivalent wording is leading coefficient not congruent to 0 mod p.
if x^2 = a ( mod p ) then ( p - x )^2 = a ( mod p ) also
34:20 So is f(92) the only solution to when f is congruent to 0 mod 125? I thought there were supposed to be two because f is quadratic? Is it like the other solution is imaginary or something?
It looks like he was only building up solutions using the solution using x=2 (mod 5). To get the other solution, you would build up using x=3 (mod 5)
@@robertmauck4975 Oh ok thanks!
The other solution is x=18 - I'll make a full post giving the full solutions to the warm-ups if you want to check your answers.
The other root can be easily found to be 18, since the two roots add up to -15≡110(mod 125).
Your proof is very interesting,....
Can we let p approach infinity and somehow use the Fundamental Theorem of Algebra as an argument?
Hi....thank you ....Can u give us vidéos about tribes ans Lebesgue integral
In Lagrange theorem, p is prime?
@Alain Rogez: Yes it is. Some polynomials that are congruent to zero (mod a non-prime) might have a number of distinct solutions that is no more than the degree of f(x), but the number of distinct solutions could be greater than the degree of f(x). We have no simple way of predicting which. Distinct solutions are those not congruent to each other mod p.
The result that the number of distinct solutions is no more than the degree of f(x) is only guaranteed when p is prime and at least one of the coefficients of f(x) is not divisible by p.
How to find the smallest solution? f(92) = 9875 but I found f(18) = 625
Since the degree of f(x) is 2, there are at most 2 solutions.
To solve the congruence f(x) = x^2 + 15x + 31 ≡ 0 (mod 125), we start by finding the solutions to f(x) ≡ 0 (mod 5), which are x=2 and x=3.
We then use a=2 to generate a solution to f(x) ≡ 0 (mod 25). You find t=3, and that gives (2 + 3*5), which is x=17.
We then use a=3 to generate a solution to f(x) ≡ 0 (mod 25). You find t=3, and that gives (3 + 3*5), which is x=18.
We then use a=17 to generate a solution to f(x) ≡ 0 (mod 125). You find t=3, and that gives (17 + 3*25), which is x=92.
We then use a=18 to generate a solution to f(x) ≡ 0 (mod 125). You find t=0, and that gives (18 + 0*5), which is x=18.
So the two solutions to x^2 + 15x + 31 ≡ 0 (mod 125) are x=18 and x=92. It should be obvious with only two solutions which is the smaller.
I have to admit I have no way of predicting which solution of x^2 + 15x + 31 ≡ 0 (mod 5) will result in the smaller solution to x^2 + 15x + 31 ≡ 0 (mod 125).
Knowing one root, the other root is easily found using the fact that the two roots add up to -15≡110(mod 125).
o, you have to know calc 2 to watch this, rip.
no you don't, just use the formal definition of the derivative
@@rickdoesmath3945 Taylor series
@@anshumanagrawal346 yeah but if you define the formal derivative of a polynomial, then the equality michael used in the video can be derived easily from just calculations, you do not need the theorems from analysis to do that
@@rickdoesmath3945 That's still cheating. For his Number Theory course-of which this video is #15 in the series-Michael started with Peano Axioms. Everything has been developed step-by-step starting with that. (He does use Set Theory notation, but that's for convenience only; so far he hasn't used any significant results from set theory.)
In this course, till now, he hasn't defined real numbers. So the algebra of real numbers, including polynomials of real numbers, as well as calculus, haven't been defined yet.
In fact, in another video (not part of this Number Theory course), Michael showed that limits and derivatives cannot be rigorously defined with rationals alone.
So when he says "I'm sure you've done a course on calculus. so let's use Taylor's Series"-that's highly improper. He's asking you to take a big leap of faith. We're supposed to believe that using the lessons of the previous videos-1 through 14-you can take a detour, develop real numbers, limits, and calculus, and come back to lesson #15 without any loss of rigor.
I personally don't have a problem with it-I'm an engineer after all, and useful *results* are more important to me than the *process* used to prove them. But for a mathematician-that's very unusual, to say the least.
@@nHans We do not need limits to do what he has done in this video. We can just *define* the derivative of a polynomial p(x) = a_n x^n +... +a_0 to be the polynomial q(x) = na_n x^(n-1) +... + a_1 and then the Taylor formula can be proven by simple calculations. This is done a lot of times in abstract algebra, especially in ring theory, where its impossibile to define limits. We don't care about real numbers here. We just care about this equality. Moreover, this video series is made to support a course he is teaching on number theory to students who already know their real analysis.