5
$\begingroup$

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:

Three answers were already posted using "Solve"...

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.

$\endgroup$

4 Answers 4

8
$\begingroup$

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}
*)
$\endgroup$
0
11
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – ZaMoC
    Commented Sep 4, 2022 at 19:57
  • $\begingroup$ 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. $\endgroup$
    – Roman
    Commented Sep 4, 2022 at 20:27
  • $\begingroup$ 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... $\endgroup$
    – ZaMoC
    Commented Sep 4, 2022 at 20:41
7
$\begingroup$
n /. Solve[{n^2 + 23 == 2^100*k}, {k, n}, PositiveIntegers]

enter image description here

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

114298292320608409339221863469

$\endgroup$
1
  • $\begingroup$ nice! Although a function that does the same thing as "truncate" would be very interesting. $\endgroup$
    – ZaMoC
    Commented Sep 4, 2022 at 16:07
3
$\begingroup$
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\}\}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.