1
$\begingroup$

I'm trying to find a formula for calculating $n$ such that $GCD(n, p) = 1$ and $GCD(n, q) = 1$, given the numbers $p$ and $q$. I also need it to have a linear time (O(n)) implementation i.e equally complex for big or small values of $p$ and $q$. That means no prime factorization, or just finding a prime greater than $q$ and $p$

q and p are arbitrary positive integer numbers

Is this possible? If not, why? I've tried to work it out myself/searching for it, but I don't really know where to start.

$\endgroup$
  • $\begingroup$ I assume by "formula" you mean not using the using prime factorisation of p anf q and choosing a prime not in either list? $\endgroup$ – Andrew May 28 '16 at 12:24
  • $\begingroup$ Just choose a prime larger than both of them. Or did you want your formula to have some special properties? $\endgroup$ – lulu May 28 '16 at 12:25
  • $\begingroup$ I added it to the question. But something that can run in linear time when implemented. I.e does not take any longer for big values for $q$ and $p$ $\endgroup$ – SomeNorwegianGuy May 28 '16 at 12:29
  • $\begingroup$ And, just to be clear, $p,q$ are arbitrary? (usually in number theory $p,q$ denote primes but I doubt that you mean that). You aren't supposing that $p,q$ are relatively prime or anything, right? $\endgroup$ – lulu May 28 '16 at 12:33
  • $\begingroup$ Oh, sorry for the confusion. No, p and q are arbitrary. $\endgroup$ – SomeNorwegianGuy May 28 '16 at 12:36
1
$\begingroup$

I think most of these work: $n=p\cdot q + 1$. Or you could try $n=1$. Or Or $n=p!\cdot q!+1$. For a linear-time algorithm, iterate over the numbers $2\ldots \log max(p,q)$. There is necessarily a number which is coprime to both $p$ and $q$, if they are larger than $2$.

$\endgroup$
  • $\begingroup$ @lulu Thanks, I noticed it. Also $\frac{p\cdot q}{gcd(p,q)}$ doesn't necessarily work. $\endgroup$ – Lieuwe Vinkhuijzen May 28 '16 at 12:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.