Question

For every natural number n > 1, show that
\[
n^{61}−n
\]
is divisible by 56786730
Notice that
56786730=2×3×5×7×11×13×31×61

Answer 1

interesting problem. I don't know if this helps, but it can be factored as follows:\[\begin{align}
n^61-n&=n(n^60-1)\\
&=n(n^{30}-1)(n^{30}+1)\\
&=n(n^{15}-1)(n^{15}+1)(n^{30}+1)\\
\end{align}\]

Answer 2

Using M.I. :)

Answer 3

Lol, I was thinking on those lines, then I gave up :/

Answer 4

Sorry - made a mistake in the latex:\[\begin{align}
n^{61}-n&=n(n^{60}-1)\\
&=n(n^{30}-1)(n^{30}+1)\\
&=n(n^{15}-1)(n^{15}+1)(n^{30}+1)\\
\end{align}\]

Answer 5

\[ n^{15} - 1 = (n-1)(n^{14}+n^{13} + .... + n^2+n+1)\]

Answer 6

I think this might be more of a number theory type question. the fact that we have the prime factorization makes me things of eulers totient function, or fermats little theorem. Im going to grab my book lol

Answer 7

@FoolForMath this problem may be something you can shed light on...

Answer 8

it looks like we should be able to show that each of the primes in the factorization of of 56786730 divides the statement.

Answer 9

Too scared to see that big number. May be tomorrow :)

Answer 10

:)

Answer 11

\[\begin{align}
n^{61}-n&=n(n^{60}-1)\\
&=n(n^{30}-1)(n^{30}+1)\\
&=n(n^{15}-1)(n^{15}+1)(n^{30}+1)\\
&=n(n^{5}-1)(n^{10}+n^5+1)(n^{5}+1)(n^{10}-n^5+1)(n^{30}+1)\\
\end{align}\]this is using:\[a^3-b^3=(a-b)(a^2+ab+b^2)\]\[a^3+b^3=(a+b)(a^2-ab+b^2)\]this can also be applied to the \(n^{30}\) term. Don't know if this helps?

Answer 12

\[n^{30}+1=(n^{10}+1)(n^{20}-n^{10}+1)\]

Answer 13

\[n^{61}-n=n(n-1)(n+1)(n^2+1)(n^4-n^3+n^2-n+1)(n^4+n^3+n^2+n+1)(n^8-n^6+n^4-n^2+1)(n^10-n^5+1)(n^10+n^5+1)(n^20-n^10+1)\]

Answer 14

okay what i seem to think is that the factors 2 and 3 have been taken care of. and ...

oh there, @Davidc seems to have factored it. let's see.

Answer 15

we could also use:\[a^5-b^5=(a-b)(a^4+a^3b+a^2b^2+ab^3+b^4)\]to factor:\[n^5-1=(n-1)(n^4+n^3+n^2+n+1)\]then we have our 8 factors

Answer 16

n(n+1)(n-1) is divisible by 2x3 = 6

Answer 17

http://www.wolframalpha.com/input/?i=factorize+%28n^61-n%29

Answer 18

Alright, heres a good theorem we can use. If:\[k\equiv 1\]mod p-1, then:\[n^k-n\equiv 0 \]mod p
Its easy to check that 61 is congruent to 1 mod 2-1, 3-1, 5-1, etc. So it turns out all the primes in 56786730 do divide n^61-n. So 56786730 does divide that statement for all n.

Answer 19

so (thanks to experimentX), from wolfram we know the factors are:
\[n(n-1)(n+1)(n^2+1)(n^4-n^3+n^2-n+1)(n^4+n^3+n^2+n+1)\]\[(n^8-n^6+n^4-n^2+1)(n^{10}-n^5+1)(n^{10}+n^5+1)(n^{20}-n^{10}+1)\]and experimentX has made a good observation that:

n(n+1)(n-1) is divisible by 2x3 = 6

Answer 20

joemath314159: that is waaaayyy over my head - I need to read some books on number theory I guess :)

Answer 21

yeah, its definitely a number theory question.

Answer 22

It is amazing the person who gave the right solution gets only one medal while others who did not got 3.

Answer 23

I agree - this is one downside of only allowing each person to award one medal. I always feel too guilty to "undo" a medal I have already issued to give to someone else who has a better answer.

Answer 24

i feel the same!!

Answer 25

I think we should feed this back in the feedback group to make the site admins aware of this.

Answer 26

sure ... how to do it??

Answer 27

I have posted feedback here: http://openstudy.com/updates/4fb8ec86e4b05565342df607