20090705, 00:22  #1 
Einyen
Dec 2003
Denmark
2^{2}·7·11^{2} Posts 
question
Its not really homework, just something I'm wondering about.
Given 2 primes p and q I want to find the smallest k>0 so (2*k*p+1) = 0 (mod q) Is there any faster way than trying all k from 1 until you find one that works? Last fiddled with by ATH on 20090705 at 00:22 
20090705, 03:49  #2 
"Lucan"
Dec 2006
England
2·3·13·83 Posts 
I helieve you use the Extended Euclidean Algorithm.

20090705, 17:53  #3 
"Lucan"
Dec 2006
England
194A_{16} Posts 
Hope to spare you the indignities I suffered when I asked
the same question for the same reason http://mersenneforum.org/showthread.php?t=9700 David 
20090706, 00:41  #4 
Einyen
Dec 2003
Denmark
3388_{10} Posts 
Thanks, it was just something like this I was looking for:
(2kp+1)=0 (mod q) => 2kp+1= c*q => c*q  2kp = 1 Then I can find c and more importantly 2*k my using the algorithm on GCD(p,q). Allready tested it and it works great. Last fiddled with by ATH on 20090706 at 00:52 
20090706, 07:41  #5  
"Lucan"
Dec 2006
England
2·3·13·83 Posts 
Quote:
I see Davar55 has revived that embarrassing thread I cited in the Math forum! Last fiddled with by davieddy on 20090706 at 07:42 
