euclid.js

const extendedEuclidAlgorithm = (p, q, kv) => {
  let out = ''

  const Fe = (p - 1) * (q - 1)
  let uPrev = 1,
    vPrev = 0,
    u = 0,
    v = 1,
    rPrev = kv,
    r = Fe
  let i = 1
  let z = 0
  while (r !== 1) {
    const uTemp = u,
      vTemp = v,
      rTemp = r

    z = Math.trunc(rPrev / r)
    out += `Z${i} = ${rPrev} div ${r} = ${z}\n`

    u = uPrev - z * u
    out += `U${i + 1} = U${
      i - 1
    } - Z${i} * U${i} = ${uPrev} - ${z} * ${uTemp} = ${u}\n`

    v = vPrev - z * v
    out += `V${i + 1} = V${
      i - 1
    } - Z${i} * V${i} = ${vPrev} - ${z} * ${vTemp} = ${v}\n`

    r = u * kv + v * Fe
    out += `R${i + 1} = U${i + 1} * Kb + V${
      i + 1
    } * Fe = ${u} * ${kv} + ${v} * ${Fe} = ${r}\n`

    uPrev = uTemp
    vPrev = vTemp
    rPrev = rTemp

    i += 1

    out += '\n'
  }

  return out
}

console.log(extendedEuclidAlgorithm(149, 491, 419))