Multiples of 13

**MasterOfPie** · May 4th 2009, 01:29 PM

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

**Gamma** · May 4th 2009, 03:13 PM

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.

**Danny** · May 4th 2009, 03:31 PM

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)$

**MasterOfPie** · May 4th 2009, 06:27 PM

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

**Gamma** · May 4th 2009, 07:32 PM

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

**TheAbstractionist** · May 5th 2009, 02:54 AM

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

**Soroban** · May 5th 2009, 05:44 AM

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.

**glowplug19** · May 5th 2009, 09:42 AM

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?

**SimonM** · May 5th 2009, 11:16 AM

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

**TheAbstractionist** · May 5th 2009, 03:37 PM

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.

Thread: Multiples of 13

LinkBack

Thread Tools

Display

Multiples of 13

Similar Math Help Forum Discussions

Multiples

Multiples of 7 between 400&500

Multiples

sum of multiples

Multiples of 2, 3, 5, but not 7

Search Tags