2
$\begingroup$

I have the following question:

Find the remainder of $$\frac{3^{11}-1}{2}$$ divided by $9$

I tried to reformat the question: $$\frac{3^{11} -1 } {2} \times \frac{1}{9} = \frac{3^{11}-1}{18}$$ Since $3^2 = 9$ $$\frac{3^2(3^9) -1}{3^2 \times2}$$

I don't know where to go next. Anyway, this is one of my many attempts to solve this question, and most of them ends with a complicated solution. I don't want to use modular arithmetic for this question. A hint or anything will help me.

$\endgroup$

5 Answers 5

Reset to default
11
$\begingroup$

$$\frac{3^{11}-1}{2}=\frac{3-1}{2}(3^{10}+3^{9}+3^{8}+3^{7}+3^{6}+3^{5}+3^{4}+3^{3}+3^{2}+3+1)\equiv4$$

$\endgroup$
2
  • 4
    $\begingroup$ And by 7 you mean 4, right? The outside coefficient is 1, the powers of 3 are all multiples of 9 except for 1 and 3. $\endgroup$
    – Steven Irrgang
    Feb 16, 2017 at 7:15
  • $\begingroup$ Thanks! I finally understand now. $\endgroup$
    – Adola
    Feb 16, 2017 at 7:24
6
$\begingroup$

We have that $$\frac {3^{11}-1}{2} = \frac {3-1}{2}(3^{10} + 3^9 + \cdots + 3^2+3+1) \tag {1} $$

We know that $3^2 =9 \equiv 0 \mod 9$ and similarly $3^3 =3 (3^2) \equiv 0 \mod 9$ and so on. Thus, $(1)$ reduces to, $$1 (0 + 0 + 0 \cdots 0 + 3 +1 ) \equiv 4 \mod 9$$

Hope it helps.

$\endgroup$
1
  • 1
    $\begingroup$ :+1...very nice wiew $\endgroup$
    – Khosrotash
    Feb 16, 2017 at 7:18
3
$\begingroup$

$\frac {3^{11} - 1}{2} = \frac {3^{11} - 1}{3-1}=$

$3^{10} + 3^9 + .... + 3^2 + 3 + 1=$

$9(3^8 + ..... + 1) + 4$

so the remainder is $4$.

..or...

$\frac {3^{11}-1}2 = 3^{11}*\frac 12 - \frac 12 \equiv k \mod 9$

$ 3^{11}-1 \equiv 2k \mod 9$

$2k + 1 \equiv 0 \equiv 9 \mod 9$

$2k \equiv 8 \mod 9$

$k \equiv 4 \mod 9$.

$\endgroup$
2
$\begingroup$

The tool you need is modular arithmetic.

$3^{11}$ is congruent to $0$ mod $9$

$3^{11} - 1$ is congruent to $8$ mod $9$

The only hard part is the division. But, fortunately, you can uniquely divide by $2$ mod $9$: $0*2 = 0, 1*2 = 2, 2*2 = 4, 3*2 = 6, 4*2 = 8, 5*2 = 1, 6*2 = 3, 7*2 = 5,$ and $8*2 = 7$

so $8/2 = 4$ modulo $9$, thus the remainder is $4$.

$\endgroup$
2
$\begingroup$

$3^{11}$ is divisible by $9$.

So, $3^{11} - 1$, when divided by $9$, will give a remainder of $8$.

Division equation-

$a=bq+r$

$a= 3^{11} - 1$

$b= 9$

$r= 8$

$3^{11} - 1 = 9q + 8$

The $q$ given here will be even since $3^{11} - 1$ is even, $r$ is even and so $9q$ must also be even. Hence, $q$ is of the form $2k$ for some natural number $k$.

$3^{11} - 1 = 18k + 8$

Divide both sides by $2.$

$3^{11} - 1 = 18k + 8$

$(3^{11} - 1)/2 = 9k + 4$

Hence, the remainder is $4$ when $(3^{11} - 1)/2$ is divided by $9$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .