Results 1 to 10 of 10

Thread: 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 $\displaystyle 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.

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

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

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

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

    so Finally
    $\displaystyle 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,470
    Thanks
    83
    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.

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

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

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

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

    so Finally
    $\displaystyle 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

    $\displaystyle 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
    $\displaystyle a \equiv b$ mod n iff $\displaystyle 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 $\displaystyle 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, $\displaystyle 54^{12}\equiv1\pmod{13}$ and $\displaystyle 69^{12}\equiv1\pmod{13}.$ Hence $\displaystyle 54^6\equiv\pm1\pmod{13}$ and $\displaystyle 69^{6}\equiv\pm1\pmod{13}.$

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

    Since neither $\displaystyle 54+69=123$ nor $\displaystyle -54+69=15$ is divisible by 13, we conclude that $\displaystyle 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
    12,028
    Thanks
    848
    Hello, MasterOfPie!

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


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

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

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


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



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

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


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



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

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

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

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


    Therefore, the answer is no: .$\displaystyle 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 $\displaystyle 54^6\equiv\pm1\pmod{13}$ and $\displaystyle 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 $\displaystyle (1 + 2^{31})$ is a multiple of 13, then $\displaystyle 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 $\displaystyle 54^6\equiv\pm1\pmod{13}$
    Interesting problem. Could this part be explained in further detail?
    Hi glowplug19.

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

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

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

    Since 13 is a prime, it divides one of $\displaystyle 54^6-1$ and $\displaystyle 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: Oct 30th 2009, 10:31 PM
  2. Multiples of 7 between 400&500
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Dec 4th 2008, 03:27 PM
  3. Multiples
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Feb 21st 2008, 04:13 PM
  4. sum of multiples
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Sep 11th 2007, 02:12 AM
  5. Multiples of 2, 3, 5, but not 7
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Apr 11th 2005, 09:36 PM

Search Tags


/mathhelpforum @mathhelpforum