| |
 |
|
|
Science Forum Index » Mathematics Forum » Diophantine question
Page 1 of 1
|
| Author |
Message |
| philippe |
 Posted: Sun Dec 28, 2003 5:15 pm |
|
|
|
Guest
|
Hi,
I have to solve the diophantine equation x*(p+A*y)=B (unknown x,y; all
factors of B are known)
i am able to "resume" that to x*(1+A*y1)=B1 
is there in some place a way to solve this equation without testing all
possible combinaisons of sub factors of B1 ?
Any kind of pointers will be appreciated.
BR
/Philippe |
|
|
| Back to top |
|
| Robert Israel |
| Posted: Sun Dec 28, 2003 8:19 pm |
|
|
|
Guest
|
In article <bsnkmn$9qk$1@news-reader5.wanadoo.fr>,
philippe <coustaux.philippe@ns.wanadoo.fr> wrote:
Quote: I have to solve the diophantine equation x*(p+A*y)=B (unknown x,y; all
factors of B are known)
i am able to "resume" that to x*(1+A*y1)=B1
I don't know what "resume" means for you in this context, but let's
say that's the question...
I don't suppose x=B1, y1=0 is allowed?
Quote: is there in some place a way to solve this equation without testing all
possible combinaisons of sub factors of B1 ?
Well, you're looking for factors of B1 that are == 1 mod A.
If B1 = product_{j=1}^N p_j^{n_j}, a factor of B1 is product_j p_j^{m_j}
where 0 <= m_j <= n_j for all j. One way to do this (which might
be useful if A is not too large) is with dynamic programming.
First, discard any p_j that divides A.
Let B(0) = 1, and for k from 1 to N let B(k) = product_{j=1}^k p_j^{n_j}.
For k from 0 to N and a coprime to A, let x(k,a) be a factor of
B(k) that is == a mod A if such exists, otherwise 0.
Begin with x(0,1) = 1, x(0,a) = 0 otherwise.
Let o_k be the order of p_k mod A. Then for a in {1,2,...,A-1} and
coprime to A,
x(k, a) = max_{j=0}^{min(n_k, o_k)} x(k-1, (a p_k^(-j)) mod A) p_k^j
Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2 |
|
|
| Back to top |
|
| |
|
Page 1 of 1
All times are GMT - 5 Hours
The time now is Fri Dec 05, 2008 5:57 am
|
|