0
$\begingroup$

I have not been able to find any other questions on Math Exchange that answer this specific question. This is the most similar question that I have found, but the question is so poorly constructed that the answer is completely inadequate.

I have tried looking on Google to no avail. I did find this, but the formula seems incredibly inefficient and therefore insufficient. For instance, if we took the number 21...

21 % 1 = 0
21 % 2 = 1
21 % 3 = 0
21 % 4 = 1
21 % 5 = 1
21 % 6 = 3
21 % 7 = 0
...

Now imagine finding the common factors of numbers much greater than 21, such as 2,252 and 4,082... The method above would not be efficient whatsoever.

What I am trying to do is figure out the most efficient way to find all of the common factors of any given two numbers.

What is the most optimal method to find the common factors of any two numbers?

$\endgroup$
  • 2
    $\begingroup$ Factoring is very difficult. The Euclidean Algorithm allows you to rapidly compute the $\gcd$ of two specified numbers, which is, at least, something. $\endgroup$ – lulu Dec 22 '17 at 15:36
  • $\begingroup$ "Most optimal" is an extremely hard question, except for very trivial problems. I sugest satisfying with a "good" or "very good" method instead. $\endgroup$ – Ove Ahlman Dec 22 '17 at 15:38
  • $\begingroup$ @OveAhlman I mean, if it is impossible or nearly impossible to find the most optimal method to do so, a very good method would be sufficient. Can you share your 'very good' algorithm in the answer section below? $\endgroup$ – Anthony Dec 22 '17 at 15:40
3
$\begingroup$

There is no known most optimal way to do what you want.

Suppose we wish to find the list of common factors of the positive integers $x$ and $y$.

Step 1: Use the Euclidean algorithm to find the greatest common divisor of $x$ and $y$. Every common factor divides the greatest common divisor and the greatest common divisor is the smallest number having this property. Let $d = \gcd(x,y)$.

Step 2: Factor $d$ into a product of powers of (distinct) primes. Good luck. This is generally hard. If $d = 1$, this is the only common factor of $x$ and $y$. Otherwise, suppose $d = p_1^{k_1}p_2^{k_2} \cdots p_n^{k_n}$ for some positive integer $n$, distinct primes $p_i$, and positive integers $k_i$.

Step 3: Generate the common factors by iterating as if the incremented exponents, $k_i+1$, are the radices in a mixed-radix number. An example is useful here. Suppose $d = 2^3 5^2$. Then the radices are $3+1=4$ and $2+1=3$ and the common divisors are

00: 2^0 5^0 = 1
01: 2^0 5^1 = 5
02: 2^0 5^2 = 25
10: 2^1 5^0 = 2
11: 2^1 5^1 = 10
12: 2^1 5^2 = 50
20: 2^2 5^0 = 4
21: 2^2 5^1 = 20
22: 2^2 5^2 = 100
30: 2^3 5^0 = 8
31: 2^3 5^1 = 40
32: 2^3 5^2 = 200

 

 

Full example: Say $x = 31\,361\,106\,135\,591\,137$ and $y = 58\,311\,315\,507\,493$. Then $d = 178\,344\,427 = 547\cdot 571^2$. Then the common factors are (in sorted order) $\{1,\ 547,\ 571,\ 312\,337,\ 326\,041,\ 178\,344\,427\}$.

$\endgroup$
  • $\begingroup$ i'm unfamiliar with some of the terms you used, so the examples helped big time. thanks. $\endgroup$ – Anthony Dec 22 '17 at 16:07
1
$\begingroup$

You could do a prime factorization of both numbers. By comparing the lists of prime factors, you get all common prime factors directly. All common non-prime factors are products of common prime factors.

$\endgroup$
  • $\begingroup$ Super interesting, but what is the most efficient way to find all of the common prime factors "directly"? Or how do you find common prime factors in the first place? lol $\endgroup$ – Anthony Dec 22 '17 at 15:38
  • $\begingroup$ Could you clarify what you mean by 'most efficient'? Do you want to solve your problem by hand or are you coding it up? The most common, and perhaps most straightforward way to finding a prime factorization by hand is this: home.avvanta.com/~math/def2.cgi?t=primefactorization $\endgroup$ – Alice Schwarze Dec 22 '17 at 15:44
  • 1
    $\begingroup$ In principle, it would get tricky if your number becomes much greater than your list of primes. But for numbers in the thousands, you should be fine. For example, you can find the first 1000 prime numbers of wikipedia: en.wikipedia.org/wiki/… $\endgroup$ – Alice Schwarze Dec 22 '17 at 15:49
  • 1
    $\begingroup$ It is exactly the method that the calculator is using, but slightly different and more efficient than the method under 'Can I do it myself?' method. $\endgroup$ – Alice Schwarze Dec 22 '17 at 15:52
  • 1
    $\begingroup$ There might be built-in functions in scipy, R, etc. But I would assume that they are all using prime factorization. So if you detect differences between those and your own prime factorization code it would be $\endgroup$ – Alice Schwarze Dec 22 '17 at 16:00
1
$\begingroup$

The Euclidean algorithm will find the greatest common divisor. It is based on the fact that $\gcd(a,b)=\gcd(a,a-nb)$ for any natural $n$, so you start by taking the larger modulo the smaller and repeat until you get to $0$. For your example $$\begin {array} {r r} 4082&2252\\ 1830&2252\\1830&422\\142&422\\142&136\\6&136\\6&4\\2&4\\2&0 \end {array}$$ So the greatest common divisor is $2$. The common factors will be all the factors of the $\gcd$, so if the $\gcd$ had been $12$ the common factors would be $1,2,3,4,6,12$. This lets you only factor the $\gcd$, not the numbers themselves.

$\endgroup$
  • $\begingroup$ i'm not great at math, so i'm not fluent with what particular expressions means, gcd(a,a – nb) for instance. i'm guessing that translates to 4082 - 2252 = 1830, which i can see in the top row and 2nd to top row in the left column, but the list confuses me from that point onwards. can you change your answer so that it were as if you were explaining this to a child? finding the GCD first is a great idea since all common factors are factors of this! $\endgroup$ – Anthony Dec 22 '17 at 15:55
  • 1
    $\begingroup$ Going from $1830,422$ we divide to find $1830=4\cdot 422+142$. We keep the $142$. At each stage we divide with remainder and keep the remainder. It is well described on the Wikipedia page I linked. $\endgroup$ – Ross Millikan Dec 22 '17 at 16:20
  • $\begingroup$ okay, i'm starting to understand this. yeah, i've been busy responding to all of the answers/responses on this thread. i will be looking at that right now! thanks again <3 $\endgroup$ – Anthony Dec 22 '17 at 16:26
1
$\begingroup$

The Euclidean algorithm will quickly give you the greatest common divisor of two numbers, and in its extended version will give you the formula for a linear combination of the two numbers that equates to the $\gcd$.

I use a table-based form where each line gives a valid solution of $n=A\times s + B\times t$ (reading $n,s,t$ appropriately from each column in a given line). It starts with two "trivial" lines, one for each of the two numbers concerned, and then proceeds by combining the last two lines to form the next line. Using the values $A=4082, B=2053$ as an example:

\begin{array}{c|c} n & s & t & q \\ \hline 4082 & 1 & 0 & \\ 2253 & 0 & 1 & 1 \\ 1829 & 1 & -1 & 1 \\ 424 & -1 & 2 & 4 \\ 133 & 5 & -9 & 3 \\ 25 & -16 & 29 & 5 \\ 8 & 85 & -154 & 3 \\ 1 & -271 & 491 & 8 \\ \end{array}

$q$ shows what multiple of that line to subtract from the line above to make the next line - it is as big an integer as possible to make the subtraction still leave a positive value for the next $n$.

This shows that $\gcd(4082,2253)=1$ and thus they have no common factors.

$\endgroup$
  • $\begingroup$ i am so confused by that image and some of the terms you are throwing around. i'm really bad at math, but i need this for a piece of code that i'm writing $\endgroup$ – Anthony Dec 22 '17 at 15:58
  • $\begingroup$ Sorry if it's confusing for you. The key is that each line is a valid solution to the formula $n=4082s+2253t$ (taking $n,s,t$ from the appropriate columns). The link at the top ("Euclidean algorithm") goes to the Wikipedia page which has some code. $\endgroup$ – Joffan Dec 22 '17 at 16:03
  • $\begingroup$ np!! the only reason it's confusing is because i'm not great at math, so a lot of the terms and expressions are simply foreign to me. for instance, in n = 4082s + 2253t what do the s and t represent?! the s represents "seeded" and i'm assuming the t represents "tabular", correct? but what do "seeded" and "tabular" mean lol $\endgroup$ – Anthony Dec 22 '17 at 16:10
  • 1
    $\begingroup$ No, $s$ and $t$ are just two variables, read in this case from the columns of the table depending on which row you are reading. "tabular" just means "in a table" or you might say "in an array". I will revise to avoid the word "seeded" which was somewhat metaphorical anyway. $\endgroup$ – Joffan Dec 22 '17 at 16:35
1
$\begingroup$

First compute the g.c.d. of the two numbers by the Euclidean algorithm, which $O(N)$, if $N$ is an upper bound for both numbers, then factor the g.c.d. by one of the standard algorithms, e.g. Pollard's ρ algorithm if the numbers are big.

