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

1. Jun 13, 2009

### rbetan

1. The problem statement, all variables and given/known data.

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

2. Jun 13, 2009

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

Last edited: Jun 13, 2009
3. Jun 13, 2009

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

4. Jun 13, 2009

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

5. Jun 13, 2009

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

6. Jun 13, 2009

### Cyosis

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

$$\frac{a^n-b^n}{a-b}$$?

7. Jun 13, 2009

### rbetan

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

8. Jun 13, 2009

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

9. Jun 13, 2009

### Cyosis

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.

10. Jun 13, 2009

### Office_Shredder

Staff Emeritus

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 an-bn =/= c

11. Jun 13, 2009

### rbetan

thanks for your help, i really appreciate it

12. Jun 13, 2009

### rbetan

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

13. Jun 13, 2009

### Cyosis

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

14. Jun 14, 2009

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

15. Jun 15, 2009

### MLeszega

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.

16. Jun 15, 2009

### D H

Staff Emeritus
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 an-bn? (Hint: Binomial expansion). What is an-bn mod n? (Hint: Almost all of the terms in the binomial expansion vanish modulo n).

17. Jun 16, 2009

### MLeszega

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

18. Jun 16, 2009

### D H

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

19. Jun 16, 2009

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

20. Jun 16, 2009

### D H

Staff Emeritus
You cannot assume that.

For example, consider the simple case of a=3, b=1, n=2. Then a-b=2, a2-b2=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 an-bn.

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