inkyvoyd Group Title How many positive integers N<1000 are there, such that 3^N-N^3 is a multiple of 5? one year ago one year ago

1. inkyvoyd Group Title

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 Group Title

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 Group Title

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

4. inkyvoyd Group Title

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 Group Title

Are you sure that that modular arithmetic works?

6. inkyvoyd Group Title

Uh, no lol

7. wio Group Title

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

8. inkyvoyd Group Title

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

9. wio Group Title

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

10. inkyvoyd Group Title

Okay. Rawr. :/

11. wio Group Title

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 Group Title

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 Group Title

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

14. wio Group Title

Anyway properties of mod that deal with addition?

15. inkyvoyd Group Title

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

16. wio Group Title

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 Group Title

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 Group Title

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

19. inkyvoyd Group Title

It's not fair :3

20. inkyvoyd Group Title

can you tell me the answer? :3

21. wio Group Title

I'm still trying to figure it out myself.

22. wio Group Title

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

23. wio Group Title

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

24. inkyvoyd Group Title

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

25. inkyvoyd Group Title

well you showed me how I mean

26. wio Group Title

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 Group Title

then we just subtract the two?

28. wio Group Title

Well, notice something interesting?

29. wio Group Title

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

30. inkyvoyd Group Title

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 Group Title

That's what I'm thinking...

32. wio Group Title

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

33. wio Group Title

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 Group Title

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 Group Title

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

36. inkyvoyd Group Title

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

37. wio Group Title

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

38. wio Group Title

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

39. wio Group Title

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

40. inkyvoyd Group Title

okay...

41. wio Group Title

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

42. wio Group Title

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

43. wio Group Title

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 Group Title

Does that make sense?

45. inkyvoyd Group Title

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

46. wio Group Title

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 Group Title

Techincally, we determined you only needed the first 20.

48. wio Group Title

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

49. inkyvoyd Group Title

I used python to get an answer of 200.

50. inkyvoyd Group Title

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 Group Title

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 Group Title

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