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 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$.