Some help with a number theory problem

In summary, the conversation discusses a problem about integers a and b where a^n-1 divides b^n-1 for all n>0. It is suggested that if this is true, then b must be a natural power of a. However, the participants are unable to find a solution and there is a discussion about counterexamples and understanding the premise correctly. Finally, one participant suggests that the theorem can be proved by showing that b is a multiple of a.
  • #1
herraotic
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.
 
Physics news on Phys.org
  • #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.
 
  • #3
herraotic said:
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.
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.
 
  • #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?
 
  • #5
Martin Rattigan said:
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?
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.
 
  • #6
Martin Rattigan said:
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?

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?
 
  • #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
 
  • #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?
 
  • #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:
  • #10
Isn't the theorem straightforward once you know b=ka?
 
  • #11
No.

Do we know b=ka?
 
  • #12
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.
 
  • #13
But I don't think mathman was reading the question as intended when he said that. (See last few posts.)
 
  • #14
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.
 
  • #15
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.
 
  • #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:
  • #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:
  • #18
No, I meant p divides b but not a; that was the case in which I could get the contradiction.
 
  • #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].
 
  • #20
In fact if [itex](a,b)=1[/itex] the sequence will fail for [itex]n=\phi(b)[/itex].
 
Last edited:
  • #21
Apologies - when I edited #17 I probably rendered Huurkyl's #18 incomprehensible to anyone else reading.
 
  • #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
 
  • #23
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.
 
  • #24
Actually, I think my previous post is a complete solution to the problem. I wanted to acknowledge your contribution.

Petek
 
  • #25
Petek said:
Actually, I think my previous post is a complete solution to the problem. I wanted to acknowledge your contribution.

Petek
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.
 
  • #26
Hurkyl said:
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.

Oops! Back to the drawing board. Thanks for the correction.

Petek
 
  • #27
Well, I gave up and searched online for information about this problem. If you Google for the exact text of the first post in this thread, the first result is this thread and the second result points to another forum in which the exact same question was posed back in 2004. It turns out that the solution to this problem is surprisingly difficult. The problem was posed in the AMM, with a solution provided by the proposer. The thread in the other forum has lots of discussion. I'll post a link upon request.

Petek
 
  • #28
Martin Rattigan said:
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.
I agree that Mathman and I were probably reading the problem incorrectly, because given that

[itex](\forall n\in N)a^n-1|b^n-1[/itex] it is difficult to show that a|b much less that
[tex]b = a^k[/tex] While the converse is easily verified.
 
  • #29
As I suspected this problem turned out to be rather more than a relaxing Sunday afternoon puzzle.

Following Petek's lead I located the site to which I assume he refers, viz: http://www.mathlinks.ro/Forum/topic-4556.html through Google and I append a copy of the transcription of Marius Cavachi's original proof taken from the site.

I've "Latexed" it and cleaned it up a bit. Hopefully I've not introduced errors, but I haven't been through the proof yet, so it's quite possible I have. If necessary I'll remove these as I notice them or if anyone pointss them out.

Unfortunately I've had to append the proof in two posts (following) because it seems to flake the system out if I use one.
 
  • #30
Define a sequence [itex]{(Q_k)}[/itex] of polynomials with [itex]{deg(Q_k) \leq k}[/itex] by [itex]{Q_0 = -1}[/itex], and
[itex]{Q_{k+1}(x) = a^{k+1}(x-1)Q_k(bx)-b(a^{k+1}x-1)Q_k(x)}[/itex] for [itex]{k \geq 0}[/itex].

Observe that [itex]{Q_{k+1}(0) = (b - a^{k+1})Q_k(0)}[/itex]. Iterating this and employing [itex]{Q_0 = -1}[/itex] leads to
[itex]{Q_k(0) = -(b - a^k )(b - a^{k-1} )...(b - a)}[/itex].

Assume that [itex]{b\neq a^j}[/itex] for every non-negative integer [itex]{j}[/itex], so that [itex]{Q_k(0)\neq 0}[/itex].
We will obtain a contradiction by identifying a [itex]{k}[/itex] such that [itex]{Q_k}[/itex] is identically [itex]{0}[/itex].

