How many positive integers N

Question

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

inkyvoyd · Answer

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?

anonymous · Answer

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

anonymous · Answer

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

inkyvoyd · Answer

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,

anonymous · Answer

Are you sure that that modular arithmetic works?

inkyvoyd · Answer

Uh, no lol

anonymous · Answer

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

inkyvoyd · Answer

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

anonymous · Answer

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

inkyvoyd · Answer

Okay. Rawr. :/

anonymous · Answer

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?

inkyvoyd · Answer

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

inkyvoyd · Answer

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

anonymous · Answer

Anyway properties of mod that deal with addition?

inkyvoyd · Answer

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

anonymous · Answer

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

inkyvoyd · Answer

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

anonymous · Answer

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

inkyvoyd · Answer

It's not fair :3

inkyvoyd · Answer

can you tell me the answer? :3

anonymous · Answer

I'm still trying to figure it out myself.

anonymous · Answer

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

anonymous · Answer

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

inkyvoyd · Answer

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

inkyvoyd · Answer

well you showed me how I mean

anonymous · Answer

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

inkyvoyd · Answer

then we just subtract the two?

anonymous · Answer

Well, notice something interesting?

anonymous · Answer

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

inkyvoyd · Answer

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

anonymous · Answer

That's what I'm thinking...

anonymous · Answer

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

anonymous · Answer

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

anonymous · Answer

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

anonymous · Answer

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

inkyvoyd · Answer

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

anonymous · Answer

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

anonymous · Answer

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

anonymous · Answer

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

inkyvoyd · Answer

okay...

anonymous · Answer

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

anonymous · Answer

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

anonymous · Answer

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.

anonymous · Answer

Does that make sense?

inkyvoyd · Answer

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

anonymous · Answer

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

anonymous · Answer

Techincally, we determined you only needed the first 20.

anonymous · Answer

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

inkyvoyd · Answer

I used python to get an answer of 200.

inkyvoyd · Answer

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

inkyvoyd · Answer

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

anonymous · Answer

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