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?
$\begingroup$ $\endgroup$
1 - 3$\begingroup$ Because $72=2^3\cdot 3^2$. $\endgroup$Dietrich Burde– Dietrich Burde2019-06-25 08:33:23 +00:00Commented Jun 25, 2019 at 8:33
Add a comment |
2 Answers
$\begingroup$ $\endgroup$
0 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$.
$\begingroup$ $\endgroup$
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.