# Recursive Elucidation of Polynomial Congruences Using Root-Finding Numerical Techniques

Authors: M. Khalid Mahmood; Farooq Ahmad
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

In this paper we put forward a family of algorithms for lifting solutions of a polynomial congruencemodp to polynomial congruence modpk. For this purpose, root-finding iterative methods are employed for solving polynomial congruences of the form axn≡b(modpk), k≥1, where a,b, and n>0 are integers which are not divisible by an odd prime p. It is shown that the algorithms suggested in this paper drastically reduce the complexity for such computations to a logarithmic scale. The efficacy of the proposed technique for solving negative exponent equations of the form ax-n≡b(modpk) has also been addressed.


---

## Body

## 1. Introduction and Preliminaries

The scope of congruence in number theory is of vital importance. The use of iterative methods for solving nonlinear equations has become a valuable device for numerical analysts. This research work addresses some iterative methods for solving polynomial congruences of the formaxn≡b(mod⁡pk),k≥1 where a,b, and n>0 are integers which are not divisible by an odd prime p. The root-finding recursive techniques have been discussed in [1–4] to get the inverse of numbers modulo prime powers, which is the motivation of the proposed research work. In this piece of work, we use higher order iterative methods with a particular focus on Householder's and Basic Family of Iteration Functions (for detail, see [5–7]) in order to find solutions of polynomial congruences of the form axn≡b(mod⁡pk),k≥1.Hensel's lemma is one of the most popular methods amongst the existing techniques for solving polynomial congruence modulopk. By applying Hensel's lemma on some polynomial congruence modulo pk, it can be seen that the experience of the exposition of this lemma is strenuous and much more laborious. So the proposed technique endeavors to keep the elucidation consistently a little low to give advantage in finding the solution of such congruences by means of explicit iteration techniques which are quite fast in finding these solutions. The following are the two versions of well-known Hensel's lemma.Theorem 1 (see [8]).
Suppose thatg(x) is a polynomial with integral coefficients. If g(x)≡0(mod⁡pj) and g′(a)≢0(mod⁡p), then there is a unique y(mod⁡p) such that g(a+ypj)≡0(mod⁡pj+1).The following theorem can easily be deduced from Hensel's lemma after applying Taylor's Theorem. This is actually the typical procedure to find solutions of congruences modulopk by means of Hensel's lemma. For details see [9, page 106].Theorem 2 (see [9]).
Letp be a prime and k an arbitrary positive integer, and suppose that s is a solution of f(x)≡0(mod⁡pk).(1)
Ifp∤f′(s), then there is precisely one solution sk+1 of f(x)≡0(mod⁡pk+1) such that xk+1≡s(mod⁡pk) is given by sk+1=s+tpk, where t is the unique solution of f′(s)t≡(-f(s)/pk)(mod⁡p).(2)
Ifp∣f′(s) and pk+1∣f(s), then there are p solutions of f(x)≡0(mod⁡pk+1) that are congruent to s(mod⁡pk), given by s+pkj, for j=0,1,2,…,p-1.(3)
Ifp∣f′(s) and pk+1∤f(s), then there are no solutions of f(x)≡0(mod⁡pk+1) that are congruent to s(mod⁡pk).Let us solve the congruence2x3≡5(mod⁡74) using Theorem 2. Let f(x)=2x3-5. First, we solve f(x)≡0(mod⁡7). By trial, it is easy to find that x≡3(mod⁡7) and x≡4(mod⁡7) are the solutions of the congruence f(x)≡0(mod⁡7). To perform iterations by Theorem 2, we proceed as under.Takes=s1=3; then 7∤f′(3). By Theorem 2, there is a unique solution s2 of f(x)≡0(mod⁡72). To find s2, we find integer t from the congruence f′(3)t≡(-f(3)/7)(mod⁡7). This gives 54t≡(-49/7)(mod⁡7) or t≡0(mod⁡7). Hence the unique solution sk+1=s+tpk gives s2=3. Therefore s2=3 is the unique solution of f(x)≡0(mod⁡72).Next we takes2=3; then f′(3)t≡(-f(3)/72)(mod⁡7) becomes 54t≡(-49/49)(mod⁡7). That is, 5t≡6(mod⁡7) or t≡4(mod⁡7). Hence the unique solution s3=s2+tpk gives s3=3+4*72=199. Therefore, s2=199 is the unique solution of f(x)≡0(mod⁡73).Finally we takes3=199; then f′(199)=277606 is not divisible by 7. Thus there is a unique solution s4 of f(x)≡0(mod⁡74). To find s4, we solve f′(199)t≡(-f(199)/73)(mod⁡7). This gives 5t≡4(mod⁡7) or t≡5(mod⁡7). Then, s4=199+5*73=1914. Hence, s4=1914 is the solution of 2x3≡5(mod⁡74).From above example, it is noticed that several iterations are required in order to compute a solution to a congruence of higher powers of prime which is computationally intensive. Moreover at each step we need to calculate derivative of the function at current root. Hence we may hesitate in solving polynomial congruences with modulus of higher powers of primes using this lemma. Thus we need to find some explicit algorithms in which the needed derivatives are already incorporated with somelog⁡k steps. In the underlying paper we solve the polynomial congruence with higher modulo by means of algorithms developed using root-finding iterative methods. The p-adic proof of these algorithms has been derived using elementary number theory. Notations used in this paper are standard and we follow [1–3, 10, 11].


## 2. A Solution of Congruences Using Newton’s Method

