Suppose some number $n \in \mathbb{N}$ is divisible by $144$.

$$\implies \frac{n}{144}=k, \space \space \space k \in \mathbb{Z} \\ \iff \frac{n}{36\cdot4}=k \iff \frac{n}{36}=4k$$

Since any whole number times a whole number is still a whole number, it follows that $n$ must also be divisible by $36$. However, what I think I have just shown is:

$$\text{A number }n \space \text{is divisble by} \space 144 \implies n \space \text{is divisible by} \space 36 \space (1)$$

Is that the same as saying: $$\text{For a number to be divisible by 144 it has to be divisible by 36} \space (2)$$

In other words, are statements (1) and (2) equivalent?

  • 15
    Yes, absolutely. – Bernard Nov 11 at 20:47
  • 1
    Pedantically, the first sentence could have a different meaning if it somehow isn't obvious from context that $n$ is universally quantified. But in general they're the same. – Ian Nov 11 at 20:49
  • You mean this sentence "Since any whole number times a whole number is still a whole number, it follows that n must also be divisible by 36. ",right? – Nullspace Nov 11 at 20:52
  • In general, if $a$ is divisible by $b$, and $b$ is divisible by $c$, then $a$ is divisible by $c$. – AlexanderJ93 Nov 12 at 0:14
up vote 46 down vote accepted

Yes, it's the same. $A\implies B$ is equivalent to "if we have $A$, we must have $B$".

And your proof looks fine. Good job.

If I were to offer some constructive criticism, it would be of the general kind: In number theory, even though we call the property "divisible", we usually avoid division whenever possible. Of the four basic arithmetic operations it is the only one which makes integers into non-integers. And number theory is all about integers.

Therefore, "$n$ is divisible by $144$", or "$144$ divides $n$" as it's also called, is defined a bit backwards:

There is an integer $k$ such that $n=144k$

(This is defined for any number in place of $144$, except $0$.)

Using that definition, your proof becomes something like this:

If $n$ is divisible by $144$, then there is an integer $k$ such that $n=144k$. This gives $$ n=144k=(36\cdot4)k=36(4k) $$ Since $4k$ is an integer, this means $n$ is also divisible by $36$.

  • 2
    Programmers might may say mod() = 0 rather than "divides", if n modulus 144 is zero then n modulus 36 is zero etc. Non zero values are integers. – mckenzm Nov 12 at 0:30
  • Every definition I ever see of divisibility specifically excludes $0$ as a potential divisor (checked a few abstract algebra books here, etc.). If that were not the case, it would wind up violating the Division Algorithm, leave greatest common divisors not well-defined, etc. – Daniel R. Collins Nov 13 at 5:15

Yes that's correct or simply note that

$$n=144\cdot k= 36\cdot (4\cdot k)$$

but $n=36$ is not divisible by $144$.

The $\implies$ symbol is defined as follows:

If $p \implies q$ then if $p$ is true, then $q$ must also be true. So when you say $144 \mid n \implies 36 \mid n$ it's the same thing as saying that if $144 \mid n$, then it must also be true that $36 \mid n$.

There are often multiple approaches to proofs. Is usually good to be familiar with multiple techniques.

You have a very good approach. Parsimonious and references only the particular entities at hand.

Some times, for the sake of illustrating the use of additional concepts, you might want to deviate from parsimony.

In that spirit, here's an additional proof.

According to The Fundamental Theorem of Arithmetic, if something is divisible by 144, then it is divisible by at least the same primes raised to the powers you need to yield 144. In other words, $144=2^43^2$. For something to be divisible by 144, the primes 2 and 3 must appear in its prime factorization. The powers of 2 and 3 must be at least 4 and 2, respectively. Now $36=2^23^2$. So any number who's prime factorization incluedes the primes 2 and 3, and has them raised at least to the power of 2, then it is also divisible by 36. If something is divisible by 144, we are guaranteed that 2 and 3 appear in its prime factorization. We area also guaranteed that the exponents on 2 and 3 are 4 and 2 respectively. So divisibility by 144 implies divisibility by 36 since the exponents satisfy the established criteria.

The prime factorization of 144 is 2 * 2 * 2 * 2 * 3 * 3. The prime factorization of 36 is 2 * 2 * 3 * 3.

If X is divisible by Y, then X's prime factorization contains all of the factors in Y's prime factorization.

Since 144's prime factorization contains all of the factors in 36's prime factorization, 144 is divisible by 36.

The prime factorization of any number that is divisible by 144 contains all of the prime factors of 144, which contains all of the prime factors of 36. Hence any number that is divisible by 144 has a prime factorization that contains all the prime factors of 36, and therefore is divisible by 36.

If $n$ is a multiple of $144$, it must automatically be a multiple of any divisor $d$ of $144$. The prime factorization of $144$ is $(2^4)(3^2)$, and so $36 = (2^2)(3^2)$ must be a divisor of $144$ and hence of $n$.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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