Re: How to solve modular equations?

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* David Cleaver [2021-12-29 13:40]:
> On Wed, Dec 29, 2021 at 9:07 AM Bill Allombert <
> Bill.Allombert@math.u-bordeaux.fr> wrote:
> 
> > On Wed, Dec 29, 2021 at 01:09:20AM, David Cleaver wrote:
> > > Is there a way to solve modular equations in pari-gp?
> > >
> > > I've found how to solve simple modular equations with znlog, but how
> > would
> > > I solve:
> > > A*10^(B*n) + C*n + D = 0 mod p
> > > where A, B, C, and D are integers and p is a prime.
> > >
> > > For example, if A = 2, B = 2, C = -99, D = -9, and p = 13,
> > > how can I find which values of n are solutions to the equation?
> > >
> > > For this example, I know that this function has solutions whenever n =
> > [11,
> > > 19, 30] mod 39.
> > >
> > > Is there a way to find general solutions like this?
> >
> > For small p, it is easy:
> > First compute
> > N = p*znorder(Mod(10,p)^B)
> > and try all n between 0 and N-1.
> > This gives you all the solutions modulo N.
[...]
> I would like to use p up to 10^15, or 10^18 if I can.

For each (fixed) n0 between 0 and M-1 with M = znorder(Mod(10,p)^B),
solve for n1 mod p:

  n1 = (-1/C)(D + A*(10^B)^n0) mod p.   \\ I'm assuming gcd(C, p) = 1

Then use chinese(Mod(n0, M), Mod(n1, p)), you'll get M solutions.

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux         Fax: (+33) (0)5 40 00 21 23
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`