Checking the result fast
Divisibility by 5.
A number is divisible by 5 iff it ends with either 5 or 0. So you know right away that 123·345=42434 is wrong. It's a different question how to get the right answer (42435).
Use divisibility criteria.
As above, divisibility criteria are useful in establishing whether a result is wrong. Note that this way you never may be sure whether the result is right. The following criteria is available:
Divisibility by 3
Divisibility by 9
Divisibility by 7
Divisibility by 11
A number is divisible by 4 iff its 2-digit tail is divisible by 4. For example, 12345 is not divisible by 4 since 45 is not. However, 12348 is divisible by 4 since 48 is.
A number is divisible by 8 iff its 3-digit tail is divisible by 8. For example, 12345 is not divisible by 8 since 345 is not. However, 12344 is divisible by 8 since 344 is. Indeed 344=320+24, where both operands are divisible by 8.
A number is divisible by 25 if it ends with one of the four: 00, 25, 50, 75. Therefore 234465 is not divisible by 25.
The is a general way of deriving divisibility criteria for numbers such as 7, 11, 13, and other.
Use rude bounds.
127·345=27455 is clearly wrong because 127>100 while 345>300. Therefore, it must be that 127·345>100·300=30000.
220=524288 is clearly wrong because 220=(210)2=10242>10002=1000000. Actually 524288=219.
A practical application.
Use digital roots.
Digital root of an integer is, by definition, the sum of its digits computed recursively until only one digit remains. Thus to compute the digital root of 33572, we calculate first 3 + 3 + 5 + 7 + 2 = 20. The digitl root of 33572 is then 2 = 2 + 0.
The important fact about digital roots is that the digital root of the product of integers equals the product of their digital roots (downsized to a digital root if necessary.)
348·11 = 3828. The digital roots of 348, 11, and 3828 are respectively 6, 2, and 3. Take the product of 6 and 2: 6·2 = 12 with the digital root equal to 1 + 2 = 3, which is exactly the digital root of 3828.
Consider an integer a
a = an10n + an-110n-1 +...+ a1101 + a0
Criteria of divisibility by 9
a is divisible by 9 if and only if the sum of the digits an + an-1 + ... + a1 + a0 is divisible by 9.
Criteria of divisibility by 11
a is divisible by 11 if and only if the alternating sum of the digits (-1)nan + (-1)n-1an-1 + ... -a1 + a0 is divisible by 11.
In what follows I shall be using representation of a number in various base systems. In the decimal (base 10) system a number a is written as
a = (a)10 = an10n + an-110n-1 + ... + a1101 + a0
Generally speaking, for an integer base b the same number a will be written as
a = (a)b = ckbk + ck-1bk-1 + ... + c1b1 + c0
Notation (a)b is meant to underscore the base in which a is expanded. The most customary is the decimal system. But, say, the French still use remnants of the system in base 20. With the advent of computers the binary (base 2) and hexadecimal (base 16) have been thrust into prominence. The octal system (base 8) is very useful in handling lengthy binary representations.
Conversion between different bases is a good exercise that helps test your understanding of relevant techniques.
Theorem
Let b be an integer. Then an integer a
is divisible by (b-1) if and only if the sum of digits in its expansion (a)b is divisible by (b-1)
is divisible by (b+1) if and only if the alternating sum of digits in its expansion (a)b is divisible by (b+1)
Proof
The proof is based on Modulo Arithmetic. Thus we have b-1=0 (mod (b-1)) which implies b=1 (mod (b-1)). Therefore, for every i>0, bi = 1 (mod(b-1)). Multiplying this by ci and summing up for i=0,1, ..., k we get the first assertion.
Similarly, b+1=0 (mod (b+1)) hence b=-1 (mod (b+1)). Therefore, for i>0, bi = (-1)i (mod(b+1)). Multiplying this by ci and summing up for i=0,1, ..., k we get the second assertion.
Example 1
Let a=164. Is it divisible by 4? On the one hand, 164=125+25+2·5+4=(1124)5. The sum of digits is 1+1+2+4=8 and is divisible by 4. Therefore 164 is divisible by 4.
On the other hand, 164=2·81+0·27+0·9+0·3+2=(20002)3. The alternating sum of digits is 2-0+0-0+2=4 and is divisible by 4. Therefore, again, 164 is divisible by 4.
For divisibility by 7 there are two criteria:
a = (a)6 = ck6k+ck-16k-1+...+c161+c0 is divisible by 7 iff the alternating sum of digits (-1)kck+(-1)k-1ck-1+...+c0 is divisible by 7.
a = (a)8=ck8k+ck-18k-1+...+c181+c0 is divisible by 7 iff the sum of digits ck+ck-1+...+c0 is divisible by 7.
Example 2
512=83. Therefore (512)10=(1000)8. This implies that divided by 7 the remainder will be 1. Then, for example, 511 is divisible by 7.
1296=64. Therefore (1296)10=(10000)6. From here (1296+6)10=(10010)6. Its alternating sum of digits is 1-0+0-1+0=0. As a result, 1302 is divisible by
Problem
5109094x171709440000 = 21!, find x.
Solution
I can immediately think of a couple of question:
What is so special (if, of course, anything at all) about the 8th digit from the left? Can I hide another digit and have a meaningful problem?
What is so special about the number 21? If I compute the factorial of another number, say 10, would I be able to retrieve a hidden digit?
With regard to the first question, all digits look the same to me except for the trailing zeros. Zeros at the end of a number indicate the number of factors of 10 this number has. Let pursue this. Where do these factors of 10 come from? The number being a factorial, it's the product
21! = 1·2·3·4·5·...·19·20·21.
Then there are two factors (10 and 20) that contribute zeros to the result and another two (5 and 15) that combine with other even factors (of which there is a plenty) to add another two 0s. At this point, we began utilizing the fact that the given number is known to have certain factors. However, returning to the question asked, I can't think of a way in which other factors of 21! have affected the 8th digit.
As far as my current understanding of the problem goes, there is nothing special about the 8th digit. I also begin suspecting that the choice of 21 in the formulation of the problem is not very important. Indeed it would not be important if the question was to count the number of trailing 0s.
The important thing is that the number is presented as a product of several factors. This is actually the only piece of information that could be gathered from the original formulation. What do I know about factors? They are divisors of a product. Yes, indeed, I have already used properties of multiples of 5 and 10, right? Do I know of other rules concerning division of a number by other numbers? Actually, in school, we do not study a lot about numbers and their features. The study of Arithmetic concentrates on addition and other operations, on the table of multiplication - nothing very generic. And next we plunged into Algebra where numbers have hardly been mentioned at all. Is it also your recollection? (An aside: this is why I disagree with the dictionary definitions of Mathematics as a study of numbers. There is nothing in our education that remotely suggests any study of numbers as such.)
I am lucky, however, to remember one property of numbers divisible by 3 and 9.
A number is divisible by 3 (or 9) iff the sum of its digits is divisible by 3 (or 9).
I start feeling excited. The statement above does not say anything specific about the number of digits or their position. This jibes well with the hunch that selection of the 8th digit was arbitrary. But to apply this statement we have to establish whether the number is divisible by 3 (or 9). It's easy to check that all factorials starting with 3! are divisible by 3 whereas, starting with 6!, all factorials are divisible by 9. Therefore, 21! is divisible by 9. Can we use this?
The sum of digits of 21!, as it's presented in the problem, is (61+x). This is divisible by 9 iff x=2. This must be the missing digit! Division by 3 could also be used for the 8th digit. However, it would fail for the first one.
Summing up:
Given n!, n>5, with one digit removed.Then it is possible to recover the digit.
Please do not jump to conclusions. Remember the problem we just had trying to recover the first digit? May there arise other complications? Sure. There is no way (or, rather, we have not established a way) to tell 0 from 9.
Posts
