Here's the question you clicked on:
inkyvoyd
How many positive integers N<1000 are there, such that 3^N-N^3 is a multiple of 5?
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?
If you do mod 10, the the solutions are \[ 5-0 =5\\ 6-1=5\\ 7-2=5\\ 8-3=5\\ 9-4=5 \]
Hmmm, so I mean it eliminates what they can be... a bit.
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,
Are you sure that that modular arithmetic works?
You're just checking that the last digit is the same...
yeah, but how do I even solve this problem? do you have any idea or hints? xD
Honest, I'm not sure, but I do think it probably involve modular arithmetic.
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?
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...
mm. So we solve both equations for n, and subtract the intersections?
Anyway properties of mod that deal with addition?
uhh, I have no idea what I'm doing here lol
Okay I messed up. It should be:\[ 3^n-n^3 \equiv 0\pmod{10}\\ 3^n-n^3 \equiv 5\pmod{10} \]
how does one solve these equations? if it takes too long to explain, do you know of any links where I could learn more?
You'd have to learn modular arithmetic/number theory.
can you tell me the answer? :3
I'm still trying to figure it out myself.
Think about what happens to the last digit of the \(3^n\) terms... each time it is multiplied by 3.
When \(n=0\), it is \(3^n = 1\pmod{10}\)
oh god I think I figured out how to solve this problem then
well you showed me how I mean
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}\\ \]
then we just subtract the two?
Well, notice something interesting?
We know that the \(n^3\) begins to cycle after 10, while the \(3^n\) begins to cycle after 4.
ugh, the lcm of those is 20, so we'll have to check all solutions for up to 20, then multiply by 1000/20?
That's what I'm thinking...
Here, I'll write a program to do it up to the first 20... brb.
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} \]
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} \]
The only problem here is that I'm not sure if Javascript can handle numbers as large as \(3^{100}\)
I have mathematica - but I don't know how to use it lol
But we seems to consistently 1/10 to be congruent... meaning that if we do 0 to 999, we'd get 100.
Whoops.... I was never letting c go to above 10... hmmm I'm gonna have to try this...
Okay, so i'm getting about 4 for every 20... that is to say 1/5 of them seem to work.
Okay so here is what I did.... I kept track of \(3^n\mod{10}\) as well as \(n^3\mod{10}\)
So let's just say : \[ 3^n \equiv a \pmod{10}\\ n^3 \equiv b \pmod{10} \]
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.
Yeah. Wait, did you program this brute-force?
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 \]
Techincally, we determined you only needed the first 20.
I could have done this by hand relatively quickly, but I am very prone to mistakes. That is why I programmed it.
I used python to get an answer of 200.
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 :)
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
I'm getting n/5 for all n that is a multiple of 20.