P-adic division algorithm

Encyclopedia : P : PA : PAD : P-adic division algorithm

The correct title of this } is }}}. The initial letter is capitalized due to [Naming conventions #Lower case first lettertechnical restrictions].

The p-adic division algorithm is a simple algorithm for dividing p-adic numbers in mathematics. Most algorithms proceed one p-adic digit at a time, but this algorithm improves the number of correct digits in the quotient by a factor of c during each calculation. Furthermore, it is very easy to define.

Description of the algorithm

To compute the inverse of a, first choose a number c > 1, and an initial guess x₀, which must be chosen to have at least 1 correct p-adic digit, that is x₀ a ≡ 1 (mod p). Then, apply the iteration

[x_=\frac-a^\left(\frac-x_\right)^c. ]

The result is a polynomial in x_k and a after c has been chosen.

One can also convert nth root algorithms from real numbers to p-adic numbers.

Example

To calculate 1/11 in Q₇ with c = 3, we start with x₀ = 2. The first three iterates are

[x_1=842, \,]

[x_2=72207276962, \,]

[x_3=45554184106538309239332600382503722. \,]

This tells us that 7²⁷ divides (45554184106538309239332600382503722×11 − 1).

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.