Author |
Topic: When A = B^k (Read 770 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
When A = B^k
« on: Mar 5th, 2004, 5:59am » |
 Quote  Modify
|
Given two numbers A, B [in] [bbn]. Prove that the following statements are equivalent:
1. For every n [in] [bbn], (Bn-1) | (An-1).
2. A = Bk for some k [in] [bbn].
|
|
 IP Logged |
|
|
|
Pietro K.C.
Full Member
 
Gender:
Posts: 213
|
|
Re: When A = B^k
« Reply #1 on: Mar 8th, 2004, 3:23am » |
Quote Modify
|
OK, we have to show that (1) --> (2) and (2) --> (1).
The second part is easy:
If A = Bk, then
An - 1 = Bkn - 1.
Setting X = Bn gives
An - 1 Xk - 1
-------- = --------- = 1 + X + ... + Xk-1 [in] N
Bn - 1 X - 1
for each n [in] N.
For the first part, I've been able to show that, assuming (1),
if p is a prime and p | A, then p | B.
Proof:
Suppose p prime such that p | A but not p | B. Then An - 1 is not divisible by p for any n [in] N, while p | Bp-1 - 1. Therefore,
Ap-1 - 1
--------- [notin] N.
Bp-1 - 1
Using this, I've been able to demonstrate the theorem for the restricted case where B is a prime power. It's a fun problem to work on, Barukh!
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: When A = B^k
« Reply #2 on: Apr 2nd, 2004, 1:18pm » |
Quote Modify
|
No luck yet... 
Wish I could say it's due to lack of time, but I've worked on it through a few of my more tedious classes - especially Economics for Engineers - and it isn't solved.
Besides what I said in the preceding post, I've come to the following rather weak conclusions (I won't hide them because they're more like lines of attack than solutions):
1. If, given the information that
(*) Bn-1 | An-1 for all n [in] [bbn]
and A > B, we can show that B | A, the theorem will be proved. Because then we'll be able to write
A = qB [bigto] An-1 = qnBn-1 = qnBn-Bn+Bn-1 = Bn(qn-1) + (Bn-1)
and hence
Bn-1 | An-1 [bigto] Bn-1 | Bn(qn-1).
Since gcd(Bn,Bn-1) = 1, this happens iff
Bn-1 | qn-1
and so we're back at the original problem, but now with a smaller number. Applying the hypothetical B | A argument over and over, eventually we'll reach q < B, in which case
B-1 | q-1 [bigleftrightarrow] q = 1.
So we'll have A = B[cdot][cdot][cdot]B[cdot]1 = Bk for some k [in] [bbn] (might be 0).
2. From (*) we gather that, whenever gcd(B,m)=1 for an m [in] [bbn], also gcd(A,m)=1 (prove this). Further, the order of A mod m always divides the order of B mod m. (Define the order to be zero if there is no k [in] [bbn] such that Bk [equiv] 1 (mod m))
I'm not sure what to make of this, but it may be useful. I think only pairs of numbers where one is a power of the other can have this property. Needless to say, a proof of this would amount to a proof of the theorem.
Any takers?
|
| « Last Edit: Apr 2nd, 2004, 6:46pm by Pietro K.C. » |
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: When A = B^k
« Reply #3 on: Apr 3rd, 2004, 3:29am » |
Quote Modify
|
Pietro, I am glad you are trying to solve this difficult problem and not give up too easy  ! Your observations are very good.
If you want to try another approach which leads to the solution I've learned, here are two hints  :
HINT 1: Consider the expression (An-1)/(Bn-1) – (An/Bn + An/B2n + .. + An/Bkn + …), where the last sum runs for all k such that Bkn <= An.
HINT 2: Search for another thread in this section that links the first hint with the solution.
Good luck!
|
| « Last Edit: Apr 3rd, 2004, 3:29am by Barukh » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: When A = B^k
« Reply #4 on: May 29th, 2004, 10:12am » |
Quote Modify
|
Before this thread is forgotten in obscurity, here’s the solution I know.
[smiley=blacksquare.gif]
Let M = max {k | Bk [le] A}. Consider the sum S(n) = [sum]k=1M An/Bkn. Because
S(n) = An(B-n - B-(M+1)n)/(1 - B-n) [ge] (An - B)/(Bn - 1),
(An-1) / (Bn-1) - S(n) [to] 0 when n [to] [infty]. This is equivalent to { S(n) } [to] 0 when n [to] [infty] ( {} is fractional part ).
Now, the following thread proves the statement about the “integral nature” of a rational r whose powers’ fractional part has a limit 0. This statement may be naturally generalized as follows: if rk[in][bbq] (k=1,…,M) and lim {[sum]rkn} [to] 0 when n [to][infty], then rk[in][bbz]. Now, in S(n), take rk = A/Bk, and the result follows.
[smiley=blacksquare.gif]
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print