Results 1 to 10 of 10

Math Help - Multiples of 13

  1. #1
    Newbie
    Joined
    May 2009
    Posts
    2

    Multiples of 13

    I didn't know where to post this problem so excuse me if this isn't where it should be..
    The problem is:
    Is 54^{103} + 69^{67} a multiple of 13?
    I have no idea how to go about this problem.
    Could someone enlighten me to a solution to the problem. (The solution is way more important than the answer)
    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517
    This is probably an Algebra or Discrete or number theory problem, but Ill help anyway.

    I hope you know modular arithmetic if you were assigned this problem
    Reduce mod 13 and see if it is 0 mod 13 or not.

    54=13*4+2 \Rightarrow 54 \equiv 2 (mod 13)
    69=13*5+4 \Rightarrow 69 \equiv 4 (mod 13)

    Now I suggest calculating the orders of these guys mod 13.
    2^4 \equiv 3
    2^6 =2^42^2\equiv 3*2^2 = 12 \equiv -1
    2^{12}=(2^6)^2 \equiv -1^2 = 1
    54^{103} =54^{12*8+7} \equiv (2^12)^8 2^7 \equiv 2^7 \equiv -2 \equiv 11 (mod 13)

    Similarly
    4^2 \equiv 3 (mod 13)
    4^3 =4^24 \equiv 4*3 = 12 \equiv -1 (mod 13)
    4^6=(4^3)^2 \equiv (-1)^2 \equiv 1 (mod 13)

    69^{67}=69^{6*11+1}=(67^6)^{11}69 \equiv 4 (mod 13)

    so Finally
    54^{103} + 69^{67} \equiv 11 + 4 \equiv 2 (mod 13)
    but if it were divisible by 13 it should be 0 mod 13, so it is not divisible.

    You need to check these calculations, I did them very quickly, so they may be unreliable, but that should at least give you an idea.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Jester's Avatar
    Joined
    Dec 2008
    From
    Conway AR
    Posts
    2,325
    Thanks
    10
    Quote Originally Posted by Gamma View Post
    This is probably an Algebra or Discrete or number theory problem, but Ill help anyway.

    I hope you know modular arithmetic if you were assigned this problem
    Reduce mod 13 and see if it is 0 mod 13 or not.

    54=13*4+2 \Rightarrow 54 \equiv 2 (mod 13)
    69=13*5+4 \Rightarrow 69 \equiv 4 (mod 13)

    Now I suggest calculating the orders of these guys mod 13.
    2^4 \equiv 3
    2^6 =2^42^2\equiv 3*2^2 = 12 \equiv -1
    2^{12}=(2^6)^2 \equiv -1^2 = 1
    54^{103} =54^{12*8+7} \equiv (2^12)^8 2^7 \equiv 2^7 \equiv -2 \equiv 11 (mod 13)

    Similarly
    4^2 \equiv 3 (mod 13)
    4^3 =4^24 \equiv 4*3 = 12 \equiv -1 (mod 13)
    4^6=(4^3)^2 \equiv (-1)^2 \equiv 1 (mod 13)

    69^{67}=69^{6*11+1}=(67^6)^{11}69 \equiv 4 (mod 13)

    so Finally
    54^{103} + 69^{67} \equiv 11 + 4 \equiv 2 (mod 13)
    but if it were divisible by 13 it should be 0 mod 13, so it is not divisible.

    You need to check these calculations, I did them very quickly, so they may be unreliable, but that should at least give you an idea.
    Maple agree's with you

    54^{103} + 69^{67} = 2\; \text{(mod }13)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    May 2009
    Posts
    2
    Thank you very much, but I have one question. How did you go from:
    2^7 is equivalent to -2 is equivalent to 11 (mod 13)

    Edit: (i think i got it.. 2^7 is 2^6*2 so (-1)*(2) = -2 and then (13 - 2) to get it in mod 13)?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517
    a \equiv b mod n iff n|(b-a)
    13|11-(-2)=13.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Quote Originally Posted by MasterOfPie View Post
    I didn't know where to post this problem so excuse me if this isn't where it should be..
    The problem is:
    Is 54^{103} + 69^{67} a multiple of 13?
    I have no idea how to go about this problem.
    Could someone enlighten me to a solution to the problem. (The solution is way more important than the answer)
    Thanks
    Hi MasterOfPie.

    By Fermatís little theorem, 54^{12}\equiv1\pmod{13} and 69^{12}\equiv1\pmod{13}. Hence 54^6\equiv\pm1\pmod{13} and 69^{6}\equiv\pm1\pmod{13}.

    \therefore\ 54^{103}+69^{67}=54^{17\times6+1}+69^{11\times6+1}  \equiv\pm54\pm69\pmod{13}.

    Since neither 54+69=123 nor -54+69=15 is divisible by 13, we conclude that 54^{103}+69^{67} is not divisible by 13.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,547
    Thanks
    539
    Hello, MasterOfPie!

    Here's a primitive approach that doesn't require familiarity with Modulo Arithmetic.


    Is 54^{103} + 69^{67} a multiple of 13?

    We have: . 54^{103} \;=\;(4\cdot13 + 2)^{103}

    . = \; (4\cdot13)^{103} + {103\choose102}(4\cdot13)^{103}(2^1) + {103\choose101}(4\cdot13)^{101}(2^2) + \hdots  + {103\choose1}(4\cdot13)^1(2^{102}) + 2^{103}
    . . . . | \leftarrow - - - - - - - - - - - - - _{\text{ multiple of 13 }} - - - - - - - - - - - - - - - - - - - - - \rightarrow|


    So we are concerned with the remainder only: . 2^{103}



    We have: . 69^{67} \:=\:(5\cdot13 + 4)^{67}

    . = \; (5\cdot13)^{67} + {67\choose66}(5\cdot13)^{66}(4^1) + {67\choose65}(5\cdot13)^{65}(4^2) + \hdots  + {67\choose1}(5\cdot13)^1(4^{66}) + 4^{67}
    . . . | \leftarrow - - - - - - - - - - - - - _{\text{ multiple of 13 }} - - - - - - - - - - - - - - - - - - \rightarrow|


    So we are concerned with the remainder only: . 4^{67}



    The problem becomes: .Is (2^{103} + 4^{67}) a multiple of 13?

    We have: . 2^{103} + (2^2)^{67} \;=\;2^{103} + 2^{134} \;=\;2^{103}(1 + 2^{31})

    . . Obviously, 2^{103} is not a multiple of 13.

    . . If (1 + 2^{31}) is a multiple of 13, then 2^{31} must be a multiple of 12.
    . . . . This, of course, is also impossible.


    Therefore, the answer is no: . 54^{103} + 69^{67} is not a multiple of 13.

    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    May 2009
    Posts
    8
    Quote Originally Posted by TheAbstractionist View Post
    Hence 54^6\equiv\pm1\pmod{13} and 69^{6}\equiv\pm1\pmod{13}.
    Interesting problem. Could this part be explained in further detail?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Oct 2008
    From
    Guernsey
    Posts
    69
    Quote Originally Posted by Soroban View Post

    . . If (1 + 2^{31}) is a multiple of 13, then 2^{31} must be a multiple of 12.
    . . . . This, of course, is also impossible.
    I'm not convinced by this step;

    1+25 is divisible by 13, but 25 isn't divisible by 12
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Quote Originally Posted by glowplug19 View Post
    Quote Originally Posted by TheAbstractionist View Post
    Hence 54^6\equiv\pm1\pmod{13}
    Interesting problem. Could this part be explained in further detail?
    Hi glowplug19.

    We have 54^{12}\equiv1\pmod{13}

    \implies\ 54^{12}-1\equiv0\pmod{13}

    \implies\ (54^6-1)(54^6+1)\equiv0\pmod{13}

    Since 13 is a prime, it divides one of 54^6-1 and 54^6+1,\ \therefore\ 54^6\equiv\pm1\pmod{13}.

    The reason for using 6 rather than 12 is that it allows you to get closer to 103 and 67.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Multiples
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 30th 2009, 10:31 PM
  2. Multiples of 7 between 400&500
    Posted in the Algebra Forum
    Replies: 1
    Last Post: December 4th 2008, 03:27 PM
  3. Multiples
    Posted in the Algebra Forum
    Replies: 3
    Last Post: February 21st 2008, 04:13 PM
  4. sum of multiples
    Posted in the Algebra Forum
    Replies: 1
    Last Post: September 11th 2007, 02:12 AM
  5. Multiples of 2, 3, 5, but not 7
    Posted in the Algebra Forum
    Replies: 2
    Last Post: April 11th 2005, 09:36 PM

Search Tags


/mathhelpforum @mathhelpforum