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.

How many consecutive zeros are there at the end of $11^{100} - 1$?

Attempt

Trial and error on Wolfram Alpha shows using modulus shows that there are 4 zeros (edit: 3 zeros, not 4). Otherwise, I have no idea even where to start.

share|improve this question
    
Are you sure about the trial and error attempts? I get only three. –  Brian M. Scott Nov 6 '12 at 13:22
    
In Mathematica Min[IntegerExponent[11^100 - 1, 5], IntegerExponent[11^100 - 1, 2]] returns 3 –  belisarius Nov 6 '12 at 15:46
    
@BrianM.Scott - It should be 3 zeros, not 4. Thanks. –  Legendre Nov 7 '12 at 1:42

5 Answers 5

up vote 53 down vote accepted

$11^{100}=(10+1)^{100}=\sum_{k=0}^{100}\binom{100}k10^k=1+100\cdot10+4950\cdot100+161700\cdot1000+\ldots~$. Thus, $11^{100}-1=1000+495000+161700000+\ldots=162196000+\ldots~$. The remaining terms all have factors of $10^k$ for some $k\ge4$ and therefore have at least four zeroes. Thus, $11^{100}-1$ ends with three zeroes.

share|improve this answer
    
Pfew... Finally! Reading all these other answers, I was wondering when somebody would decide to use good'old'fashioned binomial expansion. :-) –  Did Nov 6 '12 at 18:28
1  
@did: I like getting good mileage out of elementary tools. :-) –  Brian M. Scott Nov 6 '12 at 18:43
1  
Don't you need a "-1" in your concluding sentence? (I don't have enough rep to make such a small edit.) –  xan Nov 6 '12 at 19:15
    
@xan: I do indeed; thanks for catching that. –  Brian M. Scott Nov 6 '12 at 19:17
    
Nice answer, thanks! –  Legendre Nov 7 '12 at 1:41

Find the highest power of 2 in its factorization and find the highest power of 5 in its factorization. If you take the minimum of these two numbers, you will get the highest power of 10 in the factorization.

Now, to find these highest powers, as you have already mentioned, we use modulus.

$11 \equiv 1 \mod 2$ so that $11^{100} - 1 \equiv 1^{100} - 1 \equiv 0 \mod 2$

Thus, we know that it contains at least one 2.

$11 \equiv -1 \mod 4$ so that $11^{100} - 1 \equiv (-1)^{100} - 1 \equiv 0 \mod 4$

Thus, it contains at least $2^2$.

$11 \equiv 3 \mod 8$ so that $11^2 \equiv 1 \mod 8$ so that $11^{100} - 1 \equiv 1^{50} - 1 \equiv 0 \mod 8$

Thus, we have $2^3$.

$11 \equiv -5 \mod 16$ so that $11^2 \equiv 9 \mod 16$ so that $11^4 \equiv 1 \mod 16$ so that $11^{100} - 1 \equiv 1^{25} - 1 \equiv 0 \mod 16$.

Thus, we have $2^4$. We definitely do not have $2^5$ as

$11^2 \equiv -7 \mod 32$ so that $11^4 \equiv 17 \mod 32$ so that $11^8 \equiv 1 \mod 32$ so that $11^{100} - 1 \equiv 11^4 \cdot 11^{96} - 1 \equiv 17 \cdot 1 - 1 \mod 32 \equiv 16 \mod 32$.

So, your answer is at most 4. Now, do the same for 5.

$11 \equiv 1 \mod 5$ so that $11^{100} - 1 \equiv 1^{100} - 1 \equiv 0 \mod 5$.

Thus, there is at least one 5. Keep going... the calculations will get more difficult as your powers get higher. Or, you could do the same thing directly with 10. But, the numbers would be bigger much faster and thus the calculations might be more difficult.

share|improve this answer

With something so small, if you have access to a computer, you just calculate it. This provides no insight into how to solve a much larger problem, of course, but it's absurdly fast for a problem of this scale.

Mathematica:

In[0]:= 11^100 - 1

