wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> When A = B^k
        
(Message started by: Barukh on Mar 5^th, 2004, 5:59am)

Title: When A = B^k
Post by Barukh on Mar 5^th, 2004, 5:59am

Given two numbers A, B [in] [bbn]. Prove that the following statements are equivalent:

1. For every n [in] [bbn], (Bⁿ-1) | (Aⁿ-1).
2. A = B^k for some k [in] [bbn].

Title: Re: When A = B^k
Post by Pietro K.C. on Mar 8^th, 2004, 3:23am

OK, we have to show that (1) --> (2) and (2) --> (1).

The second part is easy:
[hide]
If A = B^k, then

Aⁿ - 1 = B^kn - 1.

Setting X = Bⁿ gives

Aⁿ - 1 X^k - 1
-------- = --------- = 1 + X + ... + X^k-1 [in] N
Bⁿ - 1 X - 1

for each n [in] N.
[/hide]

For the first part, I've been able to show that, assuming (1),
[hide]
if p is a prime and p | A, then p | B.
[/hide]
Proof:
[hide]
Suppose p prime such that p | A but not p | B. Then Aⁿ - 1 is not divisible by p for any n [in] N, while p | B^p-1 - 1. Therefore,

A^p-1 - 1
--------- [notin] N.
B^p-1 - 1
[/hide]

Using this, I've been able to demonstrate the theorem for the restricted case where [hide]B is a prime power[/hide]. It's a fun problem to work on, Barukh!

Title: Re: When A = B^k
Post by Pietro K.C. on Apr 2^nd, 2004, 1:18pm

No luck yet... :P

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

(*) Bⁿ-1 | Aⁿ-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] Aⁿ-1 = qⁿBⁿ-1 = qⁿBⁿ-Bⁿ+Bⁿ-1 = Bⁿ(qⁿ-1) + (Bⁿ-1)

and hence

Bⁿ-1 | Aⁿ-1 [bigto] Bⁿ-1 | Bⁿ(qⁿ-1).

Since gcd(Bⁿ,Bⁿ-1) = 1, this happens iff

Bⁿ-1 | qⁿ-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 = B^k 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 B^k [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?

Title: Re: When A = B^k
Post by Barukh on Apr 3^rd, 2004, 3:29am

Pietro, I am glad you are trying to solve this difficult problem and not give up too easy :D! 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: [hide]Consider the expression (Aⁿ-1)/(Bⁿ-1) – (Aⁿ/Bⁿ + Aⁿ/B²ⁿ + .. + Aⁿ/B^kn + …), where the last sum runs for all k such that B^kn <= Aⁿ[/hide].

HINT 2: [hide]Search for another thread in this section that links the first hint with the solution[/hide].

Good luck!

Title: Re: When A = B^k
Post by Barukh on May 29^th, 2004, 10:12am

Before this thread is forgotten in obscurity, here’s the solution I know.

[smiley=blacksquare.gif][hide]
Let M = max {k | B^k [le] A}. Consider the sum S(n) = [sum]_k=1^M Aⁿ/B^kn. Because

S(n) = Aⁿ(B^-n - B^-(M+1)n)/(1 - B^-n) [ge] (Aⁿ - B)/(Bⁿ - 1),
(Aⁿ-1) / (Bⁿ-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 (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam;action=display;num=1077786604) 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 r_k[in][bbq] (k=1,…,M) and lim {[sum]r_kⁿ} [to] 0 when n [to][infty], then r_k[in][bbz]. Now, in S(n), take r_k = A/B^k, and the result follows.
[/hide][smiley=blacksquare.gif]