hermann on Tue, 21 Nov 2023 11:56:18 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: sqrt(x,n) for non-prime n? 

On 2023-11-21 09:41, Aurel Page wrote:

Dear Hermann,

You can use 5-adics:
? sqrt(-1+O(5^3))
% = 2 + 5 + 2*5^2 + O(5^3)

Best,
Aurel


Thank you — every day something new to learn with PARI/GP.
I have not used p-adic numbers until now.

? s=sqrt(-1+O(5^3))
%26 = 2 + 5 + 2*5^2 + O(5^3)
? s%s.mod
%27 = 57
? Mod(s%s.mod,5^3)^2
%28 = Mod(124, 125)
? Mod(s,5^3)^2
%29 = Mod(124, 125)
?

What can be done if modulus is not a p-adic number?
Like n=856 in example of:
https://en.m.wikipedia.org/wiki/Kunerth%27s_algorithm

sqrt(41) (mod 856) is 345, can that be determined with PARI/GP somehow?

? Mod(345,856)^2
%30 = Mod(41, 856)
?