How to find integers that divide another integer.

Question

For mathematical proofs, I want to be able to find all integers that divide another integer. For instance, integers that divide 50.

Following the definition that:

• $a$ and $b$ are integers where $b$ not equal to $0$
• $a$ is divisible by $b$ ($a/b$), if there is another integer $c$ where $a = bc$

In the example above. I could say that 50 is divisible by 5 since $10\times5=50$ satisfying $a = bc$. But how can I prove it for all integers using the previous definition? Or am I looking at the wrong thing?

Thanks.

Answer 1

Can you use prime factorization? The best way to do this is say that $50 = 2^1 * 5^2$, and that any number that divides $50$ must be equal to $2^n * 5^m$, where $0 \leq n \leq 1$ and $0 \leq m \leq 2$. The full list is

$$ 2^0 * 5^0 = 1\\ 2^0 * 5^1 = 5\\ 2^0 * 5^2 = 25\\ 2^1 * 5^0 = 2\\ 2^1 * 5^1 = 10\\ 2^1 * 5^2 = 50 $$

If we have one of these numbers, $(2^n * 5^m)$, then we can show that $ (2^n * 5^m) * (2^{1-m} * 5^{2-m}) = 50$, so it divides $50$ by your definition of "divides."

Answer 2

In general factoring is hard - that is the basis of some codes. However in the case of small numbers like $50$ which you can factorise, splitting into distinct prime factors helps to achieve a systematic approach and gives a check that you have found them all.

If $$N=\prod_{r=1}^np_r^{a_r}$$ is the factorisation into distinct primes, with the prime $p_r$ appearing $a_r$ times in the factorisation, then the factors are the numbers of the form $$F=\prod_{r=1}^np_r^{b_r}: 0\le b_r\le a_r$$ and there are $$K=\prod_{r=1}^n(a_r+1)$$ distinct factors including $1$ and $N$.

In particular we can note that the number of factors is even if any of the $a_r$ are odd - so the positive integers with an odd number of distinct positive integer factorisations are precisely the square numbers.