Posts Tagged ‘Hensel’s lemma’
Solving Certain Linear Systems over the Integers.
friday, june 17th, 2011We present a (well-known) method to compute a solution to the linear system Ax=b over the integers, when it is known that the determinant of A is non-zero and that a solution with integral coefficients exists. We also provide a running time analysis.
How to Compute the 5-adic Expansion of 1/2; or: Hensel’s Lemma and (Non-Analytic) Newton Iteration.
saturday, february 6th, 2010In this post, we consider the quest of computing the 5-adic expansion of 1/2. We begin with introducing p-adic integers and numbers, and discussing when certain polynomials with coefficients in the integers have zeroes in the p-adic integers. This question is closely related to Hensel’s lemma, which can be proven using an algebraic version of Newton’s iteration. We use this to compute approximations of rational numbers in the p-adics, and consider which p-adic numers have an eventually periodic expansion.