Newton's method is a well-known iterative procedure for finding the roots of an equation. It is the best tool in many ways for the solution of a nonlinear problem. Its simplicity and great speed always attract in attempting a nonlinear problem. Assume that an initial estimatex0 is known for the desired root α of f(x)=0. Then to perform iterations the formula for Newton's method is
(1)xk+1=xk-f(xk)f′(xk),k=0,1,2…
Let us take f(x)=b/xn-a. Then using (1), the explicit form for Newton's method is
(2)nbxk+1=(n+1)bxk-axkn+1.
Like real numbers, it can be proved that Newton's method is quadratically convergent. Now if xk is the solution of axn≡b(mod⁡pk) then for some integer t, we have, axkn=b+tpk. Then by using (2), we obtain
(3)axk+1n=(b+tpk)(nb)n{(n+1)b-b-tpk}n=(b+tpk)(nb)n(nb-tpk)n=(b+tpk)(nb)n×{(nb)n-n(nb)n-1tpk+termsinvolvingp2k}≡(b+tpk)(nb)n{(nb)n-n(nb)n-1tpk}(mod⁡p2k)≡(nb)nb(nb)n(mod⁡p2k).
Now, if a,b,n≢0(mod⁡p) then (p,bn)=1 and hence (p2k,(bn)n)=1. Then by Cancellation law, (3) yields that xk+1 is the solution of the congruence axn≡b(mod⁡p2k).Let us solve the congruence2x3≡3(mod⁡532). In order to solve a polynomial congruence of the form axn≡b(mod⁡p2k),k≥1, we first see that it is sufficient to solve axn≡b(mod⁡p) since every solution of axn≡b(mod⁡p2k) is a solution of axn≡b(mod⁡p). Once we do this, then we can apply (2) for finding the solutions of axn≡b(mod⁡p2k) from the solutions of the congruence axn≡b(mod⁡pk). Therefore, we first solve the congruence 2x3≡3(mod⁡5). By inspection we see that x≡4(mod⁡5) is the solution of the congruence 2x3≡3(mod⁡5). Thus we choose x1=4 as our initial guess. Then by (2), we have
(4)9x2=4.3.4-2(4)4=-464≡-414(mod⁡52).
Hence,
(5)x2≡-46(mod⁡25)≡4(mod⁡25).
We repeat above process and find that x3≡504,x4≡368004,x5≡88003883629 and x6≡1996563532039908180504 are the solutions of the given congruence modulo 54,58,516, and 532, respectively.


### 2.1. Order of Convergence

As far as the convergence of an iterative method of orderm is concerned, it avows that the accurateness or precision to compute the current approximation xj is only mj digits. This means that if we start with an r-digit integer xk as the initial estimate in some modulo pα, then xk+1 would be a new approximation in modulo pmα containing rm-digits.To ensure that the Newton's method is quadratically convergent, we show thatxk+1 will not be a solution if we expand the binomial (nb-tpk)n up to terms involving p2. For this, we rewrite the step
(6)axk+1n=(b+tpk)(nb)n(nb-tpk)n=(b+tpk)(nb)n{(nb)n-n(nb)n-1tpk+n(n-1)2×(nb)n-2t2p2+termsinvolvingp3kn(n-1)2}≡(b+tpk)(nb)n{n(n-1)2(nb)n-n(nb)n-1tpkhhhhhhhhh+n(n-1)2(nb)n-2t2p2(mod⁡p3k)}≡b(nb)n-((n+1)/2)(nb)n-1t2p2(nb)n(mod⁡p3k)≢b(mod⁡p3k)as-n+12(nb)n-1t2p2≢0(mod⁡p3k).


## 2.1. Order of Convergence

As far as the convergence of an iterative method of orderm is concerned, it avows that the accurateness or precision to compute the current approximation xj is only mj digits. This means that if we start with an r-digit integer xk as the initial estimate in some modulo pα, then xk+1 would be a new approximation in modulo pmα containing rm-digits.To ensure that the Newton's method is quadratically convergent, we show thatxk+1 will not be a solution if we expand the binomial (nb-tpk)n up to terms involving p2. For this, we rewrite the step
(6)axk+1n=(b+tpk)(nb)n(nb-tpk)n=(b+tpk)(nb)n{(nb)n-n(nb)n-1tpk+n(n-1)2×(nb)n-2t2p2+termsinvolvingp3kn(n-1)2}≡(b+tpk)(nb)n{n(n-1)2(nb)n-n(nb)n-1tpkhhhhhhhhh+n(n-1)2(nb)n-2t2p2(mod⁡p3k)}≡b(nb)n-((n+1)/2)(nb)n-1t2p2(nb)n(mod⁡p3k)≢b(mod⁡p3k)as-n+12(nb)n-1t2p2≢0(mod⁡p3k).


## 3. Third Order Iterative Methods

The following are the third order iterative methods for which the explicit formulas for finding the roots of congruences are presented. The p-adic proofs of their convergence is given in the following two theorems.


### 3.1. A Variant of Newton’s Method

Several variants of Newton's method have been given by many researchers to improve the order of convergence. For third-order convergence, the following three variants of Newton's methods have been studied earlier in [11, 12] to solve nonlinear equations, given as
(7)xk+1=xk-f(xk)f′(xk+1*),k≥0,(8)wherexk+1*=xk-f(xk)2f′(xk)(9)xk+1=xk-f(xk+1*)f′(xk),k≥0,wherexk+1*=xk-f(xk)f′(xk),(10)xk+1=xk-2f(xk)f′(xk+1*)+f′(xk),k≥0wherexk+1*=xk-f(xk)f′(xk).
In the following theorem, we use (7) to find the solutions of congruences of the form axn≡b(mod⁡p3k), k≥1, from the solutions of the congruence axn≡b(mod⁡pk).Theorem 3.
Leta,b, and n>0 be integers which are not divisible by an odd prime p. If xk, k≥1 satisfies axn≡b(mod⁡pk) then xk+1 satisfies the congruence axn≡b(mod⁡p3k), where
(11)xk+1=xk[1+(b-axkn){(2n+1)b-axkn}n+12n+1(nb)n+1]Proof.
To prove this, letf(x)=b/xn-a. By (8), we get, xk+1*=xk(((2n+1)b-axkn)/nb). Then by (7), we obtain
(12)xk+1=xk[1+(b-axkn){(2n+1)b-axkn}n+12n+1(nb)n+1].
If xk is the solution of axn≡b(mod⁡pk) then for some integer t, we have axkn=b+tpk. Putting in (12), we get
(13)nb(2nb)nxk+1=xk[nb(2nb)n-tpkvvvvvv×{(2nb)n-n(2nb)n-1tpkvvvvvvv.-n(n-1)2(2nb)n-2t2p2kvvvvvvv..+termsinvolvingp3k}]≡xk{nb(2nb)n-tpk(2nb)nvvvvvv+n(2nb)n-1t2p2k}(mod⁡p3k).
Since p>2 and (2nb,p)=1, so ((2nb)n-1,p3k))=1. Then by (13)
(14)2(nb)2xk+1=xk{2(nb)2-2nbtpk+nt2p2k}(mod⁡p3k).
This implies that
(15)axk+1n≡(b+tpk)×(2(nb)2-2nbtpk+nt2p2k)n(2(nb)2)n(mod⁡p3k)≡b(2(nb)2)n(2(nb)2)n(mod⁡p3k)≡b(mod⁡p3k)as(2nb,p)=1.


### 3.2. Abbasbandy's Method

