Possible Congruence Question

**craig** · December 3rd 2009, 01:16 PM

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

**Drexel28** · December 3rd 2009, 01:47 PM

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

**craig** · December 3rd 2009, 02:31 PM

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

**Drexel28** · December 3rd 2009, 03:32 PM

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.

Thread: Possible Congruence Question

LinkBack

Thread Tools

Display

Possible Congruence Question

Similar Math Help Forum Discussions

congruence question

congruence question

Congruence question

Congruence question

Congruence question

Search Tags