Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 1 down vote favorite

For a given set of numbers, I need to find the lowest common divisor that's higher than a given number, N. Is there a way to do that?

share|improve this question
Do you mean the least common multiple that is greater than $N$? – Brian M. Scott Oct 21 '12 at 17:44
No. I do mean a divisor. – shesek Oct 21 '12 at 17:48
1  
@shesek Any common divisor divides the gcd and every divisor of gcd is a common divisor. Hence, what you are after is $$\min \{d| \gcd(x_1,x_2,\ldots,x_k): d > N\}$$ Is this what you are after and am I interpreting your question correctly? – user17762 Oct 21 '12 at 17:50
3  
I’d find the gcd $d$ of the set of numbers. If I could easily find its prime factorization, I’d do so, and from that I’d find the smallest subproduct bigger than $N$. – Brian M. Scott Oct 21 '12 at 17:57
1  
If I were programming it, I don’t think that I’d bother with the prime factors: factorization tends to be difficult. You might find that a simple search from $N+1$ to $d$, testing each number to see whether it divides $d$ and picking the first hit, is the way to go. – Brian M. Scott Oct 21 '12 at 18:46
show 4 more comments

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.