## inkyvoyd 2 years ago How many positive integers N<1000 are there, such that 3^N-N^3 is a multiple of 5?

1. inkyvoyd

I rewrote it as modular arithmetic 3^N mod 10=N^3 mod 10 or |3^N mod 10 -N^3 mod 10|=5 But how do I solve this?

2. wio

If you do mod 10, the the solutions are $5-0 =5\\ 6-1=5\\ 7-2=5\\ 8-3=5\\ 9-4=5$

3. wio

Hmmm, so I mean it eliminates what they can be... a bit.

4. inkyvoyd

this problem is from brilliant.org . I have no idea what I'm supposed to do to solve it, but I know it's number theory. I tried factoring the expression into difference of cubes, bu that did not work,

5. wio

Are you sure that that modular arithmetic works?

6. inkyvoyd

Uh, no lol

7. wio

You're just checking that the last digit is the same...

8. inkyvoyd

yeah, but how do I even solve this problem? do you have any idea or hints? xD

9. wio

Honest, I'm not sure, but I do think it probably involve modular arithmetic.

10. inkyvoyd

Okay. Rawr. :/

11. wio

Hmmm, well we definitely have to leverage the fact that if it is a multiple of five, then it's last digit is either 0 or 5, right?

12. inkyvoyd

yeah. I got that part, which is why I was able to reformulate the problem in terms of modular arithmetic, which I have no knowledge of...

13. inkyvoyd

mm. So we solve both equations for n, and subtract the intersections?

14. wio

Anyway properties of mod that deal with addition?

15. inkyvoyd

uhh, I have no idea what I'm doing here lol

16. wio

Okay I messed up. It should be:$3^n-n^3 \equiv 0\pmod{10}\\ 3^n-n^3 \equiv 5\pmod{10}$

17. inkyvoyd

how does one solve these equations? if it takes too long to explain, do you know of any links where I could learn more?

18. wio

You'd have to learn modular arithmetic/number theory.

19. inkyvoyd

It's not fair :3

20. inkyvoyd

can you tell me the answer? :3

21. wio

I'm still trying to figure it out myself.

22. wio

Think about what happens to the last digit of the $$3^n$$ terms... each time it is multiplied by 3.

23. wio

When $$n=0$$, it is $$3^n = 1\pmod{10}$$

24. inkyvoyd

oh god I think I figured out how to solve this problem then

25. inkyvoyd

well you showed me how I mean

26. wio

Okay I programmed a bit and got these patterns: $n^3\\ 0^3 \equiv 0 \pmod{10}\\ 1^3 \equiv 1 \pmod{10}\\ 2^3 \equiv 8 \pmod{10}\\ 3^3 \equiv 7 \pmod{10}\\ 4^3 \equiv 4 \pmod{10}\\ 5^3 \equiv 5 \pmod{10}\\ 6^3 \equiv 6 \pmod{10}\\ 7^3 \equiv 3 \pmod{10}\\ 8^3 \equiv 2 \pmod{10}\\ 9^3 \equiv 9 \pmod{10}\\ 3^n\\ 3^0 \equiv 1 \pmod{10}\\ 3^1 \equiv 3 \pmod{10}\\ 3^2 \equiv 9 \pmod{10}\\ 3^3 \equiv 7 \pmod{10}\\ 3^4 \equiv 1 \pmod{10}\\ 3^5 \equiv 3 \pmod{10}\\ 3^6 \equiv 9 \pmod{10}\\ 3^7 \equiv 7 \pmod{10}\\ 3^8 \equiv 1 \pmod{10}\\ 3^9 \equiv 3 \pmod{10}\\$

27. inkyvoyd

then we just subtract the two?

28. wio

Well, notice something interesting?

29. wio

We know that the $$n^3$$ begins to cycle after 10, while the $$3^n$$ begins to cycle after 4.

30. inkyvoyd

ugh, the lcm of those is 20, so we'll have to check all solutions for up to 20, then multiply by 1000/20?

31. wio

That's what I'm thinking...

32. wio

Here, I'll write a program to do it up to the first 20... brb.

33. wio

When I go to 20....$\begin{array}{rlcrcl} 3:& 3^{3} &-& 3^4 &\equiv& 0 \pmod{10}\\ 17:& 3^{17} &-& 17^4 &\equiv& 0 \pmod{10}\\ \end{array}$