Let [itex]{r_{0,n} = (b^{n - 1})/(a^{n - 1})}[/itex] for [itex]{n>0}[/itex].

By assumption [itex]{r_{0,n}}[/itex] is an integer.

For [itex]{k \geq 0}[/itex] define [itex]{r_{k+1,n}}[/itex] recursively by

[itex]{r_{k+1,n} = a^{k+1}r_{k,n+1} - br_{k,n}}[/itex]

Let [itex]{p_0 = 1}[/itex] and:

[itex]{{p_{k+1} = b(1 - a^{k+1} )p_k}}[/itex]

By induction on [itex]{k}[/itex] it follows for [itex]{n \geq 1}[/itex] and [itex]{k \geq 0}[/itex] that

[itex]{r_{k,n} = [b^np_k + Q_k(a^n) ]/[(a^{n+k} - 1)(a^{n+k-1} - 1)...(a^n - 1)]}[/itex]

Now fix [itex]{k}[/itex] so that [itex] a^k < b < a^{k+1} [/itex] . Since

[itex]{(a^n - 1)(a^{n+1} - 1)...(a^{n+k} - 1) = a^{n(k+1)} (1 - a^{-n} )(a - a^{-n} )...(a^k - a^{-n} ) \geq a^{n(k+1)} /2}[/itex]
we see that

[itex]{|r_{k,n}| \leq |b^np_k + Q_k(a^n)|/[a^{n(k+1)} /2] \leq 2( |p_k|(b/a^{k+1})^n + |Q_k(a^n)|/(a^n )^{k+1} )\;\;(*)}[/itex]
 
Last edited:
  • #31
Since [itex]{b < a^{k+1}}[/itex] and [itex]{deg(Q_k) < k+1}[/itex], the rightmost expression in (*) is bounded above by [itex]{1}[/itex]
when [itex]{n}[/itex] is sufficiently large. Thus [itex]{r_{k,n} = 0}[/itex] for large [itex]{n}[/itex], since it is an integer.

For all large [itex]{n}[/itex], this yields
[itex]{b^n p_k + Q_k(a^n) = 0}[/itex] and thus [itex]{p_k(b/a^k )^n + Q_k(a^n) /(a^n )^k = 0}[/itex].


This forces [itex]{p_k = 0}[/itex], since otherwise the left side is unbounded as [itex]{n\rightarrow +\infty}[/itex].
We now conclude that [itex]{Q_k(a^n) = 0}[/itex] for all [itex]{n}[/itex] and thus [itex]{Q_k}[/itex] is the zero polynomial
and we are done.
 
  • #32
I have noticed a couple of misprints in the previous two posts. Unfortunately I can no longer edit them. No one has pointed out the misprints so hopefully they haven't caused too much confusion, but I have corrected them and combined the posts below.

Define a sequence [itex]{(Q_k)}[/itex] of polynomials with [itex]{deg(Q_k) \leq k}[/itex] by [itex]{Q_0 = -1}[/itex], and [itex]{Q_{k+1}(x) = a^{k+1}(x-1)Q_k(ax)-b(a^{k+1}x-1)Q_k(x)}[/itex] for [itex]{k \geq 0}[/itex].

Observe that [itex]{Q_{k+1}(0) = (b - a^{k+1})Q_k(0)}[/itex]. Iterating this and employing [itex]{Q_0 = -1}[/itex] leads to [itex]{Q_k(0) = -(b - a^k )(b - a^{k-1} )...(b - a)}[/itex].

Assume that [itex]{b\neq a^j}[/itex] for every non-negative integer [itex]{j}[/itex], so that [itex]{Q_k(0)\neq 0}[/itex]. We will obtain a contradiction by identifying a [itex]{k}[/itex] such that [itex]{Q_k}[/itex] is identically [itex]{0}[/itex].