In [10], Abbasbandy used Adomian decomposition method to improve Newton's method for solving nonlinear equations. The improved method is called Abbasbandy’s method (AM). Solving polynomial congruences is one of the most interesting problems in number theory. In this section, we use AM to solve polynomial congruences of the form axn≡b(mod⁡pk), k≥1. It can be seen that AM lifts a solution modulo p to p3 then to p9 and by iteration to p3k. To perform iterations, the formula for AM is expressed as
(16)xk+1=xk-f(xk)f′(xk)-f2(xk)f′′(xk)2f′3(xk)-f3(xk)f′′′(xk)6f′4(xk).Theorem 4.
Leta,b, and n>0 be integers which are not divisible by a prime p>3. If xk, k≥1 satisfies axn≡b(mod⁡pk) then xk+1 satisfies the congruence axn≡b(mod⁡p3k), where
(17)6n3b3xk+1=xk(2b3(1+3n+5n2+3n3)-3ab2(2+5n+5n2)xkn+6a2b(1+n)2xk2n-a3(2+3n+n2)xk3n).Proof.
To prove this, letf(x)=b/xn-a. By (16), we obtain
(18)xk+1=xk-b/xkn-a-nb/xkn+1-(b/xkn-a)2(n(n+1)b/xkn+2)2(-nb/xkn+1)3+(b/xkn-a)3((n(n+1)(n+2)b)/xkn+3)6(-nb/xkn+1)4=xk[1+b-axknnb+(b-axkn)2(n+1)2n2b2+(b-axkn)3(n+1)(n+2)6n3b3].
This can be simplified as(19)6n3b3xk+1=xk[6b3n3+(b-axkn)6n2b2vvvvvvv.+(b-axkn)2(n+1)3nbvvvvvvv.+(b-axkn)3(n+1)(n+2)]=xk(2b3(1+3n+5n2+3n3)vvvvvvv.-3ab2(2+5n+5n2)xknvvvvvvv.+6a2b(1+n)2xk2n-a3(2+3n+n2)xk3n).
Next we show that xk+1 is a solution of the congruence axn≡b(mod⁡p3k). Now if xk is the solution of axn≡b(mod⁡pk) then for some integer t, we have, axkn=b+tpk. Putting in (19), we get
(20)6n3b3xk+1=xk[2b3(1+3n+5n2+3n3)vvvvvv.-3b2(2+5n+5n2)(b+tpk)vvvvvv.+6b(1+n)2(b2+2btpk+ttp2k)vvvvvv.-(2+3n+n2)(b3+3b2tpkvvvvvvvvvvvvvvvvvv..+3bt2p2k+t3p3k)]≡xk[6n3b3-6n2b2tpkvvvv..+3n(n+1)bt2p2k](mod⁡p3k).
This implies that
(21)(6n3b3)naxk+1n≡[6n3b3-6n2b2tpk+3n(n+1)bt2p2k]n(mod⁡p3k).
Using Binomial Series expansion, we obtain
(22)(6n3b3)naxk+1n≡[(6n3b3)n+n(6n3b3)n-1vvvvv.×(-6n2b2tpk+3n(n+1)bt2p3k)vvvvv.+n(n-1)2(6n3b3)n-2vvvvv.×(-6n2b2tpk+3n(n+1)bt2p2k)2vvvvv.+termsinvolvingp3k](b+tpk)(mod⁡p3k)≡[(6n3b3)n-6n3b2(6n3b3)n-1tpk+6n3b(6n3b3)n-1t2p2k](b+tpk)(mod⁡p3k)≡b(6n3b3)n(mod⁡p3k).
Since p>3 and (nb,p)=1, so (6n3b3,p)=1 and hence ((6n3b3)n,p3k)=1. Finally, by Cancelation law (22) yields that xk+1 is the solution of the congruence ax2≡b(mod⁡p3k).


### 3.3.  Remark

Note that variants of Newton's method discussed in Section3 are the two-step (predictor-corrector) methods while the followings are one-step methods. This clearly shows that the technique suggested is equally good even to two step methods and could be enhanced to multistep methods.


## 3.1. A Variant of Newton’s Method

Several variants of Newton's method have been given by many researchers to improve the order of convergence. For third-order convergence, the following three variants of Newton's methods have been studied earlier in [11, 12] to solve nonlinear equations, given as
(7)xk+1=xk-f(xk)f′(xk+1*),k≥0,(8)wherexk+1*=xk-f(xk)2f′(xk)(9)xk+1=xk-f(xk+1*)f′(xk),k≥0,wherexk+1*=xk-f(xk)f′(xk),(10)xk+1=xk-2f(xk)f′(xk+1*)+f′(xk),k≥0wherexk+1*=xk-f(xk)f′(xk).
In the following theorem, we use (7) to find the solutions of congruences of the form axn≡b(mod⁡p3k), k≥1, from the solutions of the congruence axn≡b(mod⁡pk).Theorem 3.
Leta,b, and n>0 be integers which are not divisible by an odd prime p. If xk, k≥1 satisfies axn≡b(mod⁡pk) then xk+1 satisfies the congruence axn≡b(mod⁡p3k), where
(11)xk+1=xk[1+(b-axkn){(2n+1)b-axkn}n+12n+1(nb)n+1]Proof.
To prove this, letf(x)=b/xn-a. By (8), we get, xk+1*=xk(((2n+1)b-axkn)/nb). Then by (7), we obtain
(12)xk+1=xk[1+(b-axkn){(2n+1)b-axkn}n+12n+1(nb)n+1].
If xk is the solution of axn≡b(mod⁡pk) then for some integer t, we have axkn=b+tpk. Putting in (12), we get
(13)nb(2nb)nxk+1=xk[nb(2nb)n-tpkvvvvvv×{(2nb)n-n(2nb)n-1tpkvvvvvvv.-n(n-1)2(2nb)n-2t2p2kvvvvvvv..+termsinvolvingp3k}]≡xk{nb(2nb)n-tpk(2nb)nvvvvvv+n(2nb)n-1t2p2k}(mod⁡p3k).
Since p>2 and (2nb,p)=1, so ((2nb)n-1,p3k))=1. Then by (13)
(14)2(nb)2xk+1=xk{2(nb)2-2nbtpk+nt2p2k}(mod⁡p3k).
This implies that
(15)axk+1n≡(b+tpk)×(2(nb)2-2nbtpk+nt2p2k)n(2(nb)2)n(mod⁡p3k)≡b(2(nb)2)n(2(nb)2)n(mod⁡p3k)≡b(mod⁡p3k)as(2nb,p)=1.


