1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Jun 13, 2009 #1
    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. jcsd
  3. Jun 13, 2009 #2


    User Avatar
    Homework Helper

    If [itex]n|a^n-b^n[/itex] then there exists a c, such that [itex] a^n-b^n=cn[/itex]. 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
  4. Jun 13, 2009 #3
    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
  5. Jun 13, 2009 #4


    User Avatar
    Homework Helper

    You're making it way too hard on yourself. The problem statement states that a and b are distinct, therefore [itex]a-b \neq [/itex]. Now replace a^n-b^n with cn. Does n divide this new expression?
  6. Jun 13, 2009 #5
    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.
  7. Jun 13, 2009 #6


    User Avatar
    Homework Helper

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

  8. Jun 13, 2009 #7
    then (a^n-b^n)/(a-b) is equal to (cn)/(a-b)
  9. Jun 13, 2009 #8
    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?
  10. Jun 13, 2009 #9


    User Avatar
    Homework Helper

    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 [itex]\frac{a^n-b^n}{a-b}[/itex] is an integer otherwise the entire exercise would be pointless.

    If you're not convinced we can prove it with induction.
  11. Jun 13, 2009 #10


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

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

    [itex]\frac{a^n-b^n}{a-b}[/itex] doesn't give us that trivially c/(a-b) is an integer, since an-bn =/= c
  12. Jun 13, 2009 #11
    thanks for your help, i really appreciate it
  13. Jun 13, 2009 #12
    I do not see how does it follow that c/(a-b) must be an integer.

    can you please help.
  14. Jun 13, 2009 #13


    User Avatar
    Homework Helper

    Yes I jumped to the conclusion too quickly. I'll have a look on how to do it correctly.
  15. Jun 14, 2009 #14
    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.
  16. Jun 15, 2009 #15
    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.
  17. Jun 15, 2009 #16

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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).
  18. Jun 16, 2009 #17
    Any update on this problem? I am interested in its solution.
  19. Jun 16, 2009 #18

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
  20. Jun 16, 2009 #19
    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.
  21. Jun 16, 2009 #20

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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 [itex]\left( \begin{matrix}n \\ k \end{matrix} \right)[/itex] 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.
  22. Jun 17, 2009 #21
    Ok, I figured out the solution today while at work. Ty for the hints.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook