# Math Help - Possible Congruence Question

1. ## Possible Congruence Question

When $n=2009$, find the remainder when

$\frac{11 \times 10^n - 4 \times 3^n}{99}$.

Have no idea how to approach this problem, any help would be appreciated

I've got the hint that $99 = 11 \times 9$, thinking that the solutions involves $(mod 11)$ and $(mod 9)$?

Thanks in advance for the help

Craig

2. Originally Posted by craig
When $n=2009$, find the remainder when

$\frac{11 \times 10^n - 4 \times 3^n}{99}$.

Have no idea how to approach this problem, any help would be appreciated

I've got the hint that $99 = 11 \times 9$, thinking that the solutions involves $(mod 11)$ and $(mod 9)$?

Thanks in advance for the help

Craig
Problem: Find the remainder of $\frac{11\cdot 10^{2009}-4\cdot 3^{2009}}{99}$

Solution: Note that this is equivalent to asking what is the smallest positive remainder of the above. So realize though that $\frac{11\cdot 10^{2009}-4\cdot 3^{2009}}{99}=\frac{10^{2009}}{9}-\frac{4\cdot 3^{2007}}{11}$. To do this we work in mods, namely we compute $10^{2009}\text{ mod }9,4\cdot 3^{2007}\text{ mod }11$. Note though that $10\equiv1\text{ mod }9\implies 10^{2009}\equiv1^{2009}=1\text{ mod }9$. Also, note that $4\cdot 3^{2007}=4\cdot 3^{7}\cdot3^{2000}$. And since $(3,11)=1$ and $\phi(11)=10$ we see then by Euler's theorem that $4\cdot 3^{2007}\equiv 4\cdot 3^{7}\text{ mod }$. Lastly we see that $4\cdot 3^7=12\cdot 3^6\equiv 3^6=729\equiv 3\text{ mod }11$. Thus our final answer is $\frac{1}{9}-\frac{3}{11}=\frac{-16}{99}$, but since we wanted the positive remainder we add $99$ to the numerator to arrive at $\frac{83}{99}$. Thus $11\cdot10^{2009}-4\cdot3^{2009}\equiv 83\text{ mod }99$

- Wolfram|Alpha

3. Hi thanks a lot for your reply. I was following you until this bit:

Originally Posted by Drexel28
Also, note that $4\cdot 3^{2007}=4\cdot 3^{7}\cdot3^{2000}$. And since $(3,11)=1$ and $\phi(11)=10$ we see then by Euler's theorem that $4\cdot 3^{2007}\equiv 4\cdot 3^{7}\text{ mod }$. Lastly we see that $4\cdot 3^7=12\cdot 3^6\equiv 3^6=729\equiv 3\text{ mod }11$.
I know that $4\cdot 3^{2007}=4\cdot 3^{7}\cdot3^{2000}$.

But I'm not sure how you got to this result,

we see then by Euler's theorem that $4\cdot 3^{2007}\equiv 4\cdot 3^{7}\text{ mod }$
Also is there a typo in that last bit, did you mean to end it with $\text{ mod }11$?

Thanks again for the help

Craig

4. Originally Posted by craig
Hi thanks a lot for your reply. I was following you until this bit:

I know that $4\cdot 3^{2007}=4\cdot 3^{7}\cdot3^{2000}$.

But I'm not sure how you got to this result,
[/tex]
We were dealing with, as the second fraction $\frac{4\cdot 3^{2009}}{99}=\frac{4\cdot 3^2\cdot3^{2009}}{99}=\frac{4\cdot 3^{2007}}{11}$

Also is there a typo in that last bit, did you mean to end it with $\text{ mod }11$?

Thanks again for the help

Craig
Clearly.