3

Let $A = 1+5+5^2+\dots+5^{99}$, then $A$ is:

  1. A prime number
  2. not divisible by 3
  3. divisible by 13
  4. divisible by 125

I know this is a sum of a Geometric Progression, so $ A = (5^{100}-1)/4$ but I cannot find $5^{100}$ So I thought of finding a pattern between the progression starting from 1. I get 1,6,31,131,... but cannot seem to be finding any pattern. May someone Help?

Daniel R
  • 3,199
Matt
  • 1,150
  • $5^{100}=25^{50}=(-1)^{50}=1$ modulo $13$. – symplectomorphic Jul 05 '16 at 06:12
  • what is modulo? – Matt Jul 05 '16 at 06:13
  • 3
    Do you really mean $1+5^2+\dots$, or is it $1+5+5^2+\cdots$? If it is the latter, you can deal with the choices easily. – André Nicolas Jul 05 '16 at 06:13
  • $$5\equiv-1\pmod3\implies5^{100}\equiv(-1)^{100}$$

    So, $3|(5^{100}-1)$

    As $(3,4)=1,3$ will divide $\dfrac{5^{100}-1}{5-1}$

     – lab bhattacharjee Jul 05 '16 at 06:14
  • what is meaning of congruency sign and mod can you explain it without using them or perhaps provide a link where they are explained. – Matt Jul 05 '16 at 06:18
  • @RaghavSingal https://en.wikipedia.org/wiki/Modular_arithmetic –  Jul 05 '16 at 06:18
  • @RaghavSingal: just read Wikipedia. – symplectomorphic Jul 05 '16 at 06:18
  • Yeah.. do $5^{100}=25^{50} = (213 - 1)^{50} = 2^{50}13^{50} - 502^{49}13^{49} + ...... + {50 \choose 2}2^213^2 - 50213 + 1$. So $5^{100} - 1 = 2^{50}13^{50} - 502^{49}13^{49} + ...... + {50 \choose 2}2^213^2 - 50213$ which is divisible by 13. Learn modulo arithmatic. It's the arithmetic of remainders. That way you don't have to deal with all that $2^{50}13^{50} - 502^{49}13^{49} + ...... + {50 \choose 2}2^213^2 - 50213$ shit. You can get right to the important stuff $5^{100} \equiv 1 \mod 13$ which means $5^{100}$ divided by $13$ has remainder $1$. – fleablood Jul 05 '16 at 06:33
  • @fleablood thank you for providing an alternative which I can understand it helped! Also, I will definitely study modulo arithmetic. – Matt Jul 05 '16 at 10:26
  • You are welcome. Modulo arithmetic is fairly intuitive at first (if a is 1 more than a perfect multiple of 7 and b is 2 more than a perfect multiple of 7 then a+b; ab; (a+b)^3 will be 1+2, 12; (1+2)^3 etc more than a perfect multiples of 7) but it becomes a great tool for solving systems of equations. (what are the last 4 digits of $2037^{13452}$? Surprisingly that's easy to solve!) However comments like "Oh, just learn a new branch of math you've never heard of" are ... off-putting. – fleablood Jul 05 '16 at 16:33
  • Point is... with $5^2 = 213 - 1$ we are only interested in what happens to the "remainder" -1. The (213) no matter how manipulated (and with the binomial theory it gets very manipulated) it's always a multiple of 13 and we still only care about the remainder. Modulo arithmetic allows us a vocabular to talk about only the remainders. – fleablood Jul 05 '16 at 16:36

2 Answers2

6

I will assume that you mean $1+5+5^2+\cdots +5^{99}$. Let's deal with the choices one at a time.

Of course 4.) is false, all the terms except one are multiples of $5$. So the sum cannot be a multiple of $5$.

1.) is clearly false, we have an even number of odd numbers. The sum is therefore even, and thus not prime.

2.) Group in groups of $2$. Note that $1+5$ is a multiple of $3$, and so is $5^2+5^3$, which is $5^2(1+5)$. The same is true of $5^4+5^5=5^4(1+5)$, and so on. So our whole sum is a multiple of $3$.

3.) Note that $1+5+5^2+5^3$ is a multiple of $13$, and therefore so is $5^4+5^5+5^6+5^7$ and so on. (We are grouping in groups of $4$.)

André Nicolas
  • 507,029
  • Who naturally spots that $1+5+5^2+5^3$ is a multiple of 13? I have to assume the author of the problem had modular arithmetic in mind. – symplectomorphic Jul 05 '16 at 06:36
  • The author did. But he rose to the challenge to come up with an answer for the OP which didn't use it. – fleablood Jul 05 '16 at 06:39
  • 1
    Not too hard to note $1 + 5 + 5^2 + 5^3 = (1 + 5^2) + 5(1+5^2) = 26*6$. – fleablood Jul 05 '16 at 06:40
  • @symplectomorphic: From a comment, it looks as if OP may not be familiar with modular arithmetic. – André Nicolas Jul 05 '16 at 06:40
  • @fleablood: yes, duh, it is not hard to check but not something one would go looking for. I don't see how that method will help the OP solve other problems. – symplectomorphic Jul 05 '16 at 06:42
  • @symplectomorphic: I certainly agree that it is important that OP become familiar with modular arithmetic, and your answer will help to motivate that. – André Nicolas Jul 05 '16 at 06:44
  • It'd be useful and easy for the OP to learn i) $a \equiv b \mod c$ means $a - b$ is divisible by $c$. ii) if $a \equiv b \mod c$ then $na \equiv nb \mod c$ (because $na - nb$ is divisible by $c$. And iii) if $a \equiv b \mod c$ then $a^k = b^k \mod c$. Knowing that $25^{50}\equiv (-1)^50 \equiv 1 \mod 13 \implies $5^{100} - 1 $ is divisible by 13 will be easy to grasp. Once the OP gets used to it. – fleablood Jul 05 '16 at 06:46
  • Mmmm. modular arithmetic is easier but ... I think recognizing 1+a + a^2 +... will have such mini factors can be useful. – fleablood Jul 05 '16 at 06:51
  • I'm always amazed how you manage to solve all these problems in no time ! – Saikat Jul 05 '16 at 09:53
  • Thank you for providing a simple solution! It has made the problem very easy! It helped! – Matt Jul 05 '16 at 10:28
  • @RaghavSingal: You are welcome. – André Nicolas Jul 05 '16 at 12:35
4

Since the question concerns divisibility, consider reducing modulo $3$, $13$, etc.

In particular, note

$$5^{100}\equiv(-1)^{100}\equiv 1 \mod 3$$

and

$$5^{100}\equiv 25^{50}\equiv (-1)^{50}\equiv 1\mod 13$$

What does this tell you about the divisibility of $\frac{1}{4}(5^{100}-1)$ by $3$ and $13$?

symplectomorphic
  • 18,604