Out[0]= 
1378061233982227018411833717208963677626433120003846643314647\
75521549852095523076769401159497458526446000

Python:

>>> pow(11,100)-1
1378061233982227018411833717208963677626433120003846643314647
75521549852095523076769401159497458526446000L

Scala:

scala> (BigInt(11) pow 100) - 1
res1: scala.math.BigInt = 
1378061233982227018411833717208963677626433120003846643314647
75521549852095523076769401159497458526446000

scala> ((BigInt(11) pow 100) - 1).toString.
       reverse.takeWhile(_=='0').length
res2: Int = 3
share|improve this answer
    
Some people around does not like computations... That's a shame. –  Lierre Nov 6 '12 at 19:29
    
Indeed. It's good to know when a problem is trivially computable even if you can't do it in your head. Maybe you need to know how to generalize, in which case it's unhelpful. But maybe you just need that answer, in which case it's perhaps better to spend 10 seconds typing than 5 minutes thinking about it and calculating initial terms by hand (or doing modulus arithmetic or whatever). –  Rex Kerr Nov 6 '12 at 20:57

With the help of Lifting the Exponent Lemma:

$v_2(11^{100}-1)=v_2(11-1)+v_2(100)=5$

$v_5(11^{100}-1)=v_5(11-1)+v_5(100)=3$

Answer $=3$

share|improve this answer
5  
At least make sure you apply this unknown lemma correctly then: $$v_2(11^{100} - 1) = v_2(11 - 1) + v_2(11 + 1) + v_2(100) - 1 = 1 + 2 + 2 - 1 = 4.$$ –  TMM Nov 6 '12 at 18:18

We know

if $$ord_{p^s}a=d, ord_{p^{s+1}}a=d\space or \space pd--->(1)$$ (Proof)

and if $$ord_{(p^s)}(a)=d, ord_{p^{(s+1)}}(a)=pd,\space then \space ord_{p^{(s+2)}}(a)=p^2d--->(2)$$(Proof below)

where $p$ is any odd prime and $s$ is a positive integer .

As $11\equiv1\pmod 5\implies ord_511=1$

But $11\not\equiv1\pmod {25}\implies ord_{25}(11)\ne1\implies ord_{25}(11)=1\cdot 5=5$(Using (1))

So, using (2), $ord_{125}(11)=5\cdot 5=25$ which divides $100\implies 125\mid(11^{100}-1)$

Again using (2), $ord_{625}(11)=25\cdot 5=125$ which does not divide $100\implies 625\not\mid(11^{100}-1)$

So, $5^3\mid\mid (11^{100}-1)$

Observe that $(11^2-1)\mid (11^{100}-1)$ and $(11^2-1)=120$ is divisible by $8=2^3$ and we don't need to test for the higher powers of $2$ We doe snot need to test for the higher powers of $2,$ as even if they exist, they don't have any $5$ to be associated.

So, $10^3\mid\mid (11^{100}-1)$

[

Proof of (2):

Let $ord_{(p^s)}(a)=d, ord_{p^{(s+1)}}(a)=pd$

So, $a^d=1+cp^s$ for some positive intger $c$

If $p\mid c,a^d\equiv 1\pmod{p^{(s+1)}}\implies ord_{p^{(s+1)}}(a)\mid d$ which is impossible as $ord_{p^{(s+1)}}(a)=pd$

So, $p\not\mid c$ i.e.,$(c,p)=1$

Now, $a^{pd}=(a^d)^p=(1+cp^s)^p=1+\binom p 1cp^s+\binom p 2(cp^s)^2+\cdots+(cp^s)^p$ $\equiv 1+cp^{s+1}\pmod{p^{(s+1)}}$ if $1+2s\ge s+2$ i.e., if $s\ge 1$

So, $a^{pd}\equiv 1+cp^{s+1}\pmod{p^{(s+1)}}\not\equiv1\pmod{p^{(s+1)}}$ as $p\not\mid c$

$\implies ord_{p^{(s+2)}}\ne pd\implies ord_{p^{(s+2)}}= p(pd)$ using(1)

]

share|improve this answer

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.