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?

  • 1
    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.2011-09-27
  • 0
    @Arturo Magidin:Yes you are right,is it correct now?2011-09-27
  • 0
    $\{0\} \cup \mathbb{N}$? Since when does $\mathbb{N}$ start with 1?!2011-09-27
  • 0
    @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](http://en.wikipedia.org/wiki/Set_(mathematics)#Special_sets).2011-09-27
  • 0
    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 :)2011-09-27
  • 0
    Also from [wikipedia](http://en.wikipedia.org/wiki/Natural_number): There is no universal agreement about whether to include zero in the set of natural numbers: some define the natural numbers to be the positive integers {1, 2, 3, ...}, while for others the term designates the non-negative integers {0, 1, 2, 3, ...}. The former definition is the traditional one, with the latter definition first appearing in the 19th century.2011-09-27
  • 0
    To be unambiguous about whether zero is included or not, sometimes an index (or superscript) "0" is added in the former case, and a superscript "*" or subscript "1" is added in the latter case: $\mathbb{N}^0 = \mathbb{N}_0 = \{0, 1, 2, ...\}$; $\mathbb{N}^{*} = \mathbb{N}_1 = \{1, 2, ...\}$.2011-09-27
  • 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}$.

  • 1
    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.:)2011-09-27
  • 0
    @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$.2011-09-27
  • 0
    @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$.2011-09-27
  • 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
    ... after multiplying the count you get by $2$ and noting there are no solutions with $a=b$...2011-09-27
  • 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
    Thanks for posting 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.

  • 0
    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? :)2011-09-27
  • 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) :)