Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am taking a math competition tomorrow, and I was confused on a practice problem.

Problem 10

A majority of the 30 students in Ms. Demeanor's class bought pencils at the school bookstore. Each of these students bought the same number of pencils, and this number was greater than 1. The cost of a pencil in cents was greater than the number of pencils each student bought, and the total cost of all the pencils was $17.71. What was the cost of a pencil in cents?

http://wiki.artofproblemsolving.com/index.php/2011_AMC_10A_Problems/Problem_10

On the solution link (above), I didn't understand how 1771 was immediately factored out. How can this be done?

share|improve this question
1  
It can be done using divisibility tests for prime numbers. It can't be divisible by: 2 since it's odd, 3 since the sum of its digits is not a multiple of three, 5 since it doesn't end with a 5 or a 0. The next prime is 7. Whether or not is the fastest way, I don't know. –  ᛥᛥᛥ Feb 4 at 2:34
    
The number is 1771, not 1171, by the way. :) –  ᛥᛥᛥ Feb 4 at 2:43
1  
You can test for divisibility by $7$, $11$, and $13$ by subtracting off multiples of $7 \cdot 11 \cdot 13 = 1001$. Thus $1771 - 1001 = 770$ is divisible by $11$. –  rghthndsd Feb 4 at 3:25
    
You should learn by heart the primes < 100, then it's pretty easy to factor any number less than $100^2 = 10000$. There are only 25 primes below 100 so you can prove the primality of any number up to 9999 with at most 25 divisions. –  Bakuriu Feb 4 at 8:30
add comment

7 Answers

up vote 6 down vote accepted

I worked this out by hand without looking at the possible answers; the factorization wasn't obvious to me, but you can narrow down the possible factors very quickly. We know that the number of students who bought pencils is between 16 and 30 inclusive (the class had 30 students, and the majority of them bought pencils). We also know that the final product is odd, so none of the factors can be even. So the possible values for $s$ are 17, 19, 21, 23, 25, 27, and 29

We can rule out several of these based on simple tests. 1771 isn't a multiple of 3 because its digits don't add up to a multiple of 3. And we know it's not a multiple of 5 because it doesn't end in 5 or 0. Ruling out multiples of 3 and 5 leaves 17, 19, 23, 29.

From there, trial and error quickly yields 23 as the only value that divides 1771 evenly; the result is 77, and that's obviously 11 * 7. Since the cost was greater than the number of pencils, that means that 23 students bought 7 pencils for 11 cents each.

See also several below answers that point out useful tests for divisibility by 11 that I was unaware of when I first wrote this answer! In this case, the difference of the sums of alternating digits would quickly have shown divisibility by 11: $1 - 7 + 7 - 1 \equiv 0 \pmod{11}$.


After some thought, it has occurred to me that there's a general principle behind these simple divisibility tests. I'm surprised no one has mentioned it; perhaps it seems too obvious, but it wasn't obvious to me at first, so I'll mention it here in case it helps anyone else.

A four digit number $abcd$ is equivalent to the expression $a\,10^3 + b\,10^2 + c\,10^1 + d\,10^0$. To find the remainder of a division by $n$, reduce the powers of ten by $n$, and multiply the results by the digits $a$, $b$, and so on. So for example, say $n = 3$.

$$10^3 \equiv 1 \pmod{3}$$ $$10^2 \equiv 1 \pmod{3}$$ $$10^1 \equiv 1 \pmod{3}$$ $$10^0 \equiv 1 \pmod{3}$$

So we have $abcd \equiv a 1 + b 1 + c 1 + d 1 \pmod{3}$.

Since the remainder of any power of 10 divided by 3 is 1, the equation works out to a simple digital sum.

This holds as well for $n=9$; so again, we have a simple digital sum. The same principle is also behind the rule for 11, but instead of being a simple sum, it's an alternating sum, because $10^x \equiv 1 \pmod{11}$ for odd $x$ and $10^x \equiv 10 \equiv -1 \pmod{11}$ for even $x$. (This is shown by a few answers below; you can convince yourself of this fact by noting that 11 * 9 = 99, 11 * 91 = 1001, 11 * 909 = 9999, 11 * 9091 = 100001, and so on.)

So we have a sequence of values $b^x \pmod{n}$ for a given $n$ and $b$, and $x = 0, 1, 2, 3...$. Call that a modular base. The modular bases for $b = 10$ and $n = 2, 3... 9, 11$ are as follows, showing values in reverse, so that they appear in the conventional order for written numbers:

