Question

Show that n^(n-1) - 1 is divisible by (n-1)^2 for every positive integer "n".

Answer 1

How familiar are you with modular arithmetic?

Answer 2

i know nothing about modular arithmetic.

Answer 3

alright then, that means we should be able to come up with another way to solve the problem then >.<

Answer 4

Should I just quickly learn about modular arithmetic?

Answer 5

I would only take that route if you been staring at this problem for a couple of days and you still cant figure it out.

Answer 6

Alright

Answer 7

if you factor the expression once you get:\[n^{n-1}-1^{n-1}=(n-1)(n^{n-2}+n^{n-3}+\cdots + n+1)\]

Answer 8

so there is one n-1, now our job is to show that:\[n^{n-2}+\cdots + n+1\]also has a factor of n-1 in it.

Answer 9

I got to the same step then i was suck

Answer 10

not satisfied for n=1, so this statement not true

Answer 11

There is probably some restriction like n greater than or equal to 2. because it is true for n=2 and bigger.

Answer 12

but the problem said "every positive integer n".

Answer 13

So the statement is false? Would using modular arithmetic help at all is n is 2 or larger if that's the case?

Answer 14

exactly, this is false
in induction's method, u have to show it will satisfies for n=1 but the reality
0/0 not real

Answer 15

There is something wrong with the statement if n = 1 since you are saying something is divisible by 0. But for n = 2 and greater, its true.

Answer 16

But isn't 0 divisible by 0? I mean there exists a k such that k 0 = 0

Answer 17

It's an indeterminate form, and every k will satisfy, but still.

Answer 18

i''ll post my modular arithmetic solution just to show that its a true statement if n = 2 or bigger, but I still think there should be another solution, maybe not easier, but not involving higher math.

Leaving off from an earlier post, I only need to show that:\[n^{n-2}+n^{n-3}+\ldots+n+1\]is divisible by n-1. So im going to check the remainder when I divide by n-1. If the remainder is 0, then im good.

The remainder when you divide n by n-1 is 1. (Think, divide 4 by 3, or 10 by 9, there is always a remainder of 1). So:\[n^{n-2}+n^{n-3}+\ldots+n+1\equiv (1)^{n-2}+(1)^{n-3}+\ldots +(1)+1\] modulo n-1. Since there are n-1 terms in that summation, it follows that:\[(1)^{n-2}+(1)^{n-3}+\ldots +(1)+1=1+1+\cdots + 1=n-1\], and since n-1 perfectly divides n-1, the remainder is 0.

Answer 19

yeah, that's right for n>=2

Answer 20

I think everything will make better sense after i learn more about modular arithmetic.

Answer 21

Thank you for suggesting this method, i will continue to dig into it.

Answer 22

im still convinced there is a "normal" solution lol, i'll be thinking about it for a bit.

Answer 23

\[n^{n-2}=(n-1+1)^{n-2}=1+\sum_{k=1}^{n-2}\left(\begin{matrix}n-2 \\ k\end{matrix}\right)(n-1)^k\]\[n^{n-3}=(n-1+1)^{n-3}=1+\sum_{k=1}^{n-3}\left(\begin{matrix}n-3 \\ k\end{matrix}\right)(n-1)^k\]\[\vdots\]\[n^2=(n-1+1)^2=1+\sum_{k=1}^{2}\left(\begin{matrix}2 \\ k\end{matrix}\right)(n-1)^k\]\[n=1+(n-1)\]\[1 = 1\] ------------------------------
\[n^{n-2}+\cdots+1=(n-1)+\text{ polynomial in } (n-1)\]

Answer 24

\[n^{n-1}-1=(n-1)\left(n^{n-2}+n^{n-3}+\cdots+n^2+n+1 \right)\]

Answer 25

I do not quite understand your method. I don't think the math are st my level yet. Would you like to further explain it?

Answer 26

Let a=n-1 then,
n^(n-1) -1=(a+1)^a -1=(1+a)^a -1 =1+aC1*a+aC2*a^2+aC3*a^3+...+aCa*a^a -1
=1-1+aC1*a+aC2*a^2+aC3*a^3+...+aCa*a^a
=a*a +aC2*a^2+aC3*a^3+...+aCa*a^a
=a^2 (1+aC2 + aC3*a + ...+ aCa a^(a-2) )
Thus,
(a+1)^a -1 is always divisible a^2
=> n^(n-1) -1 is always divisible by (n-1)^2

Answer 27

@sauravshakya Can you please explain how you get from (1+a)^a -1 to =1+aC1*a+aC2*a^2+aC3*a^3+...+aCa*a^a -1. What is the "C" from aC1*a represent?

Answer 28

Bimomial expansion of (1+a)^a

Answer 29

Binomial*

Answer 30

Now, I understand. Thank you so much! I not only solved the problem, I learnt a lot more about binomial expansion as well. Thank you so much everyone! :)