# Possible Congruence Question

• Dec 3rd 2009, 01:16 PM
craig
Possible Congruence Question
When $\displaystyle n=2009$, find the remainder when

$\displaystyle \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 $\displaystyle 99 = 11 \times 9$, thinking that the solutions involves $\displaystyle (mod 11)$ and $\displaystyle (mod 9)$?

Thanks in advance for the help

Craig
• Dec 3rd 2009, 01:47 PM
Drexel28
Quote:

Originally Posted by craig
When $\displaystyle n=2009$, find the remainder when

$\displaystyle \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 $\displaystyle 99 = 11 \times 9$, thinking that the solutions involves $\displaystyle (mod 11)$ and $\displaystyle (mod 9)$?

Thanks in advance for the help

Craig

Problem: Find the remainder of $\displaystyle \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 $\displaystyle \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 $\displaystyle 10^{2009}\text{ mod }9,4\cdot 3^{2007}\text{ mod }11$. Note though that $\displaystyle 10\equiv1\text{ mod }9\implies 10^{2009}\equiv1^{2009}=1\text{ mod }9$. Also, note that $\displaystyle 4\cdot 3^{2007}=4\cdot 3^{7}\cdot3^{2000}$. And since $\displaystyle (3,11)=1$ and $\displaystyle \phi(11)=10$ we see then by Euler's theorem that $\displaystyle 4\cdot 3^{2007}\equiv 4\cdot 3^{7}\text{ mod }$. Lastly we see that $\displaystyle 4\cdot 3^7=12\cdot 3^6\equiv 3^6=729\equiv 3\text{ mod }11$. Thus our final answer is $\displaystyle \frac{1}{9}-\frac{3}{11}=\frac{-16}{99}$, but since we wanted the positive remainder we add $\displaystyle 99$ to the numerator to arrive at $\displaystyle \frac{83}{99}$. Thus $\displaystyle 11\cdot10^{2009}-4\cdot3^{2009}\equiv 83\text{ mod }99$

- Wolfram|Alpha
• Dec 3rd 2009, 02:31 PM
craig
Hi thanks a lot for your reply. I was following you until this bit:

Quote:

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

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

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

Quote:

we see then by Euler's theorem that $\displaystyle 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 $\displaystyle \text{ mod }11$?

Thanks again for the help

Craig
• Dec 3rd 2009, 03:32 PM
Drexel28
Quote:

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

I know that $\displaystyle 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 $\displaystyle \frac{4\cdot 3^{2009}}{99}=\frac{4\cdot 3^2\cdot3^{2009}}{99}=\frac{4\cdot 3^{2007}}{11}$

Quote:

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

Thanks again for the help

Craig
Clearly.