Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Some help with a number theory problem

  1. Feb 28, 2010 #1
    Let a,b>1 be integers such that for all n>0 we have a^n-1|b^n-1. Then b is a natural power of a. I can't find a solution.
     
  2. jcsd
  3. Mar 1, 2010 #2
    34 views and no solutions???

    Come on physicsforums, you're making me think this is a beta board and I should go look to more able forums.
     
  4. Mar 1, 2010 #3

    mathman

    User Avatar
    Science Advisor

    It doesn't look right to me. As far as I can tell you have a|b and nothing else. In other words if b/a is an integer, then so is (b/a)n.
     
  5. Mar 27, 2010 #4
    Well mathman doesn't actually give a counterexample or prove a|b unless I'm missing something in, "In other words ...", so no progress so far.

    Converse is easy to prove, and the result looks very plausible, but what is the origin of the question? I.e. is this likely to be a Sundy afternoon problem?
     
  6. Mar 27, 2010 #5

    mathman

    User Avatar
    Science Advisor

    Since your hypothesis is for all n, then for n=2, you are assuming a|b, which means b/a is an integer. Since all positive integer powers of integers are integers, there seems to be nothing else there.
     
  7. Mar 27, 2010 #6
    Didn't give a counterexample. Mathman said that all that was shown was a|b. In other words 2|6 is a counter example since 6 is not a power of 2. Any other pair of integers where the smaller divides the larger and the larger is not a power of the smaller is also a counter example or are we missing something here?
     
  8. Mar 27, 2010 #7
    I suspect that the premise is not being read correctly. I think it's not a^(n-1)|b^(n-1), but (a^n)-1|(b^n)-1. Had it been the former, it would have probably been expressed as a^n|b^n for n>=0. Besides, it's more interesting this way. :P
     
  9. Mar 27, 2010 #8
    But [itex]2^n-1|6^n-1[/itex] is false for n=2, that would be 3|35! So I don't see how 2 and 6 are a counterexample. To get a counterexample you would need a pair of numbers [itex]a,b[/itex] such that [itex](\forall n\in N)a^n-1|b^n-1[/itex] but where [itex]\neg(\exists n\in N)b=a^n[/itex].

    Isn't that correct?
     
  10. Mar 27, 2010 #9
    I've just read Dodo's note and the previous replies now make more sense. But I think what he says is certainly correct. It is the case that

    [itex](\exists k\in N)b=a^k\implies(\forall n\in N)a^n-1|b^n-1[/itex]

    I think we're being asked to prove the converse. The question wouldn't make much sense read the other way.

    The converse is likely to be a lot more awkward, which is why I wanted to get an idea of how much more awkward before I started thinking about it.
     
    Last edited: Mar 28, 2010
  11. Mar 27, 2010 #10

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Isn't the theorem straightforward once you know b=ka?
     
  12. Mar 28, 2010 #11
    No.

    Do we know b=ka?
     
  13. Mar 28, 2010 #12

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Try substituting it, then simplifying things.


    mathman already asserted that b=ka. Skimming the details in my head, we might need to look at gcd(a,b) first, though; I'm not sure.
     
  14. Mar 28, 2010 #13
    But I don't think mathman was reading the question as intended when he said that. (See last few posts.)
     
  15. Mar 28, 2010 #14

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I had convinced myself that was true yesterday (and I hadn't yet noticed that mathman also asserted it). Lemme see if I can remember how it worked -- I recall it being a straightforward "suppose p divides one of the numbers. Then it divides the other" argument, but I could have made a mistake in my head.
     
  16. Mar 28, 2010 #15

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Ah, yes. Suppose p divides b, but does not divide a. You can derive a contradiction by looking at things mod p....

    Of course, that doesn't show b and a have the same prime factors yet. But maybe this is all I noticed when I thought about it before.
     
  17. Mar 28, 2010 #16
    This entry referred to an edit to #9 which didn't appear to have happened. I now notice it did happen so I've deleted the previous irrelevant text in this entry.
     
    Last edited: Mar 28, 2010
  18. Mar 28, 2010 #17
    Hurkyl - If you derive a contradiction from [itex]p\mid b,p\nmid a[/itex] this shows neither that [itex]b[/itex] must be a multiple nor power of [itex]a[/itex]. E.g. [itex]b=18,a=12[/itex].

    The crux of the problem is that you are guaranteed a sequence such as:

    [itex]\[3^0-1|(3^3)^0-1\][/itex]
    [itex]\[3^1-1|(3^3)^1-1\][/itex]
    [itex]\[3^2-1|(3^3)^2-1\][/itex]
    [itex]\[3^3-1|(3^3)^3-1\][/itex]
    [itex]\[\dots\][/itex]

    You need to show that a sequence such as:

    [itex]\[3^0-1|5^0-1\][/itex]
    [itex]\[3^1-1|5^1-1\][/itex]
    [itex]\[3^2-1|5^2-1\][/itex]
    [itex]\[3^3-1|5^3-1\][/itex]
    [itex]\[\dots\][/itex]

    will fail at some point.
     
    Last edited: Mar 28, 2010
  19. Mar 28, 2010 #18

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    No, I meant p divides b but not a; that was the case in which I could get the contradiction.
     
  20. Mar 28, 2010 #19
    Of course if [itex]a,b[/itex] are both prime as in the example I gave, it is obvious the sequence will fail when [itex]n=b-1[/itex].
     
  21. Mar 28, 2010 #20
    In fact if [itex](a,b)=1[/itex] the sequence will fail for [itex]n=\phi(b)[/itex].
     
    Last edited: Mar 28, 2010
  22. Mar 28, 2010 #21
    Apologies - when I edited #17 I probably rendered Huurkyl's #18 incomprehensible to anyone else reading.
     
  23. Mar 28, 2010 #22
    I think that Hurkyl is saying: Suppose that b is not a power of a. Then there exists a prime p such that p divides b but p does not divide a. We then see that p divides [itex]a^{p-1} - 1[/itex], but p does not divide [itex]b^{p-1} -1[/itex], so the divisibility condition doesn't hold for the exponent n = p - 1.

    Petek
     
  24. Mar 28, 2010 #23

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I was not trying to claim a complete solution, just progress forward.

    If we can show b = ak, then substituting into the original condition and simplifying allows us to prove the theorem (by infinite descent).

    So the challenge is to show that a | b.

    The thing I could prove is merely a step towards proving a | b. I did not claim that it is a full proof.
     
  25. Mar 28, 2010 #24
    Actually, I think my previous post is a complete solution to the problem. I wanted to acknowledge your contribution.

    Petek
     
  26. Mar 28, 2010 #25

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Your first step fails: the hypothesis that b is not a power of a does not imply that b is divisible by a prime that doesn't divide a.

    e.g. consider b = 12 and a = 6.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook