Results 1 to 4 of 4

Math Help - Possible Congruence Question

  1. #1
    Super Member craig's Avatar
    Joined
    Apr 2008
    Posts
    748
    Thanks
    1
    Awards
    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
    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
    21
    Quote Originally Posted by craig View Post
    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
    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 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
    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
    21
    Quote Originally Posted by craig View Post
    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.
    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: September 13th 2009, 09:51 AM
  4. Congruence question
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: January 6th 2009, 08:46 AM
  5. Congruence question
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 11th 2007, 03:31 PM

Search Tags


/mathhelpforum @mathhelpforum