7
$\begingroup$

How many number of ordered pairs $(a, b)$ where $a,b, \in \{1, 2,\ldots,100\}$ such that $7^a + 7^b$ is divisible by 5?

I am not sure how to do this. Any ideas?


EDIT:

I noticed that if $a$ is of the form $4k+1$ then $b$ is of the form 4k'+3 (where k,k' \in \{ 0 \} $\cup \space\mathbb{N}$).

Similarly, another possible pair would be (4k,4k'+2),now we have to count the number of ordered pair of the form (4k,4k'+2),$(4k+1,4k'+3)$,$(4k'+2,4k)$,$(4k'+3,4k+1)$ in $\{1, 2,\cdots,100\}$. However,I haven't figured out (yet) how to do this?

  • 0
    @David Bevan:On second comment:That's$a$interesting information piece of information.Thanks! :)2011-09-27

6 Answers 6

12

$7^a+7^b\equiv 2^a+2^b\pmod{5}$. Since $2$ generates the multiplicative group of integers modulo $5$, then for each $a$ there is a $b\in \{1,2,3,4\}$ such that $2^b\equiv -2^a\pmod{5}$. Now notice that b\equiv b'\pmod{4} if and only if 2^b\equiv 2^{b'}\pmod{5}.

  • 0
    Thanks Arturo,I figured it out the answer is $4 \times (25 \times 25)$.2011-09-27
2

Suppose $a < b$. Then you want the number of $(a,b)$ such that $5$ divides $ 7^a(1 + 7^{b-a})$, or equivalently such that $5$ divides $1 + 7^{b-a}$. This is the same as saying $7^{b-a} \equiv -1 \pmod 5$.

Note that $7^2 \equiv -1 \pmod 5$, and more generally that for $i = 1,2,3,4$ that $7^i \equiv 2, -1, -2 , 1$ respectively modulo $5$. So $7^i$ cycles mod $5$ with period 4. So you are looking for the $(a,b)$ such that $b-a \equiv 2 \pmod 4$. Count those up and you're done.

  • 0
    Well, technically since $b - a \equiv a - b \equiv 2 \pmod 4$ you don't even have to do that.2011-09-27
2

We can factor like so. $7^a+7^b=7^b(7^{a-b}+1)$. 5 can't factor the $7^b$ part since its only factors are 7's, b being an integer, so the 5 will have to divide $7^{a-b}+1$. From what we know about divisibility rules, we then know that $7^{a-b}+1$ will have 0 or 5 as the ones digit if 5 divides it. Therefore, $7^{a-b}$ must have 9 or 4 as the ones digit.

Looking quickly at the powers of 7, they are 7, 49, 343, 2401, 16807, 117649,...Due to the nature of multiplication, the ones digits of the powers of seven will then repeat with the pattern 7, 9, 3, 1,... Hence $7^a+7^b$ will be divisible by 5 when the ones digits of $7^{a-b}$ is 9. Looking at the pattern of ones digits, we see that this occurs when $b-a=2+4k$, $k\in Z$; $a,b\in \{1,2,3,...,100\}$. So you just need to figure out how many a,b combinations satisfy that.

  • 0
    Th$a$nks for $p$osting the only specific answer I could really comprehend :)2011-09-27
1

HINT $\ $ Put $\rm\:N = \{1,2,\ldots,100\}\:.\:$ Let $\rm\:S \subset N^2\:$ be the solution set. Let $\rm\:f\:(a,b) = (a,b+1)\:.\:$ Show that $\rm\:N^2 =\: S\cup f\:(S)\cup f^{\:2}(S)\cup f^{\:3}(S)\:$ is a partition into equal-size parts, so $\rm\:|S| =\: \ldots$

Note: in the definition of $\rm\:f\:,\:$ the increment $\rm\:b+1\:$ is interpreted $\rm\:mod\ 100\:,\:$ so $\rm\:100 + 1 \to 1\:.$

0

I've seen you got answers that are specific to the problem at hand, but keep in mind that, when all else fails, there's always the good ole power of brute force. It won't help you during exams, more importantly it won't explain the reason behind the result, but it's otherwise there.

You can apply it here because we're talking about relatively few items; you can otherwise apply it to a smaller subset of data to corroborate your thought processes with supporting data, or to just get the right answer for doublechecking purposes.

In Python:

pairs = [(i,j) for i in range(1,101) # range(a,b) => [a, a+1, ..., b-1] :/                for j in range(1,101)                if (7**i + 7**j) % 5 == 0] print(len(pairs)) 

This gives 2,500 and runs in a blink of an eye.

  • 1
    @FoolForMath meh, it's food for thought. Just because you're not looking for a solution with computers doesn't mean you can't use a computer to help get your solution. Besides, SE is not just about helping _you._2011-09-27
0

$7^a=2^a(mod 5)$

$7^b=2^b(mod 5)$

But $2^a+2^b$=0(mod5)

$2^x=2,3 or 4mod(5)$

Therefore, if $2^a=y(mod5)$, $2^b=5-y(mod5)$

$2^a=2(mod3)$ and $2^b=3(mod5)$

And therefore, $a=(1,5,9,13..97)$ and $b=(3,7,11,..99)$ (You gotta observe the cyclycity) :)