Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

inkyvoyd

  • 3 years ago

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

  • This Question is Closed
  1. inkyvoyd
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  4. inkyvoyd
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Are you sure that that modular arithmetic works?

  6. inkyvoyd
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Uh, no lol

  7. wio
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  8. inkyvoyd
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  9. wio
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  10. inkyvoyd
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Okay. Rawr. :/

  11. wio
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  14. wio
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Anyway properties of mod that deal with addition?

  15. inkyvoyd
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  16. wio
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  19. inkyvoyd
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    It's not fair :3

  20. inkyvoyd
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    can you tell me the answer? :3

  21. wio
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    I'm still trying to figure it out myself.

  22. wio
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  23. wio
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  24. inkyvoyd
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  25. inkyvoyd
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    well you showed me how I mean

  26. wio
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    then we just subtract the two?

  28. wio
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Well, notice something interesting?

  29. wio
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  30. inkyvoyd
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    That's what I'm thinking...

  32. wio
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  33. wio
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  36. inkyvoyd
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  37. wio
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  38. wio
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  39. wio
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  40. inkyvoyd
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    okay...

  41. wio
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  42. wio
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  43. wio
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Does that make sense?

  45. inkyvoyd
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  46. wio
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Techincally, we determined you only needed the first 20.

  48. wio
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  49. inkyvoyd
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    I used python to get an answer of 200.

  50. inkyvoyd
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  53. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy