$\begingroup$

As the question stated, what is the remainder when ${13}^7$ is divided by 9? There are quite a few online questions similar to this. However, I do not really understand the concept of it.

I have attempted this question by looking for a pattern (as suggested in some online search):

${13}^1 / 9$ = 4 remainder

${13}^2 / 9$ = 7 remainder

${13}^3 / 9$ = 1 remainder

${13}^4 / 9$ = 4 remainder

...

There is clearly a pattern of 4, 7, 1 before it repeats itself in the power 4. For power 7, the remainder is therefore 4. I believe the answer to this question is 4 remainder.

My question is how will I approach if the power is much larger than power 7? Say, if we have ${13}^{100}$ divide by 9, is it right to find the remainder using this method:

$100 / 3 = 33.33333 $

Since $33 * 3 = 99$, for the remainder at the 100th power, it will be 4.

Is there a more elegant way of doing this?

Edit:

Actually, this method does not seem to work if the divisible value is larger than 13. Any idea?

$\endgroup$ 5

4 Answers

$\begingroup$

The pattern you found is that the answer for $13^n$ depends on what residue you get from dividing $n$ by 3: if it's 1 the answer is 4, if it's 2, the answer is 7, if it's 0 the answer is 1.

Now I avoided using the language of group theory but that's ultimately what you need to learn. What happens here is that for any integers $n$ and $m$, $n$ has finite order modulo $m$, and a classical problem is to find that order. You can learn for example that this order divides $\varphi(m)$ where $\varphi$ is the Euler totient function; this is a direct consequence of Lagrange's theorem in group theory.

In this language what your computations show is that 13 has order 3 modulo 9, and that's why the exponent only matters modulo 3.

$\endgroup$ $\begingroup$

From$$13^n=(4+9)^n=4^n+n\cdot 4^{n-1}\cdot 9+\frac{n(n-1)}2\cdot 4^{n-2}\cdot 9^2+\cdots$$it clearly follows$$13^n\ mod\ 9=4^n\ mod\ 9$$Next$$\left((remainder\ 4)\cdot 4=16\right)\ mod\ 9=7$$$$\left((remainder\ 7)\cdot 4=28\right)\ mod\ 9=1$$$$\left((remainder\ 1)\cdot 4=4\right)\ mod\ 9=4$$Thus your periodicity observation is proved correct.

$$$$Wrt. to the $100/3$ bit of your question, that one in turn can be given as $100\ mod\ 3=1$.

--- rk

$\endgroup$ 1 $\begingroup$

Warning. I am using the notation of modular arithmetic, which is particularly convenient for your problem.

Since $13 \equiv 4 \bmod 9$, one has $13^n \equiv 4^n =2^{2n}\bmod 9$. Thus it suffices to compute the sequence $u_n = 2^n \bmod 9$. It is easy to compute this periodic sequence if you observe that $2^3 \equiv -1 \bmod 9$:\begin{align} u_0 &= 1, &u_1 &= 2, &u_2 &= 4, \\ u_3 &= -1\equiv 8, &u_4&= -2 \equiv 7, &u_5&=-4 \equiv 5, \\ u_6 &= 1, &&\text{etc.} \end{align}In particular, $u_{14} = u_2 = 4$ and thus $13^7 \equiv 4 \bmod 9$. Moreover, as you predicted, the sequence $u_{2n}$ has period $3$: $1, 4, 7, 1, \ldots$.

$\endgroup$ $\begingroup$

If you see empirically a pattern so you can cut (a partition of $\mathbb{N}$) $\mathbb{N}$ like follow. $$\mathbb{N}=\{3k , k \in \mathbb{N}\}\cup\{3k+1 , k \in \mathbb{N}\}\cup\{3k+2, k \in \mathbb{N}\}$$

Let $k \in \mathbb{N}$

Because $$ 4^{3k} \equiv 64^k \equiv 1^k \equiv1 \mod9 $$

We get :$$ 13^{3k}\equiv 4^{3k}\equiv 1 \mod 9 \\ 13^{3k+1}\equiv 4^{3k+1}\equiv 4 \mod 9 \\ 13^{3k+2}\equiv 4^{3k+2}\equiv 16 \equiv7 \mod 9 \\$$

So the cycle is verified. And because :

$$ 7=3*2+1$$

The remainder of the division of $13^7 $ by $9$ is $4$.

$\endgroup$