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

- inkyvoyd

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

- katieb

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

Get this expert

answer on brainly

SEE EXPERT ANSWER

Get your **free** account and access **expert** answers to this

and **thousands** of other questions

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

- anonymous

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

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

Looking for something else?

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

## More answers

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

- anonymous

Are you sure that that modular arithmetic works?

- inkyvoyd

Uh, no lol

- anonymous

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

- inkyvoyd

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

- anonymous

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

- inkyvoyd

Okay. Rawr. :/

- anonymous

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

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

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

- anonymous

Anyway properties of mod that deal with addition?

- inkyvoyd

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

- anonymous

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

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

- anonymous

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

- inkyvoyd

It's not fair :3

- inkyvoyd

can you tell me the answer? :3

- anonymous

I'm still trying to figure it out myself.

- anonymous

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

- anonymous

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

- inkyvoyd

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

- inkyvoyd

well you showed me how I mean

- anonymous

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

then we just subtract the two?

- anonymous

Well, notice something interesting?

- anonymous

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

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

- anonymous

That's what I'm thinking...

- anonymous

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

- anonymous

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

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

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

- inkyvoyd

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

- anonymous

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

- anonymous

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

- anonymous

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

- inkyvoyd

okay...

- anonymous

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

- anonymous

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

- anonymous

Now in the case that \(a>b\) you can just subtract them.
In the case where \(a

- anonymous

Does that make sense?

- inkyvoyd

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

- anonymous

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

Techincally, we determined you only needed the first 20.

- anonymous

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

- inkyvoyd

I used python to get an answer of 200.

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

- 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

- anonymous

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

Looking for something else?

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