## 3.2. Abbasbandy's Method

In [10], Abbasbandy used Adomian decomposition method to improve Newton's method for solving nonlinear equations. The improved method is called Abbasbandy’s method (AM). Solving polynomial congruences is one of the most interesting problems in number theory. In this section, we use AM to solve polynomial congruences of the form axn≡b(mod⁡pk), k≥1. It can be seen that AM lifts a solution modulo p to p3 then to p9 and by iteration to p3k. To perform iterations, the formula for AM is expressed as
(16)xk+1=xk-f(xk)f′(xk)-f2(xk)f′′(xk)2f′3(xk)-f3(xk)f′′′(xk)6f′4(xk).Theorem 4.
Leta,b, and n>0 be integers which are not divisible by a prime p>3. If xk, k≥1 satisfies axn≡b(mod⁡pk) then xk+1 satisfies the congruence axn≡b(mod⁡p3k), where
(17)6n3b3xk+1=xk(2b3(1+3n+5n2+3n3)-3ab2(2+5n+5n2)xkn+6a2b(1+n)2xk2n-a3(2+3n+n2)xk3n).Proof.
To prove this, letf(x)=b/xn-a. By (16), we obtain
(18)xk+1=xk-b/xkn-a-nb/xkn+1-(b/xkn-a)2(n(n+1)b/xkn+2)2(-nb/xkn+1)3+(b/xkn-a)3((n(n+1)(n+2)b)/xkn+3)6(-nb/xkn+1)4=xk[1+b-axknnb+(b-axkn)2(n+1)2n2b2+(b-axkn)3(n+1)(n+2)6n3b3].
This can be simplified as(19)6n3b3xk+1=xk[6b3n3+(b-axkn)6n2b2vvvvvvv.+(b-axkn)2(n+1)3nbvvvvvvv.+(b-axkn)3(n+1)(n+2)]=xk(2b3(1+3n+5n2+3n3)vvvvvvv.-3ab2(2+5n+5n2)xknvvvvvvv.+6a2b(1+n)2xk2n-a3(2+3n+n2)xk3n).
Next we show that xk+1 is a solution of the congruence axn≡b(mod⁡p3k). Now if xk is the solution of axn≡b(mod⁡pk) then for some integer t, we have, axkn=b+tpk. Putting in (19), we get
(20)6n3b3xk+1=xk[2b3(1+3n+5n2+3n3)vvvvvv.-3b2(2+5n+5n2)(b+tpk)vvvvvv.+6b(1+n)2(b2+2btpk+ttp2k)vvvvvv.-(2+3n+n2)(b3+3b2tpkvvvvvvvvvvvvvvvvvv..+3bt2p2k+t3p3k)]≡xk[6n3b3-6n2b2tpkvvvv..+3n(n+1)bt2p2k](mod⁡p3k).
This implies that
(21)(6n3b3)naxk+1n≡[6n3b3-6n2b2tpk+3n(n+1)bt2p2k]n(mod⁡p3k).
Using Binomial Series expansion, we obtain
(22)(6n3b3)naxk+1n≡[(6n3b3)n+n(6n3b3)n-1vvvvv.×(-6n2b2tpk+3n(n+1)bt2p3k)vvvvv.+n(n-1)2(6n3b3)n-2vvvvv.×(-6n2b2tpk+3n(n+1)bt2p2k)2vvvvv.+termsinvolvingp3k](b+tpk)(mod⁡p3k)≡[(6n3b3)n-6n3b2(6n3b3)n-1tpk+6n3b(6n3b3)n-1t2p2k](b+tpk)(mod⁡p3k)≡b(6n3b3)n(mod⁡p3k).
Since p>3 and (nb,p)=1, so (6n3b3,p)=1 and hence ((6n3b3)n,p3k)=1. Finally, by Cancelation law (22) yields that xk+1 is the solution of the congruence ax2≡b(mod⁡p3k).


## 3.3.  Remark

Note that variants of Newton's method discussed in Section3 are the two-step (predictor-corrector) methods while the followings are one-step methods. This clearly shows that the technique suggested is equally good even to two step methods and could be enhanced to multistep methods.


## 4. Higher Order Iterative Families

The following are the two well-known one step root-finding higher order iterative families. In this section, we make use of these families in order to find the solutions of congruences modulopk. The following theorems demonstrate how one can employ the order of convergence of these families to get the solutions of ecstatic problems in number theory.


### 4.1. Householder's Family

