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$
5
  • $\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, 2016 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, 2016 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, 2016 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, 2016 at 12:33
  • $\begingroup$ Oh, sorry for the confusion. No, p and q are arbitrary. $\endgroup$
    – SomeNorwegianGuy
    May 28, 2016 at 12:36

1 Answer 1

Reset to default
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$
1
  • $\begingroup$ @lulu Thanks, I noticed it. Also $\frac{p\cdot q}{gcd(p,q)}$ doesn't necessarily work. $\endgroup$
    – Lieuwe Vinkhuijzen
    May 28, 2016 at 12:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .