Find common factors of any two numbers

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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

Answer 6

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

Answer 7

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