Householder's methods are a class of well-known iterative algorithms for solving a nonlinear equation in one variable. Letf be a function of one variable with continuous derivatives of order p+1. The formula for Householder's method of order p+1 to perform iterations is
(23)xk+1=xk+p(1/f)p-1(xk)(1/f)p(xk).
Let us establish a formula for p=3 using  (23)(
p
-
1
)th derivative of 1/f(x)(24)=2f′(x)2f(x)3-f′′(x)f(x)2.
Similarly, pth derivative of 1/f(x)(25)=-6f′(x)3f(x)4+6f′(x)f′′(x)f(x)3-f′′′(x)f(x)2.
Substituting the values of (24) and (25) into (23), we obtain
(26)xk+1=(-6f(xk)f′(xk)f′′(xk))-13f(xk)[f(xk)f′′(xk)-2f′(xk)2]×(f(xk)2f′′′(xk)+6f′(xk)3-6f(xk)f′(xk)f′′(xk))-1)+xk.
In the following theorem, we use Householder's method of order 4 in order to find the solutions of congruences of the form axn≡b(mod⁡p4k), k≥1, from the solutions of the congruence axn≡b(mod⁡pk).Theorem 5.
Leta,b, and n>0 be integers which are not divisible by a prime p>3. If xk, k≥1 is a solution of the congruence axn≡b(mod⁡pk) then xk+1 is the solution of the congruence axn≡b(mod⁡p4k) satisfying the equation
(27)xk+1=(+a2(n+1)(n+2)xk2n)-1(b2(n2-1)+2ab(2n2+1)xkn+a2(n2-1)xk2n)×(b2(n-1)(n-2)+4ab(n2-1)xkn+a2(n+1)(n+2)xk2n)-1)xk.Proof.
To prove this, letf(x)=b/xn-a and solve f(x)=0 using (26); we get
(28)xk+1=(+6n2(n+1)b2xk2n+3(bxkn-a))-13(bxkn-a)[(bxkn-a)(n(n+1)bxkn+2)-2n2b2xk2n+2]×((bxkn-a)2(-n(n+1)(n+2)bxkn+3)-6n3b3xk3n+3vvvv.+6n2(n+1)b2xk2n+3(bxkn-a))-1)+xk=(×(n+1)(n+2)bxkn-6n3b3)-13xk(b-axkn)[n(n+1)(b-axkn)-2n2b2]×(6n2(n+1)b2(b-axkn)-(b-axkn)n×(n+1)(n+2)bxkn-6n3b3)-1)+xk=(+a2(n+1)(n+2)xk2n)-1(b2(n2-1)+2ab(2n2+1)xkn+a2(n2-1)xk2n)×(b2(n-1)(n-2)+4ab(n2-1)xkn+a2(n+1)(n+2)xk2n)-1)xk.
Next we show that xk+1 is a root of the congruence axn≡b(mod⁡p4k). Now if xk is the solution of axn≡b(mod⁡pk) then for some integer t, we have, axkn=b+tpk. Putting in (27), we obtain
(29)xk+1=(+(n+1)(n+2)(b+tpk)2)-1(b2(n2-1)+2b(2n2+1)(b+tpk)+(n2-1)(b+tpk)2)×(b2(n-1)(n-2)+4b(n2-1)(b+tpk)+(n+1)(n+2)(b+tpk)2)-1)xk=(+(n+1)(n+2)t2p2k)-1(6n2b2+6n2btpk+(n2-1)t2p2k)×(6n2b2+6n(n+1)btpk+(n+1)(n+2)t2p2k)-1)xk.
This implies that
(30)axk+1n≡(+(n+1)(n+2)t2p2k}n)-1(b{6n2b2+6n2btpk+(n2-1)t2p2k}n)×(+(n+1)(n+2)t2p2k}nb{6n2b2+6n(n+1)btpk+(n+1)(n+2)t2p2k}n)-1)(b+tpk).
Using Binomial Series expansion, we obtain
(31)[6n2b2+6n2btpk+(n2-1)t2p2k]n(b+tpk)=6n(nb)2nb+6nn(nb)2ntpk+6n-1(n-1)(3n2+n+1)(nb)2n-1t2p2k+6n-1n(n-1)(n3-n2-1)(nb)2n-2t3p3k+6n(nb)2ntpk+6n26n-1(nb)2n-1t2p2k+6n-1n(n-1)(3n2+n+1)(nb)2n-2t3p3k+termsinvolvingp4k≡6n(nb)2nb+6n(n+1)(nb)2ntpk+6n-1(3n3+4n2-1)(nb)2n-1t2p2k+6n-1n2(n-1)(n+1)2(nb)2n-2t3p3k(mod⁡p4k).
Similarly, we expand denominator to get
(32)b[6n2b2+6n(n+1)btpk+(n+1)(n+2)t2p2k]n=6n(nb)2nb+6n(n+1)(nb)2ntpk+6n-1(n+1)(n+2)(nb)2n-1t2p2k+6n-1(n+1)2(n-1)(n+2)(nb)2n-2t3p3k+3.6n-1(n-1)(n+1)2(nb)2n-1t2p2k+6n-1(n-1)(n+1)3(n-2)(nb)2n-2t3p3k+termsinvolvingp4k≡6n(nb)2nb+6n(n+1)(nb)2ntpk+6n-1(3n3+4n2-1)(nb)2n-1t2p2k+6n-1n2(n-1)(n+1)2(nb)2n-2t3p3k(mod⁡p4k).
Substituting (31) and (32) into (30), we get
(33)axk+1n≡bdd(mod⁡p4k)where,d=6n(nb)2nb+6n(n+1)(nb)2ntpk+6n-1(3n3+4n2-1)(nb)2n-1t2p2k+6n-1n2(n-1)(n+1)2(nb)2n-2t3p3k.
Next we claim that d≢0(mod⁡p). To prove our assertion we let d=6n(nb)2nb+6n(n+1)(nb)2ntpk+6n-1(3n3+4n2-1)(nb)2n-1t2p2k+6n-1n2(n-1)(n+1)2(nb)2n-2t3p3k≡0(mod⁡p). But then 6n(nb)2nb≡0(mod⁡p). This shows that (nb)2n≡0(mod⁡p) as p>3 and (b,p)=1. Which further implies that p∣nb, a contradiction since (nb,p)=1. Hence we conclude that d≢0(mod⁡p) and so because d≢0(mod⁡p4k). Thus by (33), xk+1 is the solution of the congruence ax2≡b(mod⁡p4k).


### 4.2.  Basic Family of Iteration Functions

Basic family of iteration functions denoted byBm(x) is a well-known class of iterative algorithms of order m for solving a nonlinear equation in one variable. The details of Basic Family and its mathematical interpretation regarding existence and characterizations have been discoursed earlier in [5]. It has been proved that the members of this family like B2 and B3 coincide with well-known Newton's and Halley's methods. We further see that the member B4(x) coincides with a member of Householder's Family of order four. However, we demonstrate that the Basic family of iteration functions is more convenient in finding roots of the given congruence with desired convergence. To find the solutions of congruences modulo pk, we need to recall the basics of this family as given in [5] (for details see page 1–3 in [13]).Letf(x) be a polynomial of degree ≥2 over the field of complex numbers. For integer m≥2, let Lm(x) be a square matrix of order m whose diagonals elements are f(x) defined as
(34)Lm(x)=(f(x)00⋯0f′(x)f(x)0⋯0f′′(x)2f′(x)f(x)⋯0⋮⋮⋮⋮⋮fm-1(x)(m-1)!fm-2(x)(m-2)!fm-3(x)(m-3)!⋯f(x)).
For j=12,…, let Lmj(x) be a square matrix of order m-j obtained by removing first j rows and last j columns of the matrix Lm(x) together with L11(x)=1 given as
(35)Lmj(x)=(fj(x)j!fj-1(x)(j-1)!⋯0fj+1(x)(j+1)!fj(x)j!⋯0⋮⋮⋮⋮fm-1(x)(m-1)!fm-2(x)(m-2)!⋯fj(x)j!).
The family of iteration functions Bm(x) is termed as Basic Family of iteration function of order m, where
(36)Bm(x)=x-f(x)det⁡(Lm-11(x))det⁡(Lm1(x)).
Let us establish a formula for m=4. Then by (36), we obtain
(37)B4(x)=x-f(x)det⁡(L31(x))det⁡(L41(x))
Now
(38)L41(x)=(f′(x)f(x)0f′′(x)2!f′(x)f(x)f′′′(x)3!f′′(x)2!f′(x)).
Then
(39)det⁡(L41(x))=(f′(x))3-12f(x)f′(x)f′′(x)+16(f(x))2f′′′(x).
Similarly,
(40)L31(x)=(f′(x)f(x)f′′(x)2!f′(x)).
Then
(41)det⁡(L31(x))=(f′(x))2-12f(x)f′′(x).
Substituting (39) and (41) into (37), after simplifying we obtain
(42)B4(x)=x-6f(x)(f′(x))2-3(f(x))2f′′(x)(f(x))2f′′′(x)+6(f′(x))3-6f(x)f′(x)f′′(x).
Now by (26) and (42), it is interesting to notice that both families are mapped onto each other even for fourth order members. That is, the iteration function of Householder's family for d=3 and the iteration function B4 for Basic Family are same. Therefore, the fourth order convergence for p-adic analysis of Basic Family as proved in Theorem 5 is instinctively established. However, the Basic Family is certainly more expedient to find solutions of congruences modulo pk as one can find the desired solution using (36) as well. Let us again find the solution of 2x3≡5(mod⁡74) through determinants. Here f(x)=5/x3-3 and x=3 is the initial solution. Then by (37),
(43)det⁡(L41(3))=det⁡(-527-492701081-527-4927-507291081-527)≡923(mod⁡74).
Similarly,
(44)det⁡(L31(3))=det⁡(-527-49271081-527)≡592(mod⁡74).
Substituting the values into (37), we obtain
(45)xk+1=B4(x)≡3+49(592)27(923)(mod⁡74)≡528904(mod⁡74)≡1914(mod⁡74).