Let [itex]{r_{0,n} = (b^n - 1)/(a^n - 1)}[/itex] for [itex]{n>0}[/itex]. By assumption [itex]{r_{0,n}}[/itex] is an integer.

For [itex]{k\geq 0}[/itex] define [itex]{r_{k+1,n}}[/itex] recursively by [itex]{r_{k+1,n}=a^{k+1}r_{k,n+1}-br_{k,n}}[/itex].

Let [itex]{p_0=1}[/itex] and [itex]{{p_{k+1} = b(1 - a^{k+1} )p_k}}[/itex].

By induction on [itex]{k}[/itex] it follows for [itex]{n \geq 1}[/itex] and [itex]{k \geq 0}[/itex] that

[itex]{r_{k,n}=[b^np_k + Q_k(a^n) ]/[(a^{n+k} - 1)(a^{n+k-1} - 1)...(a^n - 1)]}[/itex]

Now fix [itex]{k}[/itex] so that [itex]a^k<b<a^{k+1}[/itex]. Since

[itex](a^n-1)(a^{n+1}-1)\dots(a^{n+k}-1)=a^{n(k+1)}(1-a^{-n})(a-a^{-n})\dots(a^k-a^{-n})\geq a^{n(k+1)}/2[/itex]

we see that

[itex]|r_{k,n}|\leq |b^np_k+Q_k(a^n)|/[a^{n(k+1)}/2]\leq 2(|p_k|(b/a^{k+1})^n+|Q_k(a^n)|/(a^n )^{k+1})\;\;(*)[/itex]

Since [itex]{b < a^{k+1}}[/itex] and [itex]{deg(Q_k) < k+1}[/itex], the rightmost expression in (*) is bounded above by [itex]{1}[/itex] when [itex]{n}[/itex] is sufficiently large. Thus [itex]{r_{k,n} = 0}[/itex] for large [itex]{n}[/itex], since it is an integer.

For all large [itex]{n}[/itex], this yields [itex]{b^n p_k + Q_k(a^n) = 0}[/itex] and thus [itex]{p_k(b/a^k )^n + Q_k(a^n) /(a^n )^k = 0}[/itex].

This forces [itex]{p_k = 0}[/itex], since otherwise the left side is unbounded as [itex]{n\rightarrow +\infty}[/itex]. We now conclude that [itex]{Q_k(a^n) = 0}[/itex] for all [itex]{n}[/itex] and thus [itex]{Q_k}[/itex] is the zero polynomial and we are done.
 

1. What is number theory?

Number theory is a branch of mathematics that studies the properties and relationships of numbers. It focuses on understanding the patterns and structures of numbers, including prime numbers, integers, and rational numbers.

2. What is a number theory problem?

A number theory problem is a mathematical question or puzzle that involves the properties and relationships of numbers. These problems often require creative thinking and use of mathematical concepts to find a solution.

3. How do I approach a number theory problem?

When approaching a number theory problem, it is important to carefully read and understand the given information. Then, try to identify any patterns or relationships between the numbers involved. You can also use known theorems and techniques from number theory to help solve the problem.

4. What are some common techniques used in number theory?

Some common techniques used in number theory include prime factorization, modular arithmetic, and the Chinese remainder theorem. Other techniques such as Euclid's algorithm and Fermat's little theorem can also be useful in solving number theory problems.

5. How can I improve my skills in number theory?

To improve your skills in number theory, it is important to practice solving different types of problems and familiarize yourself with various techniques and theorems. You can also read books and attend lectures or workshops to deepen your understanding of number theory concepts and applications.

Similar threads

  • Linear and Abstract Algebra
Replies
2
Views
676
  • Linear and Abstract Algebra
Replies
11
Views
1K
Replies
2
Views
671
  • Linear and Abstract Algebra
Replies
2
Views
317
  • Linear and Abstract Algebra
Replies
28
Views
3K
  • Linear and Abstract Algebra
Replies
4
Views
725
Replies
2
Views
921
  • Linear and Abstract Algebra
Replies
1
Views
569
  • Linear and Abstract Algebra
Replies
7
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
836
Back
Top