P-adic number computation

The p-adic expansion is a way of representing rational numbers as an infinite series of digits in base p, where p is a prime number. It is used in number theory and can be used to efficiently calculate the modular inverse of a number modulo a prime.

Here's a step-by-step description of the p-adic expansion algorithm:

1. calc function:
   • Parameters: p, a, b, and an optional parameter expands (defaulted to 10).
   • If expands is equal to 0 or b is equal to 0, the function returns an empty array [].
   • Calculates i as (a * modPow(b, p - 2, p) + 2 * p) % p. The modPow function calculates b raised to the power (p - 2) modulo p, which is used to find the modular inverse of b.
   • Logs the value of Math.floor((a - b * i) / p) to the console. This value represents the next digit in the p-adic expansion.
   • Recursively calls calc with the updated values of a, b, and expands - 1, and concatenates the result with [i].
   • The recursion continues until expands becomes 0 or b becomes 0.
2. modPow function:
   • Parameters: base, exponent, and modulus.
   • Calculates base raised to the power exponent modulo modulus using a binary exponentiation algorithm.
   • Returns the calculated result.
3. In the final line, the calc function is called with p=5, a=1, and b=3, and the result is printed to the console using console.log.

The algorithm recursively calculates the p-adic expansion of a with respect to b for a given prime p. The expansion gives a representation of the rational number a/b in base p with an infinite series of digits. However, in this implementation, the recursion is limited to expands iterations, which gives a finite approximation of the p-adic expansion.

Here’s a javascript snippet of computing p-adic expansion.

function calc(p, a, b, expands = 10) {
    if (expands === 0 || b === 0) {
      return [];
    }

    const i = (a * modPow(b, p - 2, p)+2*p) % p;
    console.log(Math.floor((a - b * i) / p));
    return [i].concat(calc(p, Math.floor((a - b * i) / p), b, expands - 1));
  }

  function modPow(base, exponent, modulus) {
    let result = 1;
    base = base % modulus;

    while (exponent > 0) {
      if (exponent % 2 === 1) {
        result = (result * base) % modulus;
      }

      exponent = Math.floor(exponent / 2);
      base = (base * base) % modulus;
    }

    return result;
}

console.log(calc(5, 1, 3));

A detailed demo can be found In the following:

Compute p-adic expansion.