-- This exercise is about computing approximations to p-adic algebraic numbers.
-- This function, HenselRoot, computes the first few terms of a
-- p-adic root of a polynomial
-- P the prime
-- F the univariate polynomial
-- Alpha a root of F modulo P (and not a root of the first derivative)
-- N the number of terms to compute.
-- The result is a list L of p-adic "digits" to be interpreted as
-- L[1]*P^0 + L[2]*P^1 + L[3]*P^2 + ...
Define HenselRoot(P, F, Alpha, N)
X := Indet(UnivariateIndetIndex(F));
V := Subst(F,X,Alpha);
If V <> 0 And Mod(LC(V), P) <> 0 Then Return [] EndIf; -- bad starting point
F1 := Der(F, X); -- F1 is derivative of F
V1 := Subst(F1,X,Alpha);
If V1 = 0 Or Mod(LC(V1),P) = 0 Then Return []; EndIf; -- precondition not satisfied
InvV1 := PowerMod(LC(V1), P-2, P); -- compute reciprocal of V1
Ans := [Alpha];
For I := 1 To N Do
V := Subst(F, X, Alpha)/P^I; -- division will be exact
If V <> 0 Then V := Mod(LC(V), P); EndIf;
Delta := Mod(-V*InvV1, P);
Append(Ans, Delta);
Alpha := Alpha + P^I*Delta;
EndFor;
Return Ans;
EndDefine; -- HenselRoot
-- An example: computes the 5-adic representation of 1/3
Use Q[x];
HenselRoot(5, 3*x-1, 2, 20);
-- Study the function HenselRoot to understand how it works.
-- Without using CoCoA can you determine which of the following reside
-- in Z_5: 1/3, sqrt(6), 3/5?
-- Find the first few p-adic ``digits'' of alpha in Z_5 such
-- that 3 alpha - 1 = 0. Do the digits repeat? Do all rationals in
-- Z_5 have repeating p-adic digits? Is a p-adic number with
-- repeating digits necessarily rational?
-- How many gamma in Z_2 are there such that gamma^3-3=0?
-- How many beta in Z_2 are there such that beta^2-17=0?