Question

prove the integer 53^103+103^53 is divisible by 39

Answer 1

Are you familiar with modular arithmetic? (I hope).

Answer 2

no... :( ...please show me the steps

Answer 3

Oh.

Answer 4

how do you do this without number theory?

Answer 5

That's what I'm trying to think about.

Answer 6

what class is this?

Answer 7

If you can tell me the class, maybe I can come up with a way to help you that you will understand

Answer 8

I'm in 10th...just saw this problem and eager to know how to do it

Answer 9

bond what was your modular arithmetic way?

Answer 10

Well \(53\equiv14\) while \(103\equiv-14\), but that's as far as I got.

Answer 11

Plus 53 is an odd power, so the - stays.

Answer 12

oh wait 103 is congruent to 25 and 25+14=39

Answer 13

whenever i took number theory we wrote the numbers could only be between 0 and whatever number minus 1 we are writing are congruences in

Answer 14

Yeah, it's the same idea.

Answer 15

\(-14\equiv25\)

Answer 16

your right though

Answer 17

Ok, here's the deal:
\[53^{103}\equiv14^{103}=(14^2)^{51}*14\equiv1^{51}*14\equiv14({\rm mod} 39)\]

Answer 18

14 is congruent to 1 mod 39?

Answer 19

no, but 14^2 is

Answer 20

14^2=196 and 195 is divisible by 39

Answer 21

jaebond I think I might have to become your fan. I like your number theory skills.

Answer 22

Why thank you, I've been brushing up lately.

Answer 23

Its been awhile since i had number theory

Answer 24

So maria, the idea behind modular arithmetic is that we say that two numbers are the same if they differ by a multiple of modulus. In this case, if the "modulus" is 39, we say that 14 and 53 are the same. We also say that 92 is the same and we can write \(14\equiv53\equiv92 ({\rm mod }39)\)

Answer 25

Most of the properties of the integers hold as normal, except that you usually can't divide.

Answer 26

So the first step from what I did earlier looks like
\[53^{103}=53*53*53*...*53\] where there are 103 53's. But \(53\equiv14\), so this becomes \(14*14*14*...*14=14^{103}\).

Answer 27

Does this make sense maria?

Answer 28

hmmmm.....that's clear enough.... thanks both of you.... :)

Answer 29

why is 103 congruent to 25 ?

Answer 30

Do you know why this is working, Maria?

Answer 31

I would start off by realising 39 is divisible by 3 and 13, then show that 53^103 + 1-3^53 is divisible by both 3 and 13. It will then be divisible by 39.

Answer 32

So, 53mod3 == -1 (which means you can write 53 as 3n-1, for some integer n). So 53^103 = 3k-1, for some integer k. Similarly, 103mod3==1, which means 103^53 can be written 3p+1, for some integer p.

When you add them, 3k-1+3p+1 = 3(k+p)=3j, for some integer j. Therefore, 3 divides (103^53 + 53^103). That's the first part.

Answer 33

103mod13==-1, so 103^53 = 13s-1, for some integer s.

53mod13==1, so 53^13= 13t+1, for some integer t.

Adding them, 103^53+53^13=13(s+t)=13r, for some integer r.

Therefore, 13 divides your sum.

Since your sum is divisible by 3 and 13, and 3 and 13 are prime, it's divisible by 39.

Answer 34

ohhhhhhhh.....I see