Re: How to solve modular equations?

[David Cleaver <wraythex@gmail.com>]

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.

Cheers,
Bill.

This is really good to know, thanks!

However, I do want to solve this for large values of p also.

I would like to use p up to 10^15, or 10^18 if I can.

Is there a way to solve this generally, or do I need to check individual n values in that range?

Thanks again for your help.

David