### 4.3. Remarks

(1)
The overhead methods also give an equally efficient technique in solving polynomial congruences modulopk with negative-exponent. To find the solutions of the congruence az-n≡b(mod⁡pk), we solve the congruence ayn≡b(mod⁡pk), where zy≡1(mod⁡pk). This means that the solution of the first congruence is the multiplicative inverse of the solution of the later congruence. We claim that the linear congruence αz≡1(mod⁡pk) is always solvable, where α is the solution of the congruence ayn≡b(mod⁡pk). Then α must be a solution of the congruence ayn≡b(mod⁡p). That is aαn≡b(mod⁡p). Since p∤b, so p∤aαn. This clearly shows that p∤α. Hence (α,p)=1. Consequently, the linear congruence αz≡1(mod⁡pk) is solvable as we know that the linear congruence αz≡1(mod⁡pk) is solvable if and only if (α,p)=1. Let β be the solution of the linear congruence αz≡1(mod⁡pk). Then β is the desired solution of az-n≡b(mod⁡pk). By (45), y≡1914(mod⁡74) satisfies 2y3≡5(mod⁡74). To find a solution of 2z-3≡5(mod⁡74), we solve the linear congruence 1914z≡1(mod⁡74). It is easy to see that z=β≡2189(mod⁡74) is its solution. Hence, β≡2189(mod⁡74) is the desired solution of the congruence 2z-3≡5(mod⁡74).
(2)
The text does not discuss the well-known Halley's third order iterative method as it can be seen that it is a subcase of both families discussed above. In the Householder's family ford=2 and in basic iteration family for m=3, the results yield Halley's method.In the following algorithm, we summarize the solutions of congruences discussed in Theorems3, 4, and 5.


### 4.4. Algorithm

