# Math Help - Multiples of 13

1. ## 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?
Could someone enlighten me to a solution to the problem. (The solution is way more important than the answer)
Thanks

2. 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.

3. Originally Posted by Gamma
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)$

4. 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)?

5. $a \equiv b$ mod n iff $n|(b-a)$
13|11-(-2)=13.

6. Originally Posted by MasterOfPie
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?
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.

7. 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.

8. Originally Posted by TheAbstractionist
Hence $54^6\equiv\pm1\pmod{13}$ and $69^{6}\equiv\pm1\pmod{13}.$
Interesting problem. Could this part be explained in further detail?

9. Originally Posted by Soroban

. . 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

10. Originally Posted by glowplug19
Originally Posted by TheAbstractionist
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.