Hensel’s Lemma is a result that stipulates conditions for roots of polynomials modulo powers of primes to be “lifted” to roots modulo higher powers. The lifting method outlined in the proof is reminiscent of Newton’s Method for solving equations. Say the equations of the below type is to be solved:
The idea is to use Hensel’s Lemma to solve this type of congruence. It is also known as Hensel’s “lifting” lemma, which is a result of modular arithmetic. If f is a polynomial function and p is a Prime Number, then if f(a1) = 0 (mod p) and [f'(a1)] mod p != 0, then it’s possible to “lift” this solution to the solution for f(x) = 0 (mod pk) by using the below recursion. Note that the [f'(a1)]-1 refers to the modular inverse of f ‘(a1) modulo p.
![a_k + 1 = a_k - f(a_k) * [f'(a_1)]^{-1} (mod \; p^{k+1})](https://geeksforgeeks.org/wp-content/uploads/2023/10/dominic_rubhabha_quicklatex.com-9622ca979ba972b287b11a44786fed05_l3.png "Rendered by QuickLaTeX.com")
Example 1:
First, solve for (x = 2 is the solution for mod 5)
=>
=>
=>
=>
=>
=>
![a_2 = 2 - f(2)[f'(2)]^{-1} mod \; 25](https://geeksforgeeks.org/wp-content/uploads/2023/10/wardslaus_rubhabha_quicklatex.com-076f9632235cd58179425c1ffa270997_l3.png "Rendered by QuickLaTeX.com")
Example 2:
This has no solution as (x3 – 3) % mod 7 = 0 has no solution
Below is the implementation of Hensel’s Lemma:
C++
// C++ program to illustrate the// Hensel's Lemma#include <bits/stdc++.h>using namespace std;// Consider f(x) = x ^ 3 - k,// where k is a constant// Function to find the modular// inverse of a modulo mint inv(int a, int m){ int m0 = m, t, q; int x0 = 0, x1 = 1; if (m == 1) return 0; // Apply the Euclidean algorithm, // to find the modular inverse while (a > 1) { q = a / m; t = m; m = a % m; a = t; t = x0; x0 = x1 - q * x0; x1 = t; } if (x1 < 0) x1 += m0; return x1;}// Function to find the derivative of// f(x) and f'(x) = 3 * (x ^ 2)int derivative(int x){ return 3 * x * x;}// Function to find the image of// x in f(x) = x ^ 3 - k.int Image(int x, int k){ return x * x * x - k;}// Function to find the next power// of the numberint next_power(int a_t, int t, int a1, int prime, int k){ // Next power of prime for which // solution is to be found int power_p = (int)pow(prime, t + 1); // Using Hensel's recursion to // find the solution (next_a) for // next power of prime int next_a = (a_t - Image(a_t, k) * inv(derivative(a1), prime)) % power_p; // If next_a < 0 return equivalent // positive remainder modulo p if (next_a < 0) return next_a += power_p; // Return the next power of a return next_a;}// Function to find the solution of// the required exponent of primeint powerOfPrime(int prime, int power, int k, int a1){ // The lemma does not work for // derivative of f(x) at a1 if (derivative(a1) != 0) { int a_t = a1; // Looping from 1 to power // of prime whose solution // is to be found for (int p = 1; p < power; p++) { a_t = next_power(a_t, p, a1, prime, k); } // Final answer after evaluating // all the exponents up till // the required exponent return a_t; } return -1;}// Driver Codeint main(){ int prime = 7, a1 = 3; int power = 2, k = 3; // Function Call cout << powerOfPrime(prime, power, k, a1); return 0;} |
Java
// Java program to illustrate the// Hensel's Lemmaimport java.util.*;class GFG{// Consider f(x) = x ^ 3 - k,// where k is a constant// Function to find the modular// inverse of a modulo mstatic int inv(int a, int m){ int m0 = m, t, q; int x0 = 0, x1 = 1; if (m == 1) return 0; // Apply the Euclidean algorithm, // to find the modular inverse while (a > 1) { q = a / m; t = m; m = a % m; a = t; t = x0; x0 = x1 - q * x0; x1 = t; } if (x1 < 0) x1 += m0; return x1;}// Function to find the derivative of// f(x) and f'(x) = 3 * (x ^ 2)static int derivative(int x){ return 3 * x * x;}// Function to find the image of// x in f(x) = x ^ 3 - k.static int Image(int x, int k){ return x * x * x - k;}// Function to find the next power// of the numberstatic int next_power(int a_t, int t, int a1, int prime, int k){ // Next power of prime for which // solution is to be found int power_p = (int)Math.pow(prime, t + 1); // Using Hensel's recursion to // find the solution (next_a) for // next power of prime int next_a = (a_t - Image(a_t, k) * inv(derivative(a1), prime)) % power_p; // If next_a < 0 return equivalent // positive remainder modulo p if (next_a < 0) return next_a += power_p; // Return the next power of a return next_a;}// Function to find the solution of// the required exponent of primestatic int powerOfPrime(int prime, int power, int k, int a1){ // The lemma does not work for // derivative of f(x) at a1 if (derivative(a1) != 0) { int a_t = a1; // Looping from 1 to power // of prime whose solution // is to be found for(int p = 1; p < power; p++) { a_t = next_power(a_t, p, a1, prime, k); } // Final answer after evaluating // all the exponents up till // the required exponent return a_t; } return -1;}// Driver Codepublic static void main(String []args){ int prime = 7, a1 = 3; int power = 2, k = 3; // Function Call System.out.print(powerOfPrime(prime, power, k, a1));}}// This code is contributed by rutvik_56 |
Python3
# Python3 program to illustrate the# Hensel's Lemma# Consider f(x) = x ^ 3 - k,# where k is a constant# Function to find the modular# inverse of a modulo mdef inv(a, m): m0 = m x0 = 0 x1 = 1 if (m == 1): return 0 # Apply the Euclidean algorithm, # to find the modular inverse while (a > 1): q = a // m t = m m = a % m a = t t = x0 x0 = x1 - q * x0 x1 = t if (x1 < 0): x1 += m0 return x1# Function to find the derivative of# f(x) and f'(x) = 3 * (x ^ 2)def derivative(x): return 3 * x * x# Function to find the image of# x in f(x) = x ^ 3 - k.def Image(x, k): return x * x * x - k# Function to find the next power# of the numberdef next_power(a_t, t, a1, prime, k): # Next power of prime for which # solution is to be found power_p = int(pow(prime, t + 1)) # Using Hensel's recursion to # find the solution(next_a) for # next power of prime next_a = (a_t - Image(a_t, k) * inv(derivative(a1), prime)) % power_p # If next_a < 0 return equivalent # positive remainder modulo p if (next_a < 0): next_a += power_p return next_a # Return the next power of a return next_a# Function to find the solution of# the required exponent of primedef powerOfPrime(prime, power, k, a1): # The lemma does not work for # derivative of f(x) at a1 if (derivative(a1) != 0): a_t = a1 # Looping from 1 to power # of prime whose solution # is to be found for p in range(1, power): a_t = next_power(a_t, p, a1, prime, k) # Final answer after evaluating # all the exponents up till # the required exponent return a_t return -1# Driver Codeprime = 7a1 = 3power = 2k = 3# Function Callprint(powerOfPrime(prime, power, k, a1))# This code is contributed by amreshkumar3 |
C#
// C# program to illustrate the// Hensel's Lemmausing System;class GFG{// Consider f(x) = x ^ 3 - k,// where k is a constant// Function to find the modular// inverse of a modulo mstatic int inv(int a, int m){ int m0 = m, t, q; int x0 = 0, x1 = 1; if (m == 1) return 0; // Apply the Euclidean algorithm, // to find the modular inverse while (a > 1) { q = a / m; t = m; m = a % m; a = t; t = x0; x0 = x1 - q * x0; x1 = t; } if (x1 < 0) x1 += m0; return x1;}// Function to find the derivative of// f(x) and f'(x) = 3 * (x ^ 2)static int derivative(int x){ return 3 * x * x;}// Function to find the image of// x in f(x) = x ^ 3 - k.static int Image(int x, int k){ return x * x * x - k;}// Function to find the next power// of the numberstatic int next_power(int a_t, int t, int a1, int prime, int k){ // Next power of prime for which // solution is to be found int power_p = (int)Math.Pow(prime, t + 1); // Using Hensel's recursion to // find the solution (next_a) for // next power of prime int next_a = (a_t - Image(a_t, k) * inv(derivative(a1), prime)) % power_p; // If next_a < 0 return equivalent // positive remainder modulo p if (next_a < 0) return next_a += power_p; // Return the next power of a return next_a;}// Function to find the solution of// the required exponent of primestatic int powerOfPrime(int prime, int power, int k, int a1){ // The lemma does not work for // derivative of f(x) at a1 if (derivative(a1) != 0) { int a_t = a1; // Looping from 1 to power // of prime whose solution // is to be found for(int p = 1; p < power; p++) { a_t = next_power(a_t, p, a1, prime, k); } // Final answer after evaluating // all the exponents up till // the required exponent return a_t; } return -1;}// Driver Codepublic static void Main(string []args){ int prime = 7, a1 = 3; int power = 2, k = 3; // Function Call Console.Write(powerOfPrime(prime, power, k, a1));}}// This code is contributed by pratham76. |
Javascript
<script>// Javascript program to illustrate the// Hensel's Lemma// Consider f(x) = x ^ 3 - k,// where k is a constant // Function to find the modular// inverse of a modulo mfunction inv(a, m){ let m0 = m, t, q; let x0 = 0, x1 = 1; if (m == 1) return 0; // Apply the Euclidean algorithm, // to find the modular inverse while (a > 1) { q = Math.floor(a / m); t = m; m = a % m; a = t; t = x0; x0 = x1 - q * x0; x1 = t; } if (x1 < 0) x1 += m0; return x1;} // Function to find the derivative of// f(x) and f'(x) = 3 * (x ^ 2)function derivative(x){ return 3 * x * x;} // Function to find the image of// x in f(x) = x ^ 3 - k.function Image(x, k){ return x * x * x - k;} // Function to find the next power// of the numberfunction next_power(a_t, t, a1, prime, k){ // Next power of prime for which // solution is to be found let power_p = Math.floor(Math.pow(prime, t + 1)); // Using Hensel's recursion to // find the solution (next_a) for // next power of prime let next_a = (a_t - Image(a_t, k) * inv(derivative(a1), prime)) % power_p; // If next_a < 0 return equivalent // positive remainder modulo p if (next_a < 0) return next_a += power_p; // Return the next power of a return next_a;} // Function to find the solution of// the required exponent of primefunction powerOfPrime(prime, power, k, a1){ // The lemma does not work for // derivative of f(x) at a1 if (derivative(a1) != 0) { let a_t = a1; // Looping from 1 to power // of prime whose solution // is to be found for(let p = 1; p < power; p++) { a_t = next_power(a_t, p, a1, prime, k); } // Final answer after evaluating // all the exponents up till // the required exponent return a_t; } return -1;} // Driver Code let prime = 7, a1 = 3; let power = 2, k = 3; // Function Call document.write(powerOfPrime(prime, power, k, a1)); // This code is contributed by target_2. </script> |
Output:
6
Time Complexity: O(log N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