Step  1: Setx1 as initial estimate.Step  2:(46)k={log⁡3m,ifEquation(10)or(16)isused.log⁡4m,ifEquation(26)isused.Step  3: Fori=1 to k do
(47)xi+1={f(xi)mod⁡p3m,ifEquation(10)or(16)isused.f(xi)mod⁡p4m,ifEquation(26)isused.Step  4: Solution =xi+1The following algorithm is an improved form of the above given algorithms for any arbitrary value ofq where q is the order of convergence of the iterative method induced.Step  1: Setx1 as initial estimate.Step  2:(48)k=log⁡qm,q=3,4,…Step  3: Fori=1 to k do
(49)xi+1=f(xi)mod⁡pqmStep  4: Solution =xi+1


## 4.1. Householder's Family

Householder's methods are a class of well-known iterative algorithms for solving a nonlinear equation in one variable. Letf be a function of one variable with continuous derivatives of order p+1. The formula for Householder's method of order p+1 to perform iterations is
(23)xk+1=xk+p(1/f)p-1(xk)(1/f)p(xk).
Let us establish a formula for p=3 using  (23)(
p
-
1
)th derivative of 1/f(x)(24)=2f′(x)2f(x)3-f′′(x)f(x)2.
Similarly, pth derivative of 1/f(x)(25)=-6f′(x)3f(x)4+6f′(x)f′′(x)f(x)3-f′′′(x)f(x)2.
Substituting the values of (24) and (25) into (23), we obtain
(26)xk+1=(-6f(xk)f′(xk)f′′(xk))-13f(xk)[f(xk)f′′(xk)-2f′(xk)2]×(f(xk)2f′′′(xk)+6f′(xk)3-6f(xk)f′(xk)f′′(xk))-1)+xk.
In the following theorem, we use Householder's method of order 4 in order to find the solutions of congruences of the form axn≡b(mod⁡p4k), k≥1, from the solutions of the congruence axn≡b(mod⁡pk).Theorem 5.
Leta,b, and n>0 be integers which are not divisible by a prime p>3. If xk, k≥1 is a solution of the congruence axn≡b(mod⁡pk) then xk+1 is the solution of the congruence axn≡b(mod⁡p4k) satisfying the equation
(27)xk+1=(+a2(n+1)(n+2)xk2n)-1(b2(n2-1)+2ab(2n2+1)xkn+a2(n2-1)xk2n)×(b2(n-1)(n-2)+4ab(n2-1)xkn+a2(n+1)(n+2)xk2n)-1)xk.Proof.
To prove this, letf(x)=b/xn-a and solve f(x)=0 using (26); we get
(28)xk+1=(+6n2(n+1)b2xk2n+3(bxkn-a))-13(bxkn-a)[(bxkn-a)(n(n+1)bxkn+2)-2n2b2xk2n+2]×((bxkn-a)2(-n(n+1)(n+2)bxkn+3)-6n3b3xk3n+3vvvv.+6n2(n+1)b2xk2n+3(bxkn-a))-1)+xk=(×(n+1)(n+2)bxkn-6n3b3)-13xk(b-axkn)[n(n+1)(b-axkn)-2n2b2]×(6n2(n+1)b2(b-axkn)-(b-axkn)n×(n+1)(n+2)bxkn-6n3b3)-1)+xk=(+a2(n+1)(n+2)xk2n)-1(b2(n2-1)+2ab(2n2+1)xkn+a2(n2-1)xk2n)×(b2(n-1)(n-2)+4ab(n2-1)xkn+a2(n+1)(n+2)xk2n)-1)xk.
Next we show that xk+1 is a root of the congruence axn≡b(mod⁡p4k). Now if xk is the solution of axn≡b(mod⁡pk) then for some integer t, we have, axkn=b+tpk. Putting in (27), we obtain
(29)xk+1=(+(n+1)(n+2)(b+tpk)2)-1(b2(n2-1)+2b(2n2+1)(b+tpk)+(n2-1)(b+tpk)2)×(b2(n-1)(n-2)+4b(n2-1)(b+tpk)+(n+1)(n+2)(b+tpk)2)-1)xk=(+(n+1)(n+2)t2p2k)-1(6n2b2+6n2btpk+(n2-1)t2p2k)×(6n2b2+6n(n+1)btpk+(n+1)(n+2)t2p2k)-1)xk.
This implies that
(30)axk+1n≡(+(n+1)(n+2)t2p2k}n)-1(b{6n2b2+6n2btpk+(n2-1)t2p2k}n)×(+(n+1)(n+2)t2p2k}nb{6n2b2+6n(n+1)btpk+(n+1)(n+2)t2p2k}n)-1)(b+tpk).
Using Binomial Series expansion, we obtain
(31)[6n2b2+6n2btpk+(n2-1)t2p2k]n(b+tpk)=6n(nb)2nb+6nn(nb)2ntpk+6n-1(n-1)(3n2+n+1)(nb)2n-1t2p2k+6n-1n(n-1)(n3-n2-1)(nb)2n-2t3p3k+6n(nb)2ntpk+6n26n-1(nb)2n-1t2p2k+6n-1n(n-1)(3n2+n+1)(nb)2n-2t3p3k+termsinvolvingp4k≡6n(nb)2nb+6n(n+1)(nb)2ntpk+6n-1(3n3+4n2-1)(nb)2n-1t2p2k+6n-1n2(n-1)(n+1)2(nb)2n-2t3p3k(mod⁡p4k).
Similarly, we expand denominator to get
(32)b[6n2b2+6n(n+1)btpk+(n+1)(n+2)t2p2k]n=6n(nb)2nb+6n(n+1)(nb)2ntpk+6n-1(n+1)(n+2)(nb)2n-1t2p2k+6n-1(n+1)2(n-1)(n+2)(nb)2n-2t3p3k+3.6n-1(n-1)(n+1)2(nb)2n-1t2p2k+6n-1(n-1)(n+1)3(n-2)(nb)2n-2t3p3k+termsinvolvingp4k≡6n(nb)2nb+6n(n+1)(nb)2ntpk+6n-1(3n3+4n2-1)(nb)2n-1t2p2k+6n-1n2(n-1)(n+1)2(nb)2n-2t3p3k(mod⁡p4k).
Substituting (31) and (32) into (30), we get
(33)axk+1n≡bdd(mod⁡p4k)where,d=6n(nb)2nb+6n(n+1)(nb)2ntpk+6n-1(3n3+4n2-1)(nb)2n-1t2p2k+6n-1n2(n-1)(n+1)2(nb)2n-2t3p3k.
Next we claim that d≢0(mod⁡p). To prove our assertion we let d=6n(nb)2nb+6n(n+1)(nb)2ntpk+6n-1(3n3+4n2-1)(nb)2n-1t2p2k+6n-1n2(n-1)(n+1)2(nb)2n-2t3p3k≡0(mod⁡p). But then 6n(nb)2nb≡0(mod⁡p). This shows that (nb)2n≡0(mod⁡p) as p>3 and (b,p)=1. Which further implies that p∣nb, a contradiction since (nb,p)=1. Hence we conclude that d≢0(mod⁡p) and so because d≢0(mod⁡p4k). Thus by (33), xk+1 is the solution of the congruence ax2≡b(mod⁡p4k).


## 4.2.  Basic Family of Iteration Functions

Basic family of iteration functions denoted byBm(x) is a well-known class of iterative algorithms of order m for solving a nonlinear equation in one variable. The details of Basic Family and its mathematical interpretation regarding existence and characterizations have been discoursed earlier in [5]. It has been proved that the members of this family like B2 and B3 coincide with well-known Newton's and Halley's methods. We further see that the member B4(x) coincides with a member of Householder's Family of order four. However, we demonstrate that the Basic family of iteration functions is more convenient in finding roots of the given congruence with desired convergence. To find the solutions of congruences modulo pk, we need to recall the basics of this family as given in [5] (for details see page 1–3 in [13]).Letf(x) be a polynomial of degree ≥2 over the field of complex numbers. For integer m≥2, let Lm(x) be a square matrix of order m whose diagonals elements are f(x) defined as
(34)Lm(x)=(f(x)00⋯0f′(x)f(x)0⋯0f′′(x)2f′(x)f(x)⋯0⋮⋮⋮⋮⋮fm-1(x)(m-1)!fm-2(x)(m-2)!fm-3(x)(m-3)!⋯f(x)).
For j=12,…, let Lmj(x) be a square matrix of order m-j obtained by removing first j rows and last j columns of the matrix Lm(x) together with L11(x)=1 given as
(35)Lmj(x)=(fj(x)j!fj-1(x)(j-1)!⋯0fj+1(x)(j+1)!fj(x)j!⋯0⋮⋮⋮⋮fm-1(x)(m-1)!fm-2(x)(m-2)!⋯fj(x)j!).
The family of iteration functions Bm(x) is termed as Basic Family of iteration function of order m, where
(36)Bm(x)=x-f(x)det⁡(Lm-11(x))det⁡(Lm1(x)).
Let us establish a formula for m=4. Then by (36), we obtain
(37)B4(x)=x-f(x)det⁡(L31(x))det⁡(L41(x))
Now
(38)L41(x)=(f′(x)f(x)0f′′(x)2!f′(x)f(x)f′′′(x)3!f′′(x)2!f′(x)).
Then
(39)det⁡(L41(x))=(f′(x))3-12f(x)f′(x)f′′(x)+16(f(x))2f′′′(x).
Similarly,
(40)L31(x)=(f′(x)f(x)f′′(x)2!f′(x)).
Then
(41)det⁡(L31(x))=(f′(x))2-12f(x)f′′(x).
Substituting (39) and (41) into (37), after simplifying we obtain
(42)B4(x)=x-6f(x)(f′(x))2-3(f(x))2f′′(x)(f(x))2f′′′(x)+6(f′(x))3-6f(x)f′(x)f′′(x).
Now by (26) and (42), it is interesting to notice that both families are mapped onto each other even for fourth order members. That is, the iteration function of Householder's family for d=3 and the iteration function B4 for Basic Family are same. Therefore, the fourth order convergence for p-adic analysis of Basic Family as proved in Theorem 5 is instinctively established. However, the Basic Family is certainly more expedient to find solutions of congruences modulo pk as one can find the desired solution using (36) as well. Let us again find the solution of 2x3≡5(mod⁡74) through determinants. Here f(x)=5/x3-3 and x=3 is the initial solution. Then by (37),
(43)det⁡(L41(3))=det⁡(-527-492701081-527-4927-507291081-527)≡923(mod⁡74).
Similarly,
(44)det⁡(L31(3))=det⁡(-527-49271081-527)≡592(mod⁡74).
Substituting the values into (37), we obtain
(45)xk+1=B4(x)≡3+49(592)27(923)(mod⁡74)≡528904(mod⁡74)≡1914(mod⁡74).


