Finding Factors Efficiently

156 Views Asked by At

Let $m$ and $n$ be positive integers. What is the most efficient way to choose factors that solve this equation. Notice that two factors of 2079 must sum to 36. What is a quick way of picking numbers?

$$mn=2079$$ and $$m+n=36$$

Note that $$2079=3^3 *7*11$$

2

There are 2 best solutions below

2
On

There are only a few divisors of $2079$, namely those of the form $3^a\, 7^b\, 11^c$ with $0 \le a \le 3$, $0 \le b, c \le 1$. Hence, there are only $4 \cdot 2 \cdot 2 = 16$ choices for $m$. Considering that the choice of $m$ uniquely determines $n$, it's not too hard to just run through the possibilities.


For a more direct way, note that $n = \frac{2079}{m}$, so our second equation can be written as

$$m + \frac{2079}{m} = 36$$

Rearranging, this is just the quadratic equation

$$m^2 - 36m + 2079 = 0$$

This can be solved any number of ways, e.g. completing the square or the quadratic formula.

0
On

If the two factors $m,n$ are required to have product 2079, there is no solution with $m+n=36$ (use the quadratic formula or arithmetic/geometric mean inequality to see this). However if we require integer divisors $m,n|2079$ (and perhaps that they be distinct?), then there are solutions.

I would use the prime factorization of 2079, which you know, to list all its divisors up to half of the desired sum, $36/2 = 18$, as candidates for $m$:

$$ m = 1,3,7,9,11 $$

For each of these, subtract $n = 36-m$ and check to see if any of them divide 2079:

$$ n = 35,33,... $$

Already with $n=33$ we find success, $3+33 = 36$ and $m=3$ and $n=33$ are (distinct) divisors of 2079.