1

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.

SomeNorwegianGuy
  • 127
  • I assume by "formula" you mean not using the using prime factorisation of p anf q and choosing a prime not in either list? – Andrew 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$ – SomeNorwegianGuy 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. – SomeNorwegianGuy May 28 '16 at 12:36

1 Answers1

1

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

Lieuwe Vinkhuijzen
  • 653
  • 4
  • 10