0
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you for your answer, is there a way to proove it without using prime factorization? $\endgroup$ – Victor Luna Sep 19 '19 at 20:32
  • 1
    $\begingroup$ @VictorLuna Primes are the fundamental building blocks of products. Unique factorisation into primes is a key property of the positive integers. I am not sure what you think you might be able to prove without using prime factorisation. As you will see from my answer, the number of possible factors depends on the prime factorisation. $\endgroup$ – Mark Bennet Sep 19 '19 at 20:43
  • $\begingroup$ But what if we have for instance -40 as the integer. Would we be able to stil use factorization with primes? As we define prime as p > 1 where p is a natural number. I am new to proofs so I am just trying to understand. Also not sure if I am asking the right questions, $\endgroup$ – Victor Luna Sep 19 '19 at 20:47
  • $\begingroup$ $-40$ is just as factorizable as any positive integer: $-1 * 2^3 * 5^1$. The factors of $-40$ are the same as the factors of $40$, if you're counting both positive and negative factors of $40$. $\endgroup$ – Andrew Tindall Sep 19 '19 at 20:53
  • $\begingroup$ And what about integers that 50 are divisible by. Would you use a similar strategy or would it change to a = 50 * m where m is an integer and a is the number that 50 can be divisible by? $\endgroup$ – Victor Luna Sep 19 '19 at 21:53
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Would this be the same if we are trying to find the integers that divide negative numbers as well? $\endgroup$ – Victor Luna Sep 19 '19 at 20:48
  • $\begingroup$ @VictorLuna With negative integers you have an extra factor $-1$. If you are counting positive integer factors you ignore this. If you want to count negative integers as factors then any factor can have $-1$ or not, and you double the number. The remaining conundrum is the answer for zero. $\endgroup$ – Mark Bennet Sep 19 '19 at 20:52
  • $\begingroup$ And what about integers that 50 are divisible by. Would you use a similar strategy or would it change to a = 50 * m where m is an integer and a is the number that 50 can be divisible by? $\endgroup$ – Victor Luna Sep 19 '19 at 21:53
  • 1
    $\begingroup$ @VictorLuna If you mean multiples of $50$ so that $N=50M$ then for each factor $m$ of $M$ you will find a factor $50m$ of $N$. You factor out the $50$ and put it back in at the end. $\endgroup$ – Mark Bennet Sep 20 '19 at 7:11
  • $\begingroup$ Thank you for your explanation! However, for the purposes of what I need Andrews answer is more appropriate. $\endgroup$ – Victor Luna Sep 20 '19 at 18:49

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.