34. wio

When I go to 100 $\begin{array}{rlcrcl} 3:& 3^{3} &-& 3^4 &\equiv& 0 \pmod{10}\\ 17:& 3^{17} &-& 17^4 &\equiv& 0 \pmod{10}\\ 23:& 3^{23} &-& 23^4 &\equiv& 0 \pmod{10}\\ 37:& 3^{37} &-& 37^4 &\equiv& 0 \pmod{10}\\ 43:& 3^{43} &-& 43^4 &\equiv& 0 \pmod{10}\\ 57:& 3^{57} &-& 57^4 &\equiv& 0 \pmod{10}\\ 63:& 3^{63} &-& 63^4 &\equiv& 0 \pmod{10}\\ 77:& 3^{77} &-& 77^4 &\equiv& 0 \pmod{10}\\ 83:& 3^{83} &-& 83^4 &\equiv& 0 \pmod{10}\\ 97:& 3^{97} &-& 97^4 &\equiv& 0 \pmod{10}\\ \end{array}$

35. wio

The only problem here is that I'm not sure if Javascript can handle numbers as large as $$3^{100}$$

36. inkyvoyd

I have mathematica - but I don't know how to use it lol

37. wio

But we seems to consistently 1/10 to be congruent... meaning that if we do 0 to 999, we'd get 100.

38. wio

Whoops.... I was never letting c go to above 10... hmmm I'm gonna have to try this...

39. wio

Okay, so i'm getting about 4 for every 20... that is to say 1/5 of them seem to work.

40. inkyvoyd

okay...

41. wio

Okay so here is what I did.... I kept track of $$3^n\mod{10}$$ as well as $$n^3\mod{10}$$

42. wio

So let's just say : $3^n \equiv a \pmod{10}\\ n^3 \equiv b \pmod{10}$

43. wio

Now in the case that $$a>b$$ you can just subtract them. In the case where $$a<b$$ you have to add $$10$$ to $$a$$ first, then subtract.

44. wio

Does that make sense?

45. inkyvoyd

Yeah. Wait, did you program this brute-force?

46. wio

Here look:$\begin{array}{rrrrrl} n & a & b & a-b & r & \text{pass/fail}\\ 0 & 1 & 0 & 1 & 1 & \text{fail}\\ 1 & 3 & 1 & 2 & 2 & \text{fail}\\ 2 & 9 & 8 & 1 & 1 & \text{fail}\\ 3 & 7 & 7 & 0 & 0 & \text{pass}\\ 4 & 1 & 4 & -3 & 7 & \text{fail}\\ 5 & 3 & 5 & -2 & 8 & \text{fail}\\ 6 & 9 & 6 & 3 & 3 & \text{fail}\\ 7 & 7 & 3 & 4 & 4 & \text{fail}\\ 8 & 1 & 2 & -1 & 9 & \text{fail}\\ 9 & 3 & 9 & -6 & 4 & \text{fail}\\ 10 & 9 & 0 & 9 & 9 & \text{fail}\\ 11 & 7 & 1 & 6 & 6 & \text{fail}\\ 12 & 1 & 8 & -7 & 3 & \text{fail}\\ 13 & 3 & 7 & -4 & 6 & \text{fail}\\ 14 & 9 & 4 & 5 & 5 & \text{pass}\\ 15 & 7 & 5 & 2 & 2 & \text{fail}\\ 16 & 1 & 6 & -5 & 5 & \text{pass}\\ 17 & 3 & 3 & 0 & 0 & \text{pass}\\ 18 & 9 & 2 & 7 & 7 & \text{fail}\\ 19 & 7 & 9 & -2 & 8 & \text{fail}\\ \end{array}\\ 4/20 = 1/5$

47. wio

Techincally, we determined you only needed the first 20.

48. wio

I could have done this by hand relatively quickly, but I am very prone to mistakes. That is why I programmed it.

49. inkyvoyd

I used python to get an answer of 200.

50. inkyvoyd

import numbers i=0 for n in range (1,1000): if (3**n-n**3)%5==0: i=i+1 print(i) Was that the answer you got? Good thing it agreed with our methods :)

51. inkyvoyd

Didn't actually need import numbers, but I mean funny how 5 lines of code can get a hour's worth of math work done :S

52. wio

I'm getting n/5 for all n that is a multiple of 20.