# How to find a number with no common divider between two other number

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.

• I assume by "formula" you mean not using the using prime factorisation of p anf q and choosing a prime not in either list? May 28 '16 at 12:24
• Just choose a prime larger than both of them. Or did you want your formula to have some special properties?
– lulu
May 28 '16 at 12:25
• 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$ May 28 '16 at 12:29
• 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?
– lulu
May 28 '16 at 12:33
• Oh, sorry for the confusion. No, p and q are arbitrary. May 28 '16 at 12:36

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$.
• @lulu Thanks, I noticed it. Also $\frac{p\cdot q}{gcd(p,q)}$ doesn't necessarily work. May 28 '16 at 12:46