Number of consecutive zeros at the end of $11^{100} - 1$.

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.

• 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 – Dr. belisarius Nov 6 '12 at 15:46
• @BrianM.Scott - It should be 3 zeros, not 4. Thanks. – Legendre Nov 7 '12 at 1:42

$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.

• 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
• @did: I like getting good mileage out of elementary tools. :-) – Brian M. Scott Nov 6 '12 at 18:43

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.

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:= 11^100 - 1

Out=
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

• 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
• PHP : 137806123398222667397341263915494910257435279372577087851636691596450337180412259312481380325319352778752 !! – Ring Ø Jan 28 '16 at 9:08

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)

]

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$

• 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