# Finding least n such that n^2 + 23 is divisible by large powers of 2

Lets say that we want to find the least n such that n^2+23 is divisible by 2^100. We can compute this in one line using the Pari/GP language:

print1(truncate(-sqrt(-23+O(2^(100)))))

indeed this instantly returns

114298292320608409339221863469

If we check this number using mathematica we get

FactorInteger[114298292320608409339221863469^2 + 23]
{{2, 101}, {139, 1}, {347, 1}, {3719, 1}, {79697, 1}, {12597679, 1}, {28611917, 1}}

My question is

"is there a similar function in Mathematica?"

The only way I could get the same result in mathematica was by computing approximations of the square root of -23 using Newton's method and then testing the p-adic expansions of those approximations until they converge to a number. (I can post the code if anyone is interested).
But in Pari/GP, things are looking so much easier...

Here is also something from Pari/GP documentation that might help:

Note a very special use of truncate: when applied to a power series, it transforms it into a polynomial or a rational function with denominator a power of X, by chopping away the O(X^k). Similarly, when applied to a p-adic number, it transforms it into an integer or a rational number by chopping away the O(p^k).

EDIT:

I would really like someone to explain what the function "truncate" actually does in Pari/GP and also implement the exact same function in Mathematica.

I don't know the internals of Pari/GP either, but this looks like it:

PowerMod[-23, 1/2, 2^100]
(*  114298292320608409339221863469  *)

There's also this:

PowerModList[-23, 1/2, 2^100]
(*
{114298292320608409339221863469,
519527007793506291409129739219,
748123592434723110087573466157,
1153352307907620992157481341907}
*)

This is very fast:

Solve[n^2 + 23 == 0, Modulus -> 2^100]
(*    {{n -> 114298292320608409339221863469},
{n -> 519527007793506291409129739219},
{n -> 748123592434723110087573466157},
{n -> 1153352307907620992157481341907}}    *)

From the documentation:

Modulus->n is an option that can be given in certain algebraic functions to specify that integers should be treated modulo $$n$$.

• Well done! Although the reason that I posted this question was to understand how the function "truncate" works and if we can implement this in Mathematica. Any ideas? Commented Sep 4, 2022 at 19:57
• I don't know much about Pari/GP but from the docs you quote it looks like truncate is just a strange syntax for specifying that integers should be treated modulo a certain number. In any case, I don't think you'll get much Pari/GP help on this site here. Commented Sep 4, 2022 at 20:27
• I believe that in my example "truncate" takes the square root of a negative number and transforms it to a truncated power series. I wonder if this can be done in Mathematica... Commented Sep 4, 2022 at 20:41
n /. Solve[{n^2 + 23 == 2^100*k}, {k, n}, PositiveIntegers]

n /. Solve[{n^2 + 23 == 2^100*k}, {k, n}, PositiveIntegers] /.
C[1] -> 0 // Min

114298292320608409339221863469

• nice! Although a function that does the same thing as "truncate" would be very interesting. Commented Sep 4, 2022 at 16:07
Clear[k, n]
FindInstance[n^2 + 23 == 2^100 k, {k, n}, Integers]

> {{k -> 10305757457973967292569406234,    n ->
> 114298292320608409339221863469}}

More instances can be found by using the fourth argument; e.g.:

FindInstance[n^2 + 23 == 2^100 k, {k, n}, PositiveIntegers, 4]

$$\{\{k\to 89970487158009939302238716544192873,n\to 337714586668502527089532182369235\},\{k\to 20739937377062692735298437089238554,n\to 162144978536892754982238788424659\},\{k\to 10305757457973967292569406234,n\to 114298292320608409339221863469\},\{k\to 155910590816127116553856538253048,n\to 14058454894831131825802957122605\}\}$$