Introduction to number theory lecture 19. Hensel and Newton's method
HTML-код
- Опубликовано: 24 янв 2025
- This lecture is part of my Berkeley math 115 course "Introduction to number theory"
For the other lectures in the course see • Introduction to number...
We describe a method due to Hensel and Newton for lifting a solution of an equation mod p to a solution mod a power of p.
The textbook is "An introduction to the theory of numbers" by Niven, Zuckerman, and Montgomery (5th edition).
Will there be a course on algebraic number theory?
Yes! In about a month or so we're scheduled to record our Berkely Algebraic Number Theory Lesson
Yes please algebraic number theory very few lectures available on internet. Needed this very much specific graduate level course on it
Let x(1) be a solution of X(1)^2 = 7 (mod 3),
Let x(2) be a solution of X(2)^2 = 7 (mod 3^2),
Let x(3) be a solution of X(3)^2 = 7 (mod 3^3),
:
Let x(i) be a solution of X(i)^2 = 7 (mod 3^i),
:
Let x(n) be a solution of X(n)^2 = 7 ( mod 3^n).
If x(i+1) = x(i) (mod 3^i), then we call x(i+1) a” lift” of x(i).
Note that we can regard x(i) as an element of Z/3^iZ for any i = 1,2,3….
Assume that x(i+1) = x(i) (mod 3^i) for all i, then
x(2) = x(1) + 3a(1) for some a(1) = 1,2,3.
x(3) = x(2) + 3^2a(2) for some a(2) = 1,2,3.
:
And hence we get the following expansion.
x(n)=x(n-1) + 3^(n-1)a(n-1),
=x(n-2) + 3^(n-2)a(n-2) + 3^(n-1)a(n-1),
= … = x(1) + 3a(1) + 3^2a(2) + … + + 3^(n-2)a(n-2) + 3^(n-1)a(n-1)。
10:04~
Consider the equation X^2 = 17 ( mod 2^10).
Set f(X) := X^2, then the derivative 2X of f vanishes at X = 1 where X = 1 is a solution of X^2 = 17 (mod 2). Thus, we cannot apply Hensel’s lemma for X^2 = 17 ( mod 2^10).
10:04 The reason why 5 does not have any lift is that a lift should be congruent to 5 modulo 8, such a possible number in Z/16Z is 5 + 8 = 13 but 13 does not satisfy X^2 = 17 (mod 2^4), thus we cannot lift the solution 5.
Note that each number of the tree of 10:26 denotes one of the solution of X^2 = 17 (mod2^k) for k= 1,2,3….
X^2 = 17 (mod2^1) has a solution 1,
X^2 = 17 (mod2^2) has solutions, 1,3 and both of them are lift of 1, because 1 = 1 (mod 2) and 1 = 3 (mod2).
X^2 = 17 (mod2^3) has solutions, 1,5,3,7 and, e.g., 1 and 5 are lifts of 1, because 1 = 1 (mod 2^2) and 5 = 1 (mod2^2). Similarly, 3 and 7 in Z/8Z are lifts of 3 in Z/4Z.
And so on.
In the tree, if a solution is a lift of another solution, then they combined by a line.
Let f be a polynomial with integer coefficients.
Let p be a prime number.
For a given solution x(1) of the equation f(X) = 0 (mod p^n), try to find a solution f(X) = 0 (mod p^2n) with the condition X = x(1) (mod p^n).
From the condition X = x(1) (mod p^n), X = x(1) + ap^n for some a = 1,2,…,p^2n.
By Taylor expansion, f(x(1) + ap^n) = f(x(1)) + ap^nf’(x(1)) + (divisible terms by p^2n).
Note that if f is integer coefficients, then the terms (d/dx)^kf(x)/k! is also integer for all k, and hence the divisibility follows. 18:30
We get a necessary condition as f(x(1)) + ap^nf’(x(1)) = 0 (mod p^2n)
Because f(x(1)) = 0 mod p^n, f(x(1)) = p^nb for some b.
Thus p^nb + ap^nf’(x(1)) = 0 (mod p^2n),
that is, af’(x(1)) = b (mod p^n).
If, f’(x(1)) is nonzero modulo p^n, that is gcd(f’(x(1)), p ) = 1, then we can find a inverse multiple of f’(x(1)) in Z/pZ, and hence we get a = b/ f’(x(1)) (mod p).
Thus, we get a sufficient condition gcd（f（gcd(f’(x(1)), p ) = 1 to find a lift of x(1).
21:18 Typo? In X^2 = 5 ( mod 2^1) has a solution 1 at which the derivative of f(X) = X^2 -5 vanishes modulo 2. However, even if we cannot apply hensel’s lemma for X^2 = 5 ( mod 2^1) to find a lift of its solution x(1) = 1, we can find a lift x(2), that is, x(2) = x(1) (mod 1) and x(2)^2 = 5 (mod 2^2). In fact, x(2) = 1 is the desired lift.
Note that he said f’(x(1)) is not zero modulo 2…But in this context, this is typo. Because now, f(X) = X^2-5 and f’(X) = 2X and x(1) =1, then f’(x(1)) = 2 = 0 (mod 2).
I do not understand about the difference of Newton and Hensel’s methods.
Probably,
Using Newton’s methods, we can find a lift of solution from f(X) = 0 (mod p^n) to f(X) = 0 ( mod p^{n+1)).
Using Hensel’s method, we can find a lift of solution from f(X) = 0 (mod p^n) to f(X) = 0 ( mod p^2n).
yeeeeeeeeeeeeeee
When I win the field's medal i'll be posting videos just like this!
Good luck!
You don't have to win a fields medal in order to post a video on youtube. You can post it any time.