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$
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$
  • 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 '17 at 7:15
  • $\begingroup$ Thanks! I finally understand now. $\endgroup$ – Adola Feb 16 '17 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
    $\begingroup$ :+1...very nice wiew $\endgroup$ – Khosrotash Feb 16 '17 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$
3
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.