## anonymous 5 years ago prove the integer 53^103+103^53 is divisible by 39

1. anonymous

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

2. anonymous

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

3. anonymous

Oh.

4. myininaya

how do you do this without number theory?

5. anonymous

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

6. myininaya

what class is this?

7. myininaya

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

8. anonymous

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

9. myininaya

bond what was your modular arithmetic way?

10. anonymous

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

11. anonymous

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

12. myininaya

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

13. myininaya

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

14. anonymous

Yeah, it's the same idea.

15. anonymous

$$-14\equiv25$$

16. myininaya

17. anonymous

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

18. myininaya

14 is congruent to 1 mod 39?

19. anonymous

no, but 14^2 is

20. anonymous

14^2=196 and 195 is divisible by 39

21. myininaya

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

22. anonymous

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

23. myininaya

Its been awhile since i had number theory

24. anonymous

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

25. anonymous

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

26. anonymous

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

27. anonymous

Does this make sense maria?

28. anonymous

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

29. anonymous

why is 103 congruent to 25 ?

30. anonymous

Do you know why this is working, Maria?

31. anonymous

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.

32. anonymous

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.

33. anonymous

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.

34. anonymous

ohhhhhhhh.....I see