Show that if n devides a^n-b^n then n devides (a^n-b^n)/(a-b).

[rbetan]

1. Homework Statement .

show that if n devides a^n-b^n then n devides the quotient (a^n-b^n)/(a-b).

here n,a,b are natural numbers with a and b distinct.

2. Homework Equations .



3. The Attempt at a Solution .

i know i have to assume that n divides a^n-b^n. So, then a^n-b^n when divided by n will yield a remainder of 0. Therefore, one can say that a^n-b^n is congruent to o in (mod n).

So a^n-b^n=0(mod n) then, a^n=b^n(mod n).

but then i am stuck... i don't know if i am approaching it from the right direction. If am, am still very stuck.

thanks for any help.

 

[Cyosis]

If n|a^n-b^n then there exists a c, such that a^n-b^n=cn. This is exactly what you wrote down by using modulars, but this may look a little bit less confusing. Can you continue from here?

 

[rbetan]

okey i got an idea from your hint, but i get stuck again, let me show you what i got so far:

assuming that a^n+b^n=cn for some c but one can factor

a^n+b^n=(a-b)(a^p-1+a^n-2 b+…+a b^n-2+b^n-1)

so (a^n+b^n)/(a-b)=(a^p-1+a^n-2 b+…+a b^n-2+b^n-1)

if one can show that n|(a^p-1+a^n-2 b+…+a b^n-2+b^n-1) then it is done

but i have no idea how to continue from here. thanks for your help

 

[Cyosis]

You're making it way too hard on yourself. The problem statement states that a and b are distinct, therefore a-b \neq. Now replace a^n-b^n with cn. Does n divide this new expression?

 

[rbetan]

I am sorry i did not understand what you meant in this last post. can you elaborate more please.

i did understand that since a is different from b then their difference a-b is different from zero.

But i did not understand what do you mean by replacing a^n-b^n with cn.

 

[Cyosis]

You know that a^n-b^n=cn so what is

<br /> \frac{a^n-b^n}{a-b}<br />?

 

[rbetan]

then (a^n-b^n)/(a-b) is equal to (cn)/(a-b)

 

[rbetan]

if one can show that n | cn/(a-b) then it is done.

n| cn/(a-b) means that cn/(a-b)=nK; where K is an integer.

so for n to divide cn/(a-b) means that c/(a-b) is an integer

But how can i know that indeed this quantity c/(a-b) is an integer?

 

[Cyosis]

if one can show that n | cn/(a-b) then it is done.

n of course divides cn/(a-b) since cn/(a-b) is a multiple of c/(a-b). You're basically done at this point. Of course we have assumed here that \frac{a^n-b^n}{a-b} is an integer otherwise the entire exercise would be pointless.

If you're not convinced we can prove it with induction.

 

[Office_Shredder]

n of course divides cn/(a-b) since cn/(a-b) is a multiple of c/(a-b). You're basically done at this point. Of course we have assumed here that \frac{a^n-b^n}{a-b} is an integer otherwise the entire exercise would be pointless.

If you're not convinced we can prove it with induction.

You have to show that c/(a-b) is an integer surely.

\frac{a^n-b^n}{a-b} doesn't give us that trivially c/(a-b) is an integer, since aⁿ-bⁿ =/= c

 

[rbetan]

thanks for your help, i really appreciate it

 

[rbetan]

I do not see how does it follow that c/(a-b) must be an integer.

can you please help.

 

[Cyosis]

Yes I jumped to the conclusion too quickly. I'll have a look on how to do it correctly.

 

[rbetan]

Okey let me recap and show what i think is some progress.

Assume: n|a^n-b^n then a^n-b^n=cn for some integer c.
but a =/=b therefore, a-b=/=0. so one can divide by a-b.

(a^n-b^n)/(a-b) = (cn)/(a-b); "new goal is to show that n|cn/(a-b);"

However, recall that a^n-b^n=(a-b)(a^(n-1)+...+b^(n-1)) by the binomial theorem

so (a-b)|(a^n-b^n); therefore, cn/(a-b) is an integer.

however, i am stuck, i cannot show that c/(a-b) is an integer nor that n|cn/(a-b)

thanks for any help.

 

[MLeszega]

okey i got an idea from your hint, but i get stuck again, let me show you what i got so far:

assuming that a^n+b^n=cn for some c but one can factor

a^n+b^n=(a-b)(a^p-1+a^n-2 b+…+a b^n-2+b^n-1)

so (a^n+b^n)/(a-b)=(a^p-1+a^n-2 b+…+a b^n-2+b^n-1)

if one can show that n|(a^p-1+a^n-2 b+…+a b^n-2+b^n-1) then it is done

but i have no idea how to continue from here. thanks for your help

The problem doesn't say anything else about a,b and n other then that they are all natural numbers and a and b are distinct? Because it would be great if somewhere it says something like if d=a-b then gcd(n,d)=1.

 

[D H]

n of course divides cn/(a-b) since cn/(a-b) is a multiple of c/(a-b). You're basically done at this point.

Way too fast! You're almost done at this point only if gcd(n,a-b)=1. You still have to show that a-b divides c, which is fairly trivial given that a-b divides cn and that gcd(n,a-b)=1. Things get interesting when gcd(n,a-b)=m, m>1. Things get very interesting when m<n.

I suggest a reboot of the problem. Write a=b+d. What is aⁿ-bⁿ? (Hint: Binomial expansion). What is aⁿ-bⁿ mod n? (Hint: Almost all of the terms in the binomial expansion vanish modulo n).

 

[MLeszega]

Any update on this problem? I am interested in its solution.

 

[D H]

This is a homework problem. By the rules of this forum, those of us who know how to solve the problem cannot show the solution here. We can only point the way to the solution.

I gave a couple of hints in my previous post. Try working with these hints. Ask questions if you don't understand to what I was alluding in those hints.

 

[MLeszega]

Ok. I guess my question would then be whether or not you can assume that the gcd(n,a-b)=1. The problem is simple if you can assume that, but doesn't seem to be if you can't.

 

[D H]

You cannot assume that.

For example, consider the simple case of a=3, b=1, n=2. Then a-b=2, a²-b²=8. 2 divides 4 and 8, so the conjecture certainly holds for this simple case, even though gcd(n,a-b)=2. The conjecture similarly holds for all numbers a,b, a-b=kn so long as n divides aⁿ-bⁿ.

Another hint: n divides \left( \begin{matrix}n \\ k \end{matrix} \right) for all k between but not including 1 and n. Write a=b+kn and evaluate aⁿ-bⁿ mod n.


An even tougher case: a=7, b=1, n=4. Here, gcd(n,a-b)=2, but a-b is not a multiple of n.

 

[MLeszega]

Ok, I figured out the solution today while at work. Ty for the hints.