# 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$?

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?

-
What you write is not quite correct: when you say "if $a$ is of the form $4k+1$ then $b$ is of the form $4k+3$", you are using $k$ to play two different roles. The plain reading would imply that you have the same $k$ for both $a$ and $b$, and this is not accurate. You are also missing the possibility that $a$ is of the form $4k+2$, or that it is of the form $4k+3$, since you are required to count ordered pairs, not sets. –  Arturo Magidin Sep 27 '11 at 3:56
@Arturo Magidin:Yes you are right,is it correct now? –  Quixotic Sep 27 '11 at 4:06
$\{0\} \cup \mathbb{N}$? Since when does $\mathbb{N}$ start with 1?! –  badp Sep 27 '11 at 8:04
@badp:Since I was taught in high school and before that when my teacher was and before that ... and seems like wikepedia is with me on this. –  Quixotic Sep 27 '11 at 9:33
However,I have seen in some papers that researchers are using $\mathbb{N}$ which includes $0$ but well they are (all) defining it first in the beginning itself :) –  Quixotic Sep 27 '11 at 9:37

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

-
Thanks for your answer but as abstract algebra is still illegible to me :/,hence I couldn't understand your answer (properly).Anyways,I have edited the question.:) –  Quixotic Sep 27 '11 at 3:44
@FoolForMath: "$2$ generates the multiplicative group of integers modulo $5$" just means that given any integer $m$ relatively prime to $5$, you can find an $r$ such that $2^r\equiv m\pmod{5}$, that is, such that $5$ divides $2^r-m$. It amounts to your observation: when $a$ is of the form $4k$, then $b$ is of the form $4r+2$; if $a$ is of the form $4k+1$, then $b$ will be of the form $4r+3$; when $a$ is of the form $4k+2$, then $b$ will be of the form $4r$; and when $a$ is of the form $4k+3$, then $b$ is of the form $4r+1$. –  Arturo Magidin Sep 27 '11 at 3:53
@FoolForMath: So, for each possible value of $i$ ($i=0,1,2$ or $3$), figure out how many numbers in $\{1,2,\ldots,100\}$ are of the form $4k+i$. Then just select $a$ arbitrarily, and count the number of $b$s that can be "matched up" with $a$. –  Arturo Magidin Sep 27 '11 at 3:54
Thanks Arturo,I figured it out the answer is $4 \times (25 \times 25)$. –  Quixotic Sep 27 '11 at 7:04

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.

-
... after multiplying the count you get by $2$ and noting there are no solutions with $a=b$... –  Arturo Magidin Sep 27 '11 at 3:32
Well, technically since $b - a \equiv a - b \equiv 2 \pmod 4$ you don't even have to do that. –  Zarrax Sep 27 '11 at 3:52

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.

-
Thanks for posting the only specific answer I could really comprehend :) –  badp Sep 27 '11 at 8:27

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

-

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.

-
I haven't use algorithm or computer-science tags,ain't it tell something?And again how you know that I can't brute-force? :) –  Quixotic Sep 27 '11 at 9:25
@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. –  badp Sep 27 '11 at 10:01

$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) :)

-