Divisibility of a large number with $72$

Question

When trying to find whether some very large number is divisible by for example $72$ we can just check if that number is divisible by both $8$ and $9$. Can someone explain why that works?

Answer 1

This is due to the fact that $\mbox{gcd}(8,9)=1$. Therefore if $8|N$ and $9|N$, then $N=8M$ and since $\mbox{gcd}(8,9)=1$ then $9|M$. Finally $72|N$.

Here I used the fact that if $a|bc$ and $\mbox{gcd}(a,b)=1$ then $a|c$.

This fact can be seen as a consequence of Bezout identity: since $\mbox{gcd}(a,b)=1$, there exists $u$ and $v$ such that $au+bv=1$. Consequently $acu+bcv=c$. And $a|acu$ (immediate), $a|bcv$ (by hypothesis) hence $a|acu+bcv=c$.

Answer 2

8 can be expressed as $2^3$ and 9 as $3^2$ - they share no prime factors. So if a number is divisible by 8, when broken down into prime factors we should see $2^3$ at some point and if it is divisible by 9, we'll see $3^2$ in the prime decomposition. If a number is divisible by both 8 and 9, we'll see both sets of these prime factors in the decomposition which ultimately can be multiplied together to show that the number is divisible by 72.