wraithx on Wed, 25 Jan 2023 04:02:41 +0100

 Looking for a smaller solution...

• To: pari-users@pari.math.u-bordeaux.fr
• Subject: Looking for a smaller solution...
• From: wraithx@morpheus.net
• Date: Tue, 24 Jan 2023 21:01:24 -0600
• Delivery-date: Wed, 25 Jan 2023 04:02:42 +0100
• Dkim-signature: v=1; a=rsa-sha256; c=simple/simple; d=morpheus.net; s=mail; t=1674615692; bh=oxDuBNiCLiwSruTpEblg6UVTMu2wVfJzPfZa5JHOD7I=; h=Date:From:To:Subject:From; b=LrqgiC+8h3p+kfkk5p9Qsge9McKZEuuB8s2IkbN3lhEUZMcarPSWqs6f+nrJFIPXH 4NrpjDYSrXzzf3yaHre4hSN2T3Nl8bE9qrnT41ufSGE+QuUEIKBt+em5tqfb1SW+3K g3lmnm85h9JT0VCrjUXoarpDt5ksiCBDlZBMnzAI=
• User-agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:31.0) Gecko/20100101 Thunderbird/31.2.0

```Hello,

```
While I was working on a problem, someone offered a Pari/GP solution. While it works great, the solution is larger than I'd like. I was wondering if there was an alternate way to compute the solution that results in a smaller answer?
```
Here is a simplified version of the problem I'm working on:
--------------------------------------------------------------------------
```
Does anyone know of a way to find, or construct, a number B = k*x + y with x and y given, that is only divisible by primes from a finite set of primes P?
```
```
For example, if x=97929 and y=83261 and P = [1171, 1429, 1811, 2339], how would we find or construct B? Or, perhaps show that one doesn't exist?
```
```
I know we could do a brute force search, looping over k values and checking the factors of B, but I'm hoping someone might know of a way to construct, or constructively find, B. Is this possible?
```--------------------------------------------------------------------------

```
In the full problem I'm working on, my numbers x and y have a few hundred digits, and my set P has over 1000 primes. Also, x has only small prime factors p^e, with p a prime < 1000 and where e is usually 1, but can be higher, like 2^13, or 3^8, 7^5, etc. Also, all p are less than the smallest prime in P, ie no prime is in both sets.
```
The code that was offered is:
b(x,y,P)={G=znstar(x,1);matsolvemod(matconcat(vector(#P,i,znlog(P[i],G))),G.cyc~,znlog(y,G))}
```
which "outputs a vector giving the exponents that each of the primes in P need to be raised to in the product." ie B = product(P[i]^e[i]) where e[i] is the output of the above function.
```
```
For the full problem, this does give a solution, but each exponent e[i] in the solution has over 90 digits. Also, Pari/GP only finds exponents for 142 of the primes from P (the rest of the exponents for the other primes in the set are 0). I understand this is due to the fact that my x value has 141 factors (p_i^e_i).
```
```
Does anyone know of a way to reduce the size of the "exponents" in the solution? Perhaps by using more primes from the set P? Is there a way to get Pari/GP to use more than 142 primes from P to generate its solution to this problem? I don't need to find the smallest B value to my problem, but I would like to find a "small" B value that is computable. Perhaps a B value with only a few hundred, or a few thousand, digits. Thank you in advance for any help!
```
-David C.

```