More on Divisibility Proofs Name:A&S100, Section 00216 October 2002I think I have found a way to make the divisibilty tests for powers of 2 (i.e. 2, 4, 8, 16, 32, etc.)a bit easier. (Yeah!) Before we get to that, let’s look at a few examples. Consider the number123, 456. We can break this number as follows:123, 456 = 123, 000 + 456= 123 × 1000 + 456= 123 × 103+ 456Or, if it suits our purposes better, we could break it up as123, 456 = 120, 000 + 3, 456= 12 × 10, 000 + 3, 456= 12 × 104+ 3, 456or even as123, 456 = 123, 400 + 56= 1234 × 100 + 56= 1234 × 102+ 56In fact, we can split this number anywhere we like in a similar manner. In the general case, we haveam· · · a4a3a2a1a0= am· · · a4a3a2a1× 10 + a0oram· · · a4a3a2a1a0= am· · · a4a3a2× 102+ a1a0oram· · · a4a3a2a1a0= am· · · a4a3× 103+ a2a1a0oram· · · a4a3a2a1a0= am· · · a4× 104+ a3a2a1a0or, or, or, . . . Basically, we can keep this up until we run out of digits. With these general numberswe will not run out of digits. If you need an a5, put it in. If you need an a7, write the numberas am· · · a7a6a5a4a3a2a1a0. We now have lots of different ways to write our number. We just needto figure out which one is most useful in the proof. In the case of proofs for divisibility by 2kithappens to be the one that contains 10k. Let’s take a look.11. Prove that a positive integer is divisible by 8 if and only if the number formed by the lastthree digits of the integer are divisible by 8.Note: 8 = 23so we are going to break the number up at 103.PROOF: Let N = am· · · a3a2a1a0be a positive integer. N is divisible by 8 if and onlyifN mod 8 = 0 if and only ifam· · · a3a2a1a0mod 8 = 0 if and only if(am· · · a3× 103+ a2a1a0) mod 8 = 0.Since 103mod 8 = 0, it now follows that N mod 8 = 0 if and only if(am· · · a3× 0 + a2a1a0) mod 8 = 0 if and only ifa2a1a0mod 8 = 0 if and only ifthe number formed by the last three digits of N is divisible by 8. 2. Prove that a positive integer is divisible by 32 if and only if the number formed by the lastfive digits of the integer are divisible by 32.Note: 32 = 25so we are going to break the number up at 105.PROOF: Let N = am· · · a5a4a3a2a1a0be a positive integer. N is divisible by 32 if and only ifN mod 32 = 0 if and only ifam· · · a5a4a3a2a1a0mod 32 = 0 if and only if(am· · · a5× 105+ a4a3a2a1a0) mod 32 = 0.Since 105mod 32 = 0, it now follows that N mod 32 = 0 if and only if(am· · · a5× 0 + a4a3a2a1a0) mod 32 = 0 if and only ifa4a3a2a1a0mod 32 = 0 if and only ifthe number formed by the last five digits of N is divisible by 32. 23. Prove that a positive integer is divisible by 2 if and only if the last digit of the integer isdivisible by 2. (Or, said another way, the last digit is even.)Note: 2 = 21so we are going to break the number up at 101= 10.PROOF: Let N = am· · · a3a2a1a0be a positive integer. N is divisible by 2 if and onlyifN mod 2 = 0 if and only ifam· · · a3a2a1a0mod 2 = 0 if and only if(am· · · a3a2a1× 101+ a0) mod 2 = 0.Since 101mod 2 = 0, it now follows that N mod 2 = 0 if and only if(am· · · a3a2a1× 0 + a0) mod 2 = 0 if and only ifa0mod 2 = 0 if and only ifthe last digit of N is divisible by 2. While we are discussing divisibility proofs, we might as well work through a couple more of them.The divisibility tests that follow are for divisors which are NOT powers of 2 so we can always goback to our old friend the base 10 expansion. Before doing that though, check to see if the newway of writing numbers will make things easier. Sometimes, it is helpful and can make for a shorterproof, as in the proofs for the divisibility tests by 5 and by 10. However, the new way of writingnumbers does not appear to be helpful when trying to prove the divisibilty tests for 3 and 9 so wewill probably have to continue to use the base 10 expanision when doing the proofs of the divisibilitytests for 3 and 9. Sorry!31. Prove that a positive integer is divisible by 5 if and only if its last digit is a 5 or a 0.PROOF: Let N = am· · · a3a2a1a0be a positive integer. N is divisible by 5 if and onlyifN mod 5 = 0 if and only ifam· · · a3a2a1a0mod 5 = 0 if and only if(am· · · a3a2a1× 10 + a0) mod 5 = 0.Since 10 mod 5 = 0, it follows that N mod 5 = 0 if and only if(am· · · a3a2a1× 0 + a0) mod 5 = 0 if and only ifa0mod 5 = 0 if and only ifthe last digit of N is divisible by 5 if and only ifthe last digit of N is a 5 or a 0. 2. Prove that a positive integer is divisible by 10 if and only if its last digit is a 0.PROOF: Let N = am· · · a3a2a1a0be a positive integer. N is divisible by 10 if and onlyifN mod 10 = 0 if and only ifam· · · a3a2a1a0mod 10 = 0 if and only if(am· · · a3a2a1× 10 + a0) mod 10 = 0.Since 10 mod 10 = 0, it follows that N mod 10 = 0 if and only if(am· · · a3a2a1× 0 + a0) mod 10 = 0 if and only ifa0mod 10 = 0 if and only ifthe last digit of N is divisible by 10 if and only ifthe last digit of N is a 0. 43. Prove that a positive integer is divisible by 3 if and only if the sum of its digits is divisible by 3.PROOF: Let N = am· · · a3a2a1a0be a positive integer. N is divisible by 3 if and onlyifN mod 3 = 0 if and only ifam· · · a3a2a1a0mod 3 = 0 if and only if(am× 10m+ · · · + a3× 103+ a2× 102+ a1× 10 + a0) mod 3 = 0.Since 10 mod 3 = 1, it follows that N mod 3 = 0 if and only if(am× 1m+ · · · + a3× 13+ a2× 12+ a1× 1 + a0) mod 3 = 0 if and only if(am+ · · · + a3+ a2+ a1+ a0) mod 3 = 0 if and only ifthe sum of N ’s digits is divisible by 3. Hope this