-- 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?