Hensel 's Lemma | Java program to illustrate the Hensel 's Lemma ; Function to find the modular inverse of a modulo m ; Apply the Euclidean algorithm , to find the modular inverse ; Function to find the derivative of f ( x ) and f '(x) = 3 * (x ^ 2) ; Function to find the image of x in f ( x ) = x ^ 3 - k . ; Function to find the next power of the number ; Next power of prime for which solution is to be found ; Using Hensel 's recursion to  find the solution (next_a) for  next power of prime ; If next_a < 0 return equivalent positive remainder modulo p ; Return the next power of a ; Function to find the solution of the required exponent of prime ; The lemma does not work for derivative of f ( x ) at a1 ; Looping from 1 to power of prime whose solution is to be found ; Final answer after evaluating all the exponents up till the required exponent ; Driver Code ; Function Call
import java . util . * ; class GFG { static int inv ( int a , int m ) { int m0 = m , t , q ; int x0 = 0 , x1 = 1 ; if ( m == 1 ) return 0 ; 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 ; } static int derivative ( int x ) { return 3 * x * x ; } static int Image ( int x , int k ) { return x * x * x - k ; } static int next_power ( int a_t , int t , int a1 , int prime , int k ) { int power_p = ( int ) Math . pow ( prime , t + 1 ) ; int next_a = ( a_t - Image ( a_t , k ) * inv ( derivative ( a1 ) , prime ) ) % power_p ; if ( next_a < 0 ) return next_a += power_p ; return next_a ; } static int powerOfPrime ( int prime , int power , int k , int a1 ) { if ( derivative ( a1 ) != 0 ) { int a_t = a1 ; for ( int p = 1 ; p < power ; p ++ ) { a_t = next_power ( a_t , p , a1 , prime , k ) ; } return a_t ; } return - 1 ; } public static void main ( String [ ] args ) { int prime = 7 , a1 = 3 ; int power = 2 , k = 3 ; System . out . print ( powerOfPrime ( prime , power , k , a1 ) ) ; } }