Results 1 to 4 of 4

Thread: Possible Congruence Question

  1. #1
    Super Member craig's Avatar
    Joined
    Apr 2008
    Posts
    748
    Thanks
    1
    Awards
    1

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    22
    Quote Originally Posted by craig View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member craig's Avatar
    Joined
    Apr 2008
    Posts
    748
    Thanks
    1
    Awards
    1
    Hi thanks a lot for your reply. I was following you until this bit:

    Quote Originally Posted by Drexel28 View Post
    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,

    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    22
    Quote Originally Posted by craig View Post
    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}$



    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. congruence question
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: May 8th 2011, 10:09 AM
  2. congruence question
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 6th 2010, 07:20 AM
  3. Congruence question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Sep 13th 2009, 09:51 AM
  4. Congruence question
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: Jan 6th 2009, 08:46 AM
  5. Congruence question
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Oct 11th 2007, 03:31 PM

Search Tags


/mathhelpforum @mathhelpforum