$$2: ...0, 0, 0, 0, 0, 1$$ $$3: ...1, 1, 1, 1, 1, 1$$ $$4: ...0, 0, 0, 0, 2, 1$$ $$5: ...0, 0, 0, 0, 0, 1$$ $$6: ...4, 4, 4, 4, 4 ,1$$ $$7: ...5, 4, 6, 2, 3, 1$$ $$8: ...0, 0, 0, 4, 2, 1$$ $$9: ...1, 1, 1, 1, 1, 1$$ $$11: ...10, 1, 10, 1, 10, 1$$

The bases for 7 and 11 can also be represented in a different way

$$7: ...-2, -3, -1, 2, 3, 1$$ $$11: ...-1, 1, -1, 1, -1, 1$$

You can see here the origins of a number of common divisibility tests. In particular, this shows why you only have to look at the last digit for 2 and 5, and only at the last two digits for 4, and only at the last three digits for 8. Patterns similar to the pattern for 7 appear for larger primes.

share|improve this answer
3  
without calcuation you directly see that 11 divides 1771 –  user127.0.0.1 Feb 4 at 2:44
2  
You do perhaps :) I didn't. –  senderle Feb 4 at 2:45
1  
Division test for division by 11 is the alternating sum of the digits. 1-7+7-1=0 and 11 divides 0 so 11 divides 1771. –  Taemyr Feb 4 at 9:04
add comment

If you are familiar with divisibility by $11$, it is obvious that $1771$ is a multiple of $11$. If not, you just need to "see" that

$$1771=1111+660$$

and both $1111$ and $660$ are clearly multiples of $11$.

share|improve this answer
add comment

Hint $\,\ 11\mid 1771\ $ by $\rm\ {\rm mod}\ 11\!:\ abba\, =\, \overbrace{a\,10^3\!+\!b\,10^2\!+\!b\, 10\!+\!a}^{reduce\,\ \color{#c00}{10\,\equiv\, -1}\ \ }\, \equiv\, -a+b-b+a \equiv 0\,$

Note $\ \color{#c00}{x = -1}\,$ is a root of $\,c_0 + c_1 x + c_2 x^2 + \cdots + c_n x^n\,$ if $\,c_0\!-\!c_1\!+\!c_2\!-\!c_3\!+\cdots + (-1)^n c_n = 0.\,$ In particular this is true if the coefficient sequence has even length and is a palindrome. Thus evaluating such a palindromic polynomial at $\,x = b\,$ shows that an even length palindrome number in radix $\,b\,$ is divisible by $\,b+1,\,$ since $\,\color{#c00}{b\equiv -1}\pmod{b+1}.\,$ Above is the special case $\,b=10.$

share|improve this answer
add comment

The interesting thing about divisibilty by 11 is that you can do it by adding up alternate digits (modulo 11) and subtract this from the sum of the other alternative digits (modulo 11). If you get zero, then the number is divisible by 11.

So for 1771 you can add 1 to 7 (and get 8) ad subtract this from (7 + 1) (which is 8) and get zero. Therefore 1771 is divisible by 11.

This works because 11 is 10+1, where 10 is the number base we work in. Had it been hexadecimal, then you'd be able to add up each alternate hex digit and subtract from the sum of the remaining alternate digits, and if you get zero then your number would be divisible by 17 (which is 16(our number base) plus 1).

The thing about divisibility rules is that they work out the remainder you'd get if you did the division, but without doing the division itself.

share|improve this answer
add comment

Besides the comment of @Not Me, note that any number of the form $1nn1$ is divisible by $11$:

$1nn1 = 11\times 1(n-1)1$

where you view $n$ and $n-1$ as digits. This is simple to verify, and would seem to be very relevant to the problem.

share|improve this answer
    
Taking this one step further, it can be seen that any number of the form nmmn will be divisible by 11. It can be rewritten as 1001n + 110m which is (11 * 91n) + (11 * 10m) (brackets added for clarity only), or 11(91n + 10m) which is a multiple of 11. –  stealth_angoid Feb 5 at 9:49
add comment

For a number of this size it's feasible to do modular arithmetic calculations in one's head. Since $100 \pmod{7} \equiv 2$, $1000 \pmod{7} \equiv (10 \pmod{7})(100 \pmod{7}) \equiv 6 \pmod{7}$, so $1771 \pmod{7} \equiv (6 \pmod{7}) + (771 \pmod{7}) \equiv 0$.

share|improve this answer
add comment

Here is a completely different simple method of factoring this out, it is just coincidence [i.e. practice] that we can recognize these patterns:

$$1771=2500-729\,.$$ is a difference of two squares. This is a natural observation if you are familiar with the powers of $3$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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