## 4.3. Remarks

(1)
The overhead methods also give an equally efficient technique in solving polynomial congruences modulopk with negative-exponent. To find the solutions of the congruence az-n≡b(mod⁡pk), we solve the congruence ayn≡b(mod⁡pk), where zy≡1(mod⁡pk). This means that the solution of the first congruence is the multiplicative inverse of the solution of the later congruence. We claim that the linear congruence αz≡1(mod⁡pk) is always solvable, where α is the solution of the congruence ayn≡b(mod⁡pk). Then α must be a solution of the congruence ayn≡b(mod⁡p). That is aαn≡b(mod⁡p). Since p∤b, so p∤aαn. This clearly shows that p∤α. Hence (α,p)=1. Consequently, the linear congruence αz≡1(mod⁡pk) is solvable as we know that the linear congruence αz≡1(mod⁡pk) is solvable if and only if (α,p)=1. Let β be the solution of the linear congruence αz≡1(mod⁡pk). Then β is the desired solution of az-n≡b(mod⁡pk). By (45), y≡1914(mod⁡74) satisfies 2y3≡5(mod⁡74). To find a solution of 2z-3≡5(mod⁡74), we solve the linear congruence 1914z≡1(mod⁡74). It is easy to see that z=β≡2189(mod⁡74) is its solution. Hence, β≡2189(mod⁡74) is the desired solution of the congruence 2z-3≡5(mod⁡74).
(2)
The text does not discuss the well-known Halley's third order iterative method as it can be seen that it is a subcase of both families discussed above. In the Householder's family ford=2 and in basic iteration family for m=3, the results yield Halley's method.In the following algorithm, we summarize the solutions of congruences discussed in Theorems3, 4, and 5.


## 4.4. Algorithm

Step  1: Setx1 as initial estimate.Step  2:(46)k={log⁡3m,ifEquation(10)or(16)isused.log⁡4m,ifEquation(26)isused.Step  3: Fori=1 to k do
(47)xi+1={f(xi)mod⁡p3m,ifEquation(10)or(16)isused.f(xi)mod⁡p4m,ifEquation(26)isused.Step  4: Solution =xi+1The following algorithm is an improved form of the above given algorithms for any arbitrary value ofq where q is the order of convergence of the iterative method induced.Step  1: Setx1 as initial estimate.Step  2:(48)k=log⁡qm,q=3,4,…Step  3: Fori=1 to k do
(49)xi+1=f(xi)mod⁡pqmStep  4: Solution =xi+1


## 5. Numerical Examples

Let us solve the congruence2x3≡5(mod⁡781) by using Hensel's lemma (HL), Abbasbandy’s method (AM), a variant of Newton's method (VN), Householder's method (HM), and Basic Family's (BM) method. In order to solve a polynomial congruence of the form axn≡b(mod⁡pk),k≥1, it is sufficient to solve axn≡b(mod⁡p). Once we do this, then we can apply algorithm given Section 4.4 for finding the solutions of axn≡b(mod⁡p3k) from the solutions of the congruence axn≡b(mod⁡pk). Therefore, we first solve the congruence 2x3≡5(mod⁡7). By inspection we see that x≡3(mod⁡7) and x≡4(mod⁡7) are the solutions of the congruence 2x3≡5(mod⁡7). Thus we choose x1=3 as our initial guess. Then by Algorithm given in Section 4.4, we have
(50)x2≡3(mod⁡72),x2≡199(mod⁡73).
We repeat above process to find the roots of the given congruence modulo 74, 78,79 and so on until we get the solution of the congruence 2x3≡5(mod⁡781). The necessary computations are summarized in Table 1.Table 1
Comparison of HL, AM/VN, and HM/BM.
Methods
x
k  (modpα)
x
k
+
1  (modpmα)
HL
3
3(mod72)
AM/VN
3
199(mod⁡73)
HM/BM
3
1914(mod⁡74)
HL
3
199(mod⁡73)
AM/VN
199
37399890(mod⁡79)
HM/BM
1914
24211798063820(mod⁡716)
HL
199
1914(mod⁡74)
AM/VN
37399890
43741341794232381830191(mod727)
HM/BM
24211798063820
954381941076…900159613690770(mod764)
HL
1914
573(mod75)
AM/VN
43741341794232381830191
24452773833…232537600(mod⁡781)
Solution of the congruence2x3≡5(mod⁡781) with initial estimate x1=3.


## 6. Conclusion

The complexity of a typical method for numerical computations using Theorem2 is linear. In the underlying work we have suggested various methods that drastically reduce the complexity for such computations to a logarithmic scale. It is easily deduced from the algorithm given in Section 4.4 that the complexity of the described method is O(log⁡m). Additionally the method developed is an explicit technique which does not require any numerical computation for finding any sort of derivative. Therefore, the techniques developed in this paper perform much faster for values of m in powers of 3,4,… in contrast with existing techniques for solving polynomial congruences. Moreover the research work proves that both families of iterative function, that is, the Householder's and Basic iteration family work p-adically as shown in various results. Furthermore we have shown the efficacy of the given method for solving negative exponent equations of the form ax-n≡b.



---

*Source: 575064-2014-05-05.xml*