%%visits: 8 ## intuition Hensels_lemma is used to solve equations f(x) ≡ 0 mod pa where f(x) ∈ ℤ[x] and p is prime.
Let f(x) = anxn + an − 1xn − 1 + … + a1x + a0. Recall, f′(x) = nanxn − 1 + … + a1
Solve f(x) ≡ 0 mod m. chinese_remainder_theorem allows us to find pjaj. Hensels_lemma allows higher primes from a given prime. And chinese_remainder_theorem allows combining other primes.
Hensels_lemma has a connection to Newtons_method from calculus.
For Henzels_lemma use x2 = x1 − f(x1)u
x1 is solution in p
f(x1) is not congruent
u is the inverse of f’(x) mod 31 ## rigour ## exam clinic There are at most p solutions.
Show that there are infinitely primes of the form 6k − 1 with k positive integers.
Assume there are finitely many primes of this form p, p1…, pn
N = 6p, …pn − 1
N ≡ 2 mod 3 N ≡ 2 mod 3
Let p|N then p ≠ p1, …, pn
p can be in the class 1 mod 6 only
Multiplying
tags :math:
Let an, an − 1, an − 2…a1, a0 ∈ ℤ
f(x) = anxn + an − 1xn − 1 + an − 2xn − 2 + … + +a1x + a0
f′(x) = nanxn − 1 + (n − 1)an − 1xn − 2 + … + a1
if r = 1 then solve by trial and error
Since x2 ∈ ℤ, p2|f(x2) then p|f(x2)
We need to understand Residue classes ℤp ad ℤp2 together.
every element in ℤp gets mapped to p lots of numbers.
Henzels_lemma if there is a solution in mod p, then there are one solution in mod p 2
Ex. Let f(x) = x2 + x + 5 find all solutions to f(x) ≡ 0 mod 112
Solve for f(x) ≅ 0 mod 11. We find solutions X1 = 2, 8inℤ11
Can we use [Henzels_lemma]? well, we run the Henzels_lemma process for each solution. If f′(x1) ≅ 0 mod p, we cannot use Henzels_lemma, otherwise we can. f′(x = 2) = 2x + 1 = 5 ≅ 0 mod 11. So we use Henzels_lemma. X2 = X1 − f(X1) ⋅ u so u ⋅ f′(x1) ≡ 1 mod 11. We know u = −2 sub it back in X2 = 2 − (22 + 2 + 5)(−2) so the solution is 24 for the first element.
Case 2) the same process, check if you get $X_1 = 8 X_2 = 96 $ so there are 2 solutions mo
Note that when in Henzels_lemma when pr and r is a multiple of
If f(X1) ≡ 0 mod p and f′(x) ≡ 0 mod p, then lemma 3.7 so ⟹ f(x1 + tp) ≡ f(x1) + [pf′(x1)t = 0] ≡ f(x)
Case 1: if $f(x) $ then f(x1 + tp) ≡ 0 mod p2 so all the numbers are solutions (above x1)
Case 2: If f(x1) ≅ 0 mod p2 then f(x1 + tp) ≅ 0 mod p2
Example of this property
Let f(x) = x3 − 2x2 + x Find all solutions to f(x) ≅ 0 mod 32
find solutions for x ≡ 3 which are 0, 1 mod 3.
Check to apply Henzels_lemma.
When x1 = 0 so we check f′(x1) ≡ 0 mod 3
f′(x) = 3x2 − 4x + 1 which is 1 mod 3
Apply the equation X2 = X1 − f(x1) ⋅ u use the divides relation
Case X1 = 1
We check f′(x1) = 0 then we can’t use Henzels_lemma, so now we have to just check if f(x1) = 0 mod p2.