- #1

- 4

- 0

## Main Question or Discussion Point

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.

- Thread starter herraotic
- Start date

- #1

- 4

- 0

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

- 4

- 0

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

- #3

mathman

Science Advisor

- 7,798

- 430

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

- #4

- 330

- 3

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?

- #5

mathman

Science Advisor

- 7,798

- 430

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.

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

- 841

- 0

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?

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?

- #7

- 695

- 2

- #8

- 330

- 3

Isn't that correct?

- #9

- 330

- 3

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.

[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:

- #10

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

Isn't the theorem straightforward once you know b=ka?

- #11

- 330

- 3

No.

Do we know b=ka?

Do we know b=ka?

- #12

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

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.

- #13

- 330

- 3

- #14

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

- #15

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

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.

- #16

- 330

- 3

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:

- #17

- 330

- 3

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.

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:

- #18

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

No, I meant p divides b but not a; that was the case in which I could get the contradiction.

- #19

- 330

- 3

- #20

- 330

- 3

In fact if [itex](a,b)=1[/itex] the sequence will fail for [itex]n=\phi(b)[/itex].

Last edited:

- #21

- 330

- 3

- #22

- 362

- 7

Petek

- #23

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

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.

- #24

- 362

- 7

Petek

- #25

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

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.isa complete solution to the problem. I wanted to acknowledge your contribution.

Petek

e.g. consider b = 12 and a = 6.