Is There Always a Solution for b^x - b^y to be Divisible by a?

[Petr Mugver]

For any natural number a and b, with b > 1, two natural numbers x and y can always be found such that b^x - b^y is divisible by a.

Until now, with many tries of a and b, I have always found corresponding x and y.

I would appreciate if somebody could give me a proof or a counter example.

 

[micromass]

Hi Petr Mugver!

It seems to be always possible. Note that (if x>y) we can factor

b^x-b^y=b^y(b^{x-y}-1)

By this factorization, we can assume a coprime of b. Indeed, if p^k is a prime power that divides both a and b, then p^k will divide b^k. So we just need to choose y>k.

Now, if a and b are coprime, then I claim that there is always a z such that a divides b^z-1. Or, in other words, that b^z=1 (mod a). This follows immediately from Euler's theorem and we can choose z=\varphi(a).

 

[Petr Mugver]

Thanks for the reply!

I need to "translate" it though (I am a physician and quite unfamiliar with all this number theory stuff), but I assume that your answer is correct, so just give me some time to understand it!

Now, please tell me: has your answer something to do with the proof I figured out, which is the following:

I calculate 1/a using Euclid Algorithm "in base b". Then 1/a will be a certain number c plus an infinite geometric series in b, in other words

1/a = c + d/(1 - b^-k) = [(cb^k - c) + db^k] / (b^k - 1)

so if d is not zero (b^k - 1) is divisible by a, and if d = 0 then b^k is divisible by a.

This is certainly less elegant, but is it the same thing?

 

[micromass]

Your proof is quite nice, but I don't see how you obtained the following:

Then 1/a will be a certain number c plus an infinite geometric series in b

You somehow applied Euclid's algorithm to something, but I don't quite see it. (also not that Euclid's algorithm applies to integers only!)

 

[Petr Mugver]

You somehow applied Euclid's algorithm to something, but I don't quite see it. (also not that Euclid's algorithm applies to integers only!)

For (a simple) example, let a = 6 and b = 10.

Calculating 1/6 in base 10 (that's what I mean by Euclid's Algorithm) you get

1/6 = 0,1666... = 16,666.../100 = (10 + 6 x sum_k(10^-k))/100 =
= (10 + 60/9)/100 = 150/900

so x = 3 and y = 2.

 

[marshmellow]

Would it make sense to think of the graph of z = b^y - b^x?

if (b^y-b^x)/a = integer

b^y - b^x = integer * a

z = integer * a

It should be a plane that intersects all values of z.