For small numbers you can find the factorisation of the g.c.d. by hand. A way to do it rests on the following observations:

  • The smallest number which divides a given number $n$ is necessarily prime.
  • If a number is not prime, it has a divisor $d$ such that $1<d\le \sqrt n$.
  • A prime number $\ge 5$ has the form $6k+1$ or $6k+5$.

From these observations you can deduce this algorithm:

  1. Test if $n$ is divisible by $2$, and if it is,, divide it by $2$ as much as possible.
  2. Do the same with $3$ and the current value of $n$ (i.e. initial $n$ divides by the relevant $2^k$)
  3. From now on, do the same alternatively with $6k-1$ and $6k+1$ until the tested divisor is greater than the square root of the current value of $n$.
  4. The prime factors of the initial $n$ are the tested divisors with a positive answer, plus the final value of $n$.
$\endgroup$
  • $\begingroup$ awesome. thanks. this might be specifically what i was looking for, though two last questions: how big do you mean by 'big'? also, are there better algorithms if the numbers aren't 'big'? $\endgroup$ – Anthony Dec 22 '17 at 16:00
  • 1
    $\begingroup$ ‘big’ would mean here, say, from 20 decimal digits. It is very fast if the number to factorise has small prime factors, but there are other methods (lliptic curve method, quadratic sieve, …). For smaller numbers and a naive approach, you can test numbers one after the other, starting from $2$, considering only numbers congruent to $1$ or $5\bmod6$, dividing by factors found and stopping at $\sqrt{\text{current value of }n}$. $\endgroup$ – Bernard Dec 22 '17 at 16:15
  • $\begingroup$ okay, yeah, the biggest numbers i'll be dealing with will probably be no bigger than roughly 2,000, which is determined by the number of vertical pixels on some of the highest resolution monitors. i need to somehow translate all of this into javascript, but i'm not adequately understanding the mathematical side of things (terms, expressions, etc) right now :( $\endgroup$ – Anthony Dec 22 '17 at 16:24
  • $\begingroup$ @Anthony: I've added a description of the naive algorithm, which I hope to be clear. $\endgroup$ – Bernard Dec 22 '17 at 17:06
  • $\begingroup$ what does the k in 6k - 1 and 6k + 1 represent? the value of the exponent from step 2 (and step 1)? $\endgroup$ – Anthony Dec 22 '17 at 17:52
1
$\begingroup$

Numbers that you have mentioned are quite small to talk about a method. You can notice that dividing both even numbers by $2$ as long as we get an odd number into further composition results in:

$2252=2 \cdot 1126=2\cdot2\cdot563$

$4082=2\cdot2041=2\cdot13\cdot157$

An interesting thing to observe here is that:

$\sum2041=981+675+369+16$

This is coming from the structure of two prime numbers, since $13=3\cdot3+4$ and $157=3\cdot51+4$

In the above example the difference between 3-term arithmetic progression is equal to:

$d=2\cdot3\cdot51=306$

The number $51$ gets into two prime factors of $3$ and $17$ therefore the greatest common divisor can only be $2$.

$\endgroup$
  • $\begingroup$ i do not understand what that E symbol represents. aside from that, i have already written a script that accomplishes this which you can view here. how can i improve that script is the question! $\endgroup$ – Anthony Dec 24 '17 at 3:48
  • $\begingroup$ That E is a sigma symbol - the addition of a sequence of numbers. I think your script should have some limit as factoring very big numbers gets more complicated. I would first concentrate on Euclidean algorithm as other people suggested. I am sure there are examples on the net. $\endgroup$ – usiro Dec 24 '17 at 9:54
  • $\begingroup$ ah, you mean the sigma is used to indicate that a number is the sum of the sequential addition of a set of numbers, right? yeah, Euclidean's algorithm is in my script. that's how i find the GCD! $\endgroup$ – Anthony Dec 24 '17 at 18:59
0
$\begingroup$

there is a way to find the greatest common factor in number theory called Euclidean algorithm, but i don't know if that what you looking for.

$\endgroup$
  • $\begingroup$ i'm looking for an algorithm to find all of the common factors (common divisors and common multiples) -- of course including the least and greatest common factors --of any two given numbers with the least number of operations. $\endgroup$ – Anthony Dec 22 '17 at 15:45
  • 1
    $\begingroup$ @Anthony : "common multiples" is not the same as common factors. There are infinitely many common multiples -- you will have difficulties writing them all down. There are finitely many common divisors. $\endgroup$ – Eric Towers Dec 22 '17 at 16:00
  • $\begingroup$ @EricTowers ohhh okay, i used the wrong term. what i meant was all numbers that can be multiplied together to form the greatest of the two numbers, which i guess is simply 'common divisors' and or 'common factors'? $\endgroup$ – Anthony Dec